Go Back   CodeCall Programming Forum > Software Development > Tutorials > C Tutorials
Register Blogs Search Today's Posts Mark Forums Read

C Tutorials All C Tutorials and Code

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
  #1 (permalink)  
Old 01-01-2009, 10:03 PM
WingedPanther's Avatar
Super Moderator
 
Join Date: Jul 2006
Age: 36
Posts: 11,435
WingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud of
ADTs: Stacks and Queues Part 1: Using Arrays

One of the simplest Abstract Data Types (ADTs) is the stack. A stack provides the following methods: pop(), push(), top(), empty() and size(). A queue provides pop(), push(), front(), empty() and size(). The precise details of the ADTs will vary from description to description, but we will use these. pop() and push() are always provided.

The basic concept for these two data types is the following: a stack stores data in a list like a stack of plates. push() places data on top of the stack, and pop() removes the topmost item on the stack. This is known as a Last In First Out (LIFO) structure. A queue is more like a line at a bank. push() places data at the back of the line, and pop() removes data from the front of the line. This is known as a First In First Out (FIFO) structure.

The specification for the methods for stack are as follows:
pop(): returns the top element of the stack and removes it from the stack. If there are no elements in the stack, it throws and UnderFlow exception.
push(): takes an element as a parameter and places it at the top of the stack. If the element cannot be added, it throws an OverFlow exception.
top(): returns the top element of the stack but does not remove it from the stack. If there are no elements in the stack, it throws and UnderFlow exception.
empty(): returns true if the stack has no elements, false otherwise.
size(): returns the number of elements in the stack.

The specification for the methods for queue are as follows:
pop(): returns the first element of the queue and removes it from the stack. If there are no elements in the queue, it throws and UnderFlow exception.
push(): takes an element as a parameter and places it at the end of the queue. If the element cannot be added, it throws an OverFlow exception.
front(): returns the first element of the queue but does not remove it from the queue. If there are no elements in the queue, it throws and UnderFlow exception.
empty(): returns true if the queue has no elements, false otherwise.
size(): returns the number of elements in the queue.

Based on the above, we can create a program that should work, regardless of how we implement these ADTs. We'll assume we are dealing with string data for now, but everything could be adjusted to use templates.

teststack.cpp
Code:
#include <string>
#include <iostream>
#include "stack.h"
#include "queue.h"
using std::cout;
using std::string;

int main()
{
  Stack mystack;
  Queue myqueue;
  string temp;

  //initial state verified
  cout<<"initial size of stack: "<<mystack.size()<<"\n";
  cout<<"initial size of queue: "<<myqueue.size()<<"\n";
  int i;

  //populate the stack with 'a' – 't'... maybe
  try
  {
    for(i=0;i<20;i++)
    {
      temp = 'a'+i;
      mystack.push(temp);
    }
  }
  catch(OverFlow)
  {
    cout<<"stack overflow at i = "<<i<<"\n";
  }
  cout<<"size of stack after for loop: "<<mystack.size()<<"\n";

  //clear the stack, printing the results and force underflow
  try
  {
    for(;i>=0;i--)
      cout<<mystack.pop()<<"\n";
  }
  catch(UnderFlow)
  {
    cout<<"stack underflow at i = "<<i<<"\n";
  }
  cout<<"size of stack after for loop: "<<mystack.size()<<"\n";
  
  //populate the queue with 'a' – 't'... maybe
  try
  {
    for(i=0;i<20;i++)
    {
      temp = 'a'+i;
      myqueue.push(temp);
    }
  }
  catch(OverFlow)
  {
    cout<<"queue overflow at i = "<<i<<"\n";
  }
  cout<<"size of queue after for loop: "<<myqueue.size()<<"\n";

  //clear the queue, printing the results and force underflow
  try
  {
    for(;i>=0;i--)
      cout<<myqueue.pop()<<"\n";
  }
  catch(UnderFlow)
  {
    cout<<"queue underflow at i = "<<i<<"\n";
  }
  cout<<"size of queue after for loop: "<<myqueue.size()<<"\n";
  
  //put remaining stack methods through their paces
  mystack.push("string");
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<mystack.top()<<"\"\n";
  cout<<"the stack is ";
  if (!mystack.empty()) 
    cout<<"not ";
  cout<<"empty\n";
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<mystack.pop()<<"\"\n";
  cout<<"stack contains "<<mystack.size()<<" element(s)\n";
  cout<<"the stack is ";
  if (!mystack.empty()) 
    cout<<"not ";
  cout<<"empty\n";

  //put remaining queue methods through their paces
  myqueue.push("string");
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<myqueue.front()<<"\"\n";
  cout<<"the stack is ";
  if (!myqueue.empty()) 
    cout<<"not ";
  cout<<"empty\n";
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the top element of the stack is \""<<myqueue.pop()<<"\"\n";
  cout<<"stack contains "<<myqueue.size()<<" element(s)\n";
  cout<<"the stack is ";
  if (!myqueue.empty())
    cout<<"not ";
  cout<<"empty\n";
}
Notice that all of this assumes that the implementation of the queue and stack do not impact the ability to use them. Note that this could also be considered part of Test Driven Development for verifying the functionality of a queue and stack.

