Section 5 - Building On Top of ArrayLists: The Stack

2B.5.1 The Stack Data Structure

As our first application of the FHvector and FHlist templates, we will construct our own stack template class on top of one of those two. All the hard work that went into those classes will make our work here much shorter and cleaner. This is the kind of thing you are responsible for doing in several assignments.

A stack ADT is a data structure that admits storage and retrieval from only one position in the underlying array, namely a privileged position called the top. A stack is a last-in-first-out, or LIFO, structure, because whatever is pushed onto the top of the stack most recently is what is returned when we pop an item off the stack. Normally there is an operation that returns the value at the top of the stack without removing (i.e., popping) it. This is sometimes called top(). We cannot place anything into the stack via any operation other than push(), and we cannot retrieve or access any part of the stack other than the top, and we do that using pop() or top().

Here is the picture of the data internal to the stack. We can only access the top:

There are many ways to approach a stack. Since both the vector and list ADTs have operations like push_back(), pop_back() and back(), which do basically what a stack's push(), pop() and top() do, an application programmer may simply use these data structures directly, and this is the easiest approach. Normally, vector is used because it is faster.

The problem with using vector as a stack is that the programmer might make use of operations like brackets, [], or front() which can damage confuse the stack operations.

Let's say the development group we are in wants us to wrap a vector in our own, user-defined, data type called FHstack which contains only pure stack operations, push(), pop() and top(). We can do this very effectively by defining our own template whose only data item is an STL vector or FHvector.

The idea is this:

• Provide a bool push( Object &x ) which, internally, calls the vector's push_back() method.
• Provide an Object & pop() which, internally, calls the vector's pop() and pop_back() methods.
• Provide a const Object & top() which, internally, calls the vector's back() method.

2B.5.2 Our Implementation Choices

Now our development group has a fully functional stack data structure which restricts operations to push(), pop() and top(). It is pictured in the diagram below, but interpret the picture with caution. The location of the arrows does not imply that we are pushing things onto one side of the stack and popping them off the other -- that would be a queue, not a stack. Instead, the location of the arrows is just a way to distinguish input vs. output operations on the stack.

The decisions that are made by the project lead are:

1. Do we want pop() to both remove and return the top of the stack or just remove it?
2. How do we handle popping off of an empty stack? We can throw an exception of our own or we can return silently so the client does not crash, even without try/catch blocks.
3. Do we want extra methods that do further non-stack operations (for example a clear() or reset() to pop all remaining values off the stack)?
4. Do we want to use vector or list as our underlying data structure? Or is performance so critical that we want to use raw arrays and re-invent a couple of those wheels from scratch?

In our case, we will answer these questions the simplest way:

1. pop() will both remove and return the top.
2. pop() will return silently with a default Object in case of an empty stack.
3. There will be no extra methods - only pop(), top() and push().
4. We will use FHvector, internally.

2B.5.3 The Implementation

Here is the prototype for our template FHstack:

// FHstack protoype -------------------------
template <class Object>
class FHstack
{
private:
   FHvector<Object>  mVector;

public:
   bool push(const Object &x);
   Object &pop();
   const Object &top();
   const Object &pop() const;
};

As you can see, it's pretty short and there is no fluff. Building on top of a vector makes the development almost fun.

The implementation is even funner:

// FHstack method definitions ---------------
template <class Object>
bool FHstack<Object>::push(const Object &x)
{
   mVector.push_back(x);
   return true;
}

template <class Object>
Object & FHstack<Object>::pop()
{
   static Object retVal;
   if (mVector.size() == 0)
      return retVal;
   retVal = mVector.back();
   mVector.pop_back();
   return retVal;
}

template <class Object>
const Object & FHstack<Object>::top()
{
   static Object retVal;
   if (mVector.size() == 0)
      return retVal;
   retVal = mVector.back();
   return retVal;
}

One item to note is this test in pop() and top():

   if (mVector.size() == 0)
      return retVal;

Because we are using FHvector we could actually remove this entirely and surround the pop_back() and back() invocations in a try/catch block which catches the FHvector<Object>::VectorEmptyException, and returns the default if caught. This is slightly more efficient, however it relies on FHvector being our underlying data type. If we anticipate switching to STL vectors at some point, the exception mechanism would not work. So the test on size() is more flexible.

A main() that uses our new stack might look like this:

// FHstack main
// CS 2C, Foothill College, Michael Loceff, creator

#include <iostream>
#include <string>
using namespace std;
#include "FHvector.h"

// FHstack protoype and implementation -------------------------
// (shown above)

// --------------- main ---------------
int main()
{
   int k;

   FHstack<int> myStack;

   for (k = 0; k < 10; k++)
      myStack.push(k);

   int theTop = myStack.top();
   cout << "top: " << theTop << endl;

   for (k = 0; k < 12; k++)
      cout << myStack.pop() << endl;
}

The run is:

top: 9
9
8
7
6
5
4
3
2
1
0
0
0
Press any key to continue . . .