Section 6 - Array-Based Stacks

3B.6.1 An Array-Based Stack

A stack data structure (which is different from the program stack that we discussed earlier!) satisfies these rules:

• It stores data for us; if we have a stack object, say s, then when we want s to store a string, say "hotdog", we push it onto the stack with a call: s.push("hotdog"). "hotdog" is then placed into the stack s and then joins the other items that were on the stack.
• Whenever we go to retrieve data (called popping) from the stack, the item we get will always be the most recent item that we pushed. So if we call s.pop() right after the above push, the item returned by the pop() method would be "hotdog". This also has the effect of removing "hotdog" from the stack, so it is no longer there.

Notice that in the last paragraph, we said "the item returned by pop()."  That means pop() returns a value to the client - it does not make an independent decision to, say, print the popped item to the screen. 

Both push() and pop() will return bools.  A return of true means that the call was successful, false means that there was too much (or too little) on the stack to be pushed (or popped).

Let's say that we have defined a Stack class, and we have instantiated a Stack object, s.  Then, using s, if we push three times:

s.push("four");
s.push("nine");
s.push("two");

Then the Stack s looks like this:

top →
"two"
"nine"
"four"

If you then pop() once, the "two" is returned from the stack and it will then contain:

top →
"nine"
"four"

If you push() another item:

s.push("7.3");

the stack becomes:

top →
"7.3"
"nine"
"four"

If you pop() now, the "7.3" will be returned and if you pop() immediately after that, the "nine" will be returned, leaving only the "four" on the stack. I think you get the idea.

Since s is an object of class Stack, we should be able to instantiate more than one Stack at a time, say s1 and s2, and push() and pop() from them independently. 

3B.6.2 A Stack Example

This example defines the Stack class using techniques we have already learned.  This example is based on doubles. You'll have to compare the output to the source code carefully so you can associate the pops with the output that results.

#include <iostream>
using namespace std;

// ---------- Class MyStack Prototype -----------
class MyStack
{
private:
 static const int SIZE = 5;
 double stck[SIZE];
 int tos;

public:
  MyStack();
  bool push(double item);
  bool pop(double &item);
  void clearStack();
  bool testStack(int num_requested = 1);
}; // end of  MyStack prototype -----------------

// start of client ------------------------------
int main()
{
  MyStack stk1, stk2;
  int k;
  double result;

  // Test the Stack -----
  if ( !stk1.testStack(1) )
    cout << "empty stack; cannot pop\n";

  // push too much intentionally
  for (k = 0; k < 10; k++)
    if ( ! stk1.push( k * 1.1 ) )
      cout << "stack stk1 full; cannot push\n";

  for (k = 0; k < 5; k++)
    if ( ! stk2.push( k * 9 ) )
      cout << "stack stk2 full; cannot push\n";

  // pop too much intentionally (use testStack() for fun)
  cout << "\n--------- First Stack ---------\n";
  for (k = 0; k < 8; k++)
    if ( stk1.testStack(1) )
    {
      stk1.pop(result);
      cout << result << " : ";
    }
    else
      cout << "(empty stack; cannot pop) :";
    cout << endl;

  // pop but test with pop(), not teststack()
  cout << "\n--------- Second Stack ---------\n";
  for (k = 0; k < 8; k++)
    if ( stk2.pop(result) )
      cout << result << " : ";
    else
      cout << "(empty stack; cannot pop) :";
    cout << endl << endl;

  return 0;
}

// ----------- Class MyStack Definitions ------------
MyStack::MyStack()
{
  tos = 0;
}

// ---------------------------------------------------
bool MyStack::push( double item )
{
  if (tos == SIZE)
    return false;
  stck[tos++] = item;
  return true;
}

// ---------------------------------------------------
bool MyStack::pop(double &item)
{
  if (tos==0)
    return false;

  item =  stck[--tos];
  return true;
}
// ---------------------------------------------------
void MyStack::clearStack()
{
  tos = 0;
}

// ---------------------------------------------------

bool MyStack::testStack(int num_requested)
{
  if (tos >= num_requested)
    return true;
  return false;
}
// end of  MyStack definitions -------------------------

And the output:

Most of the example should be clear.  The instance method testStack() needs explanation.  It returns true if the number of items in the stack is greater than or equal to the parameter passed.  In our RPN calculator we will want to pop two items off the stack in order to compute their sum, difference, etc.  So we will be testing the stack by calling testStack(2) and look at the return value (true or false).

Also, since pop() needs to modify one of its parameters, we had to use a reference parameter.  We had reference parameters in the first lesson of this course.

3B.6.3 There are Stacks And Then There Are Stacks

You may have used built-in stack data structures in a collections or container framework in the past.  You will certainly do so in the future.  Be careful to read the API of the class carefully because each implementation is slightly different.  Some stacks have a pop() that removes but does not return the top of the stack, leaving the return to another function, often named top().  Other implementations don't have pop() or push() but, instead, use names like pop_back() and push_back() (underscore, rather than camelCase, is correct - this is what the C++ STL uses.)  While the ideas are universal, the details are not, so don't assume anything when you encounter a new stack class.