One of the first things we need to do is define the exceptions we'll be using. Since the only purpose of these is to enable us to flag the type of error, they're actually pretty boring. The exceptions OverFlow and UnderFlow are just classes with no data.

exceptions.h:
Code:
#ifndef EXCEPTIONS_H
#define EXCEPTIONS_H
class OverFlow
{
};

class UnderFlow
{
};
#endif
The first version of the Stack and Queue classes that we'll look at are based on arrays. To highlight the issues of using a small array, we'll use 10 element arrays so we can easily hit an OverFlow condition. In realistic cases, a Stack or Queue can easily end up having to hold hundreds of elements at a time. That, of course, means they can also end up needlessly wasting space if you set them up to hold thousands of elements when only 10 are needed. Our model works as indicated below:
Code:
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
data:      | "d1"| "d2"| "d3"| "d4"| "d5"|     |     |     |     |     |
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
index: -1     0     1     2     3     4     5     6     7     8     9
The value of index marks the position of the top of the stack. It is increased or decreased to mark when an element is pushed or popped. -1 means the stack is empty.

For the Stack, we start with our includes and declaration. We could use a const int to store the size of the array we'll be using, but that isn't really necessary.
stack.h
Code:
#ifndef STACK_H
#define STACK_H
#include <string>
#include "exceptions.h"

class Stack
{
  std::string data[10];
  int index;
public:
  int size(void);
  void push(std::string);
  std::string pop(void);
  std::string top(void);
  bool empty(void);
  Stack();
};
index just stores the current location of the last element added. Because arrays are 0 based, we have to add 1 to the index to get the size of the stack. When pushing a new element, notice that we check to make sure we have space before adding the new element.
Code:
int Stack::size(void)
{
  return index+1;
}

void Stack::push(std::string newstring)
{
  if (index==9)
    throw OverFlow();
  index++;
  data[index]=newstring;
}
pop and top are basically the same. We check to see if there are any elements first, then return the top element. We also decrement the index on a pop.
Code:
std::string Stack::pop(void)
{
  if (index==-1)
    throw UnderFlow();
  return data[index--];
}
std::string Stack::top(void)
{
  if (index==-1)
    throw UnderFlow();
  return data[index];
}
Finally, empty is simple to implement. The constructor only needs to make sure the index is set.
Code:
bool Stack::empty(void)
{
  return index==-1;
}

Stack::Stack(void)
{
  index=-1;
}
#endif
end stack.h

