ADTs: Stacks and Queues Part 1: Using Arrays

[WingedPanther]

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

#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:

#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:

           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
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

#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.

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.

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.

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).

           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
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:

           +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
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

#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:

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.

[amrosama]

awsome tutorial,
looks complicated so ill print it

[whitey6993]

Great tutorial +rep

[WingedPanther]

[MathX]

Great job!

[kannan v]

nice

[Turk4n]

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

[WingedPanther]

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.

[Turk4n]

Okay

[chili5]

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).