Section 3 - Building Blocks of A Dynamic Stack

4A.3.1 Linked List Style Programming

We are going to take a few minutes to create a new class.  Once we do that, we can return to inheritance and derived classes.

In a past lesson we created a stack data structure.  We now want to implement a stack in another manner - one which will give us a more flexible basis for other solutions. It will be based on a very general data structure called a linked-list.

Linked lists are powerful structures that are explored in CS 2C and other data structures classes. They can be used for many things beside creating dynamic stacks.  Our implementation of stacks using linked lists will reveal the power of linked lists and give you an idea of other things you can do with them.

The original stack class we wrote had a fixed-size array inside it.  Instead of using a fixed-size array we will only allocate memory as needed. That is, every time we get a push() request, we will allocate another object to hold the item being pushed. That way, the stack will grow and shrink as needed.

The concepts that we will use besides linked-lists (which we will learn here) are inheritance (i.e. derived classes) and dynamic memory allocation.

4A.3..2 A Small Node Class

We will start with a small class that we shall call a StackNode.  A StackNode will hold a single item that is to be pushed onto the stack.  The plan will be to dynamically create a StackNode object whenever the client wants to push(), and we will delete that node when the client wants to pop().  But don't worry about push() or pop(), just yet.  Let's first create our StackNode class.

// Class StackNode  ----------------------------------
class StackNode
{
public:
  StackNode *next;

  StackNode();
  virtual ~StackNode();
  void show();
};

And here is the section that defines these methods:

// StackNode method definitions --------------------------
StackNode::StackNode()
{
  next = NULL;
}
StackNode::~StackNode()
{
  // nothing needed
}
void StackNode::show()
{
  cout << "(generic node) ";
}
// end StackNode method definitions ---------------------

The first thing you will find odd about this class is that the only data is called next, and next is nothing more than a pointer to a StackNode.  In other words, the next member of the StackNode class points to another StackNode.  That might sound circular, but it is actually correct.  What holds these StackNodes together are the next pointers.  In a given list we would start with the first StackNode whose next member would point to the second StackNode.  Then the second StackNode's next member would point to the third StackNode, and so on.

You may wonder how we can construct anything useful using a class that has no data beside this next member.  There are no ints, no doubles, no strings, no Galaxies.  What are we going to be creating a stack of, exactly, if there is no data?  Great question.  In fact, we will not be providing data to the StackNode now because we will do that later when we derive a new subclass from StackNode.  Remember our Phone and PhoneWX?  See where I'm going with this?  We can add to the base class StackNode by deriving another class from it.

But don't worry about that yet.

Another new feature is the appearance of the keyword virtual in front of the destructor prototoype.  We will learn about the virtual modifier later, but for now we simply state that for any class that might be the base for some future derived class(es), one should declare that the destructor be virtual in this manner.  It will not affect any of your other coding.

We give a short main() that tests the limited functionality of StackNode.  Be sure that you understand these fundamental "moves" we are making.  If you do, then the rest should come easily.

// main method ---------------------------------------
int main()
{
  StackNode node1, node2;

  // one way to use Stack Nodes
  node1.next = &node2;

  // a more common way to use StackNodes
  node2.next = new StackNode;

  for (StackNode *p = &node1; p != NULL; p = p->next)
    p->show();
  cout << endl;
}

Here is the output:

See how we linked-up one node with the next?  Also, each node has no unique data in it, so its show() method will print out the same boring message:  (generic node).

By the way, it is okay that our next member is public.  The client will never access this class directly, so that public member will not have any meaning. This makes the data more accessible to the Stack class in a future section. Other classes that use StackNode objects will have these members declared private, so that will be a firewall for the deeply buried next member.

This is a rough idea of how we can use the StackNode to build a larger stack.  In fact, let's get to the stack next.