Using an array to implement a stack has the wonderful advantage of being simple. Based on that, it is natural to want to do the same thing for a Queue. The problem is that we have to keep track of the front and back of the tail, somehow. The implementation below takes the approach of never moving elements (an expensive operation) and instead keeping track of the tail of the queue and the number of elements in the queue (so we can locate the head of the queue).
Code:
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
data:      | "d1"| "d2"| "d3"| "d4"| "d5"|     |     |     |     |     |
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
tail: -1     0     1     2     3     4     5     6     7     8     9
count: 5
Here, tail would be equal to 4, count is 5, so to find the head we do tail-count+1 (or tail-(count-1)). Each time we pop an element, we will decrement count. Each time we push an element, we will increment both count and tail. What can happen, however, is that as items are popped off the head of the queue, we need to be able to wrap around the queue, as in the situation below:
Code:
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
data:      | "d6"|     |     |     |     | "d1"| "d2"| "d3"| "d4"| "d5"|
           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
tail: -1     0     1     2     3     4     5     6     7     8     9
count: 6
Here, tail would be equal to 0, and count is 6. If we do the previous calculation to find the head, we will do (0 – 6+ 1) = -5. This is obviously incorrect, so we have to rework our formula to this: (tail-count+1+10)%10. The +10 makes sure we are doing the modulus of a positive number. The %10 then gets us within the bounds of the array. When incrementing tail, we will have to make sure we also apply a %10 so it doesn't exceed 9. If you think this is complicated, you should try some of the other methods to implement an array-based queue. The result of all this is below, a stack modified for the necessary calculations:

queue.h
Code:
#ifndef QUEUE_H
#define QUEUE_H
#include <string>
#include "exceptions.h"

class Queue
{
  std::string data[10];
  int tail, count;
public:
  int size(void);
  void push(std::string);
  std::string pop(void);
  std::string front(void);
  bool empty(void);
  Queue();
};

int Queue::size(void)
{
  return count;
}

void Queue::push(std::string newstring)
{
  if (count==10)
    throw OverFlow();
  tail=(tail+1)%10;
  count++;
  data[tail]=newstring;
}

std::string Queue::pop(void)
{
  if (count==0)
    throw UnderFlow();
  count--;
  return data[(tail-count+10)%10];
}

std::string Queue::front(void)
{
  if (count==0)
    throw UnderFlow();
  return data[(tail-(count-1)+10)%10];
}

bool Queue::empty(void)
{
  return count==0;
}

Queue::Queue(void)
{
  count=0;
  tail=-1;
}
#endif
end queue.h

The output of this program is:
Code:
initial size of stack: 0
initial size of queue: 0
stack overflow at i = 10
size of stack after for loop: 10
j
i
h
g
f
e
d
c
b
a
stack underflow at i = 0
size of stack after for loop: 0
queue overflow at i = 10
size of queue after for loop: 10
a
b
c
d
e
f
g
h
i
j
queue underflow at i = 0
size of queue after for loop: 0
stack contains 1 element(s)
the top element of the stack is "string"
the stack is not empty
stack contains 1 element(s)
the top element of the stack is "string"
stack contains 0 element(s)
the stack is empty
stack contains 1 element(s)
the top element of the stack is "string"
the stack is not empty
stack contains 1 element(s)
the top element of the stack is "string"
stack contains 0 element(s)
the stack is empty
Part 2 will reimplement these using linked lists.
__________________
CodeCall Blog | CodeCall Wiki | Shareware
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

Last edited by WingedPanther; 01-02-2009 at 10:54 AM.. Reason: add output and links
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #2 (permalink)  
Old 01-02-2009, 04:13 PM
amrosama's Avatar
Code Warrior
/////////|||||\\\\\\\\\
 
Join Date: Aug 2007
Location: Pyramids st, Giza, Egypt
Age: 21
Posts: 8,112
amrosama is a splendid one to beholdamrosama is a splendid one to beholdamrosama is a splendid one to beholdamrosama is a splendid one to beholdamrosama is a splendid one to beholdamrosama is a splendid one to beholdamrosama is a splendid one to behold
Send a message via MSN to amrosama
Re: ADTs: Stacks and Queues Part 1: Using Arrays

awsome tutorial,
looks complicated so ill print it
__________________
im a code-warrior, see my avatar
who said arabs cant dance?
and who said arabs cant drive??!
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #3 (permalink)  
Old 01-02-2009, 05:57 PM
whitey6993's Avatar
Programming Professional
 
