Section 4 - The Stack Class

4A.4.1 The Picture of a List-Based Stack

Now that we've defined the basic StackNode class, I can show you a picture of the plan.  Our stack will consist of a list of nodes linked together.  The top of the list will be the first StackNode in the list.  Say we have StackNodes SN1, SN2, etc.  Here is the picture if we have pushed SN1, SN2, SN3 and SN4, in that order

top  →  SN4  →  SN3  →  SN2  →  SN1  →  null

The last node in the list has a null in its next field, which is how we know it is the end of the list.  The top is simply a reference to a StackNode and is not itself a full node.  Each of the other items in the list is a StackNode.

If we instantiated a new node SNnew, and pushed it onto the stack it would go at the top.  Here is the stack after a stk.push(SNnew):

top → SNnew → SN4 → SN3 → SN2 → SN1 → null

Of course, if we popped two items off the stack, they would be SNnew and SN4, leaving us with:

top  →  SN3  →  SN2  →  SN1  →  null

This is the picture you should keep in your head as you follow the current discussion.

4A.4.2 A Stack of Generic Data-less StackNodes

We complete the current phase by creating a second class (not base or derived, just a second class) called Stack that uses the StackNodes.   Here is the class prototype:

// Class Stack ---------------------------------------
class Stack
{
  StackNode *top;

public:
  Stack();
  virtual ~Stack();
  void push(StackNode  *newNode);
  StackNode *pop();
  void showStack();
};

Without even seeing the definitions of the Stack methods, we already notice something interesting.  A Stack contains nothing more than a StackNode *, that is a single StackNode pointer.  How can any class that contains only one pointer potentially hold the hundreds or thousands of StackNodes that we are going to push() onto it?  Simple.  As we push() items onto the Stack, we will allocate new StackNodes.  That pointer, top, is going to point to the first item on the Stack, and from there, each item will point to the next.  It is like a railroad train: the engine pulls only one car directly.  But that car pulls the next which pulls the next, etc.

It will help for you to see the definitions of the Stack member methods:

// Stack method definitions --------------------------
Stack::Stack()
{
  top = NULL;
}

Stack::~Stack()
{
  // don't delete the stack nodes on the stack - they belong to client.
  // nothing to do. If we were cloning nodes in push() then we would need
  // to delete the remainder of the list - but we are not cloning nodes
  // in this class.
}

StackNode *Stack::pop()
{
  StackNode *temp;

  temp = top;
  if (top != NULL)
  {
    top = top->next;
    temp->next = NULL;   // don't give client access to stack!
  }
  return temp;
}

void Stack::push(StackNode  *newNode)
{
  if (newNode == NULL)
    return;   // emergency return
  newNode->next = top;
  top = newNode;
}

void Stack::showStack()
{
  StackNode *p;

  // Display all the nodes in the stack
  for( p = top; p != NULL; p = p->next )
    p->show();
}

// end Stack method definitions ---------------------

Notice that in this case the destructor has nothing to do. If the client disposes of the stack while there is still something in it, the left-over StackNodes should not be burned up by the destructor. This is the job of the client, who instantiated these nodes in the first place.

Also, we see that this Stack takes pointers to pre-built StackNodes for its push() operation. The client must new the node and pass its pointer to push().

Similarly, pop() returns a pointer to a StackNode. The client can use this to process and destruct the StackNode. You will see how this gets used next.

What about statements like these?

top =  top->next;

p = p->next;

These are the essence of linked-list programming. Top and p are StackNode pointers and this is the way in which a StackNode pointer moves ahead one node in the list.  This is the linked-list equivalent of k++, for an int k. 

Whatever node top (or p) was pointing to, after this statement it will be pointing to the successor to that node.  Why?  Because top->next points to the next node after the node pointed to by top. We are copying the address from the next field of the node top currently points to, into the pointer top, replacing the old address with the new, updated address.

Here is a main() that utilizes the above classes.

// main method ---------------------------------------
int main()
{
  Stack stk;
  StackNode *p;

  // build the stack
  for (int k = 0; k<5; k++)
  {
    p = new StackNode();
    stk.push(p);
  }

  // show the stack, deleting as you pop
  while ( (p = stk.pop()) != NULL)
  {
    p->show();
    delete p;
  }
  cout << endl;
  return 0;
}

Here is the output:

 

I know this is a dizzying example because all of the nodes look exactly alike.  We don't have any real data in our StackNodes. This example is just to show you how the base classes get used so that when we derive sub-classes from them, you will already be familiar with the fundamentals.

I did not try to use the Stack::showStack() method in this example because I'm saving that for a future lecture.  In the above example, I am just using the individual StackNode's show() method to show each node as we pop it off the stack in a loop.

As usual, I want you to copy/paste the code into your compiler, run the program and make changes to the main() so you can experiment with your own manipulation of this elegant class.  I will put the entire listing in the next section so it is easy for you to access.

4A.4.3 Security Considerations

The very astute among you might have noticed that the line in Stack::pop() that reads

temp->next = NULL;   // don't give client access to stack

does not really remove all the security hazards in this Stack class.  The purpose of this line is to zero-out the next pointer of the popped node prior to giving it to the client.  In that way, the client can't use that node to poke into the list and change links, destroying its integrity (think about naughtyNode = stk.pop(); followed by naughtyNode->next->next = NULL;).  The above statement disallows this, so that hole is plugged.

Fine, but the fact is the client already has a way into the stack. It can use any node that it pushes then access the list of nodes through that pushed-node.  Play with this and you'll find a way in.  So, we really do have an insecure class after all, and the well-meaning measures inside pop() don't solve these other problems. These don't present a real concern, however, for the following reasons.

1. This class is not for public consumption -- we will wrap it in secure derived Stack classes that the client will use.  It will be the job of these other, derived, Stack classes to protect themselves, and no amount of client shenanigans will be able to penetrate their veil.
2. This class is a demonstration of re-usability through inheritance.  It is not about security.  We have other means of making the classes secure, and when I present linked lists later on, I will talk about them.
3. You can fix these problems here-and-now by providing enough const modifiers and other methods in the appropriate places, but it isn't worth the hassle given, 1. and 2., above.