Stacks

A stack is an ordered collection of entries that can be accessed at only one end (called the top). Therefore, whenever an item is added or removed, it will be added or removed from the top.

It's important to recognize that entries will be removed from a stack in the reverse order in which they are placed on the stack. Because of this property, a stack is called a "Last In - First Out" (LIFO) data structure.

There is special terminology for adding or removing items from a stack. Adding an entry to a stack is known as a push operation, while removing an entry from a stack is known as a pop operation.

There are two possible errors that can be caused when pushing onto/popping from a stack:

1. stack underflow - trying to pop an item from an empty stack
2. stack overflow - trying to push an item onto a full stack

A simple use of a stack is to reverse a word:

while (there are characters in a word)
   read a single character
   push the character onto the stack
endwhile

while (the stack is not empty)
   write the top character to the screen
   pop the character from the stack
endwhile

Another use of a stack is to ensure that parenthesis are balanced (i.e. that every left parenthesis has a corresponding right parenthesis):

failed = false  /* assume the string is balanced */

while (there are characters in the expression)
   ch = character from string

   if (ch is left parenthesis)
     push ch onto stack

   else if (ch is a right parenthesis AND stack is not empty)
     pop the stack

   else if (ch is a right parenthesis AND stack is empty)
     failed = true
   endif
endwhile

if (failed = false && stack is empty)
  everything is OK
else
  there is a problem
endif

This example can be carried a little further to actually evaluate an arithmetic expression:

while (there are items in the expression)
   if (item is a number)
     push onto number stack

   else if (item is an operator)
     push onto operator stack

   else if (item is a right parenthesis)
     pop the number stack twice
     pop the operator stack
     apply the operator
     push the result onto the number stack
   endif
endwhile

pop the final result

There are three ways that a stack can be implemented:

1. fixed-size array
2. dynamic array
3. dynamically using a linked list

Fixed-size array implementation

This type of implementation requires two private data members:

1. an array
2. an integer variable that indicates the top spot in the array

It will also have a number of public methods that can be used to add/remove items from the stack, determine if the stack is empty, the number of items on the stack, etc...

template <class T>
class stack
  {
  public:
    stack();               /* creates an empty stack */
    void pop();            /* removes the top item from the stack */
    void push(const T &);  /* adds an item to the stack */
    bool empty();          /* determines if the stack is empty */
    int size();            /* returns the number of items in the stack */
    T & top();             /* returns a reference to the top item on the stack */

  private:
    T data[SIZE];          /* item being stored */
    int top;               /* subscript of item at the top of the stack */
    static const int SIZE = 20;    /* maximum size of the stack */
  };


template <class T>
stack::stack()
  {
  top = -1;             /* indicates an empty stack */
  }

Dynamic array implementation

This is similar to the fixed-size array, except for the fact that the constructor will allocate memory for a specific number of nodes. Because of this, there will be a third private member that will hold the maximum size of the array.

Linked List implementation of a stack

This is a popular way to implement a stack because it can grow and shrink during execution, without having a predefined size. The head pointer will always point to the top item in the stack