Join Date: Dec 2008
Location: In front of my Computer
Posts: 291
whitey6993 has a spectacular aura aboutwhitey6993 has a spectacular aura about
Re: ADTs: Stacks and Queues Part 1: Using Arrays

Great tutorial +rep
__________________
"Simplicity is a cornerstone of genius. Have you ever heard anyone say 'I love that idea, its so complicated!'"
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #4 (permalink)  
Old 01-02-2009, 06:25 PM
WingedPanther's Avatar
Super Moderator
 
Join Date: Jul 2006
Age: 36
Posts: 11,435
WingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud of
Re: ADTs: Stacks and Queues Part 1: Using Arrays

__________________
CodeCall Blog | CodeCall Wiki | Shareware
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #5 (permalink)  
Old 01-04-2009, 03:04 PM
MathX's Avatar
Guru
 
Join Date: Oct 2008
Location: Kosovo
Age: 19
Posts: 3,994
MathX has a spectacular aura aboutMathX has a spectacular aura about
Send a message via MSN to MathX
Re: ADTs: Stacks and Queues Part 1: Using Arrays

Great job!
__________________
My Blog
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #6 (permalink)  
Old 01-05-2009, 04:22 AM
Newbie
 
Join Date: Oct 2008
Posts: 2
kannan v is an unknown quantity at this point
Thumbs up Re: ADTs: Stacks and Queues Part 1: Using Arrays

nice
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #7 (permalink)  
Old 01-09-2009, 03:37 PM
Turk4n's Avatar
Code Warrior
 
Join Date: May 2008
Location: 4chan.org/g/
Age: 20
Posts: 3,822
Turk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud of
Send a message via MSN to Turk4n Send a message via Skype™ to Turk4n
Re: ADTs: Stacks and Queues Part 1: Using Arrays

Are stacks in C++ equivalent to ArrayList and stacks in java or do they differ?
__________________

Hatsune Miku ~❤❤❤
初音ミク。~❤❤❤
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #8 (permalink)  
Old 01-09-2009, 04:00 PM
WingedPanther's Avatar
Super Moderator
 
Join Date: Jul 2006
Age: 36
Posts: 11,435
WingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud ofWingedPanther has much to be proud of
Re: ADTs: Stacks and Queues Part 1: Using Arrays

I don't know enough about ArrayList and stacks in java to say for certain. Also note that there are a LOT of built-in ADTs as part of the C++ Standard Template Library that probably correspond to them, among other things.
__________________
CodeCall Blog | CodeCall Wiki | Shareware
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #9 (permalink)  
Old 01-09-2009, 04:14 PM
Turk4n's Avatar
Code Warrior
 
Join Date: May 2008
Location: 4chan.org/g/
Age: 20
Posts: 3,822
Turk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud ofTurk4n has much to be proud of
Send a message via MSN to Turk4n Send a message via Skype™ to Turk4n
Re: ADTs: Stacks and Queues Part 1: Using Arrays

Okay
__________________

Hatsune Miku ~❤❤❤
初音ミク。~❤❤❤
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
  #10 (permalink)  
Old 11-15-2009, 08:45 PM
chili5's Avatar
Code Slinger
 
Join Date: Mar 2008
Posts: 7,018
chili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond reputechili5 has a reputation beyond repute
Re: ADTs: Stacks and Queues Part 1: Using Arrays

Quote:
Originally Posted by Turk4n View Post
Are stacks in C++ equivalent to ArrayList and stacks in java or do they differ?
Yes. The difference between Stacks and Arrays is that Stacks only let you access the top item in the Vector. In Java, a Stack is a Vector (same as the ArrayList).
__________________
"Whenever you remember, I'll be there/
Remember how we reached that dream together" - Carrie Underwood
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
Reply



Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lists, Stacks, and Queues Sionofdarkness Python 2 07-26-2006 09:38 PM


All times are GMT -5. The time now is 08:16 AM.


vBulletin v3.8.0 ©2010, Jelsoft Enterprises Ltd.


no new posts

LinkBacks Enabled by vBSEO 3.1.0