Introduction to Stacks

• The stack data structure keeps lists of elements in a manner where the last item received is the item at the top (or first item out) of the stack.  This servicing scheme is called LIFO (last in-first out). 

• While we may not be real familiar with this operating order (except in Jesus' parable of the owner of the vineyard and his hiring practices), this manner of service occurs frequently in computer science.

  • For example, the following sequence of operations behave as a stack:

    • Function calls (including recursion)

    • Interrupts

    • Some searching algorithms

    • And more .....

• In addition to constructors, the destructor, an assignment operator, etc, typically stacks have the member functions push() and pop().  Push() puts element into the stack, and pop() takes one out.

• Examples:  Below is a stack (of characters) with three elements.  It was create with the code:

  myStack.push('g');

  myStack.push('y');

  myStack.push('c');

• Take note that the last element, 'c', added is at the "top" of the stack.  If we were to pop() from the stack, the 'c' would be the first element removed.

• We can turn the stack over on it's side, like so: 

• When we do this, you can see that the stack can be implemented from an ordinary character array.
  • For example the array above could be declared as:  char storage[6];
• We may also want to keep some other information on the current state of the stack, like how many elements are in the stack (e.g. int num) and how many elements the stack could hold (e.g., int size).
• To get a complete idea of how we might do this, see the stack implementation stack.h and stack.cpp.
  • Test program for stacks:  stack_test.cpp