Stacks

A stack is an interesting data structure. The notion that you should have when using one is that of a stack of pancakes. In a stack of pancaked, there are pancakes and the stack itself. You can pop a pancake off the top of the stack, and you can push a pancake on to the top of the stack. Stacks are fun, because they fit into the C++ notion of classes quite well, as well as demonstrating a good use of inheritance.

We will now look at two extended examples of stacks. The important thing to remember is that a stack is just a datastructure, there are many ways it cam be implemented, with an array, or pointers as we will do it. When writing one for yourself, just think about how you are storing the data, and what each operation does. The first kind of stack that we will look at does no memory management. It relies on you to do all of the new and deleting. The second one will do all of the memory management for you. You should pick one and stick with it. To have your users have to delete things that you new, or delete things that they have newed can lead to some serious consequences.

The first element of a stack is the pancakes. We will call each individual pancake on our stack a node. The following is the definition of our node, it is the same for both types of stacks that we will examine.

The node has some data (like how it tastes, but it could be anything depending on your purposes), and a pointer to another node. This other node is the pancake that the current pancake is sitting on top of. This means that if you are looking at the top one, you can getNext to find out which pancake is under it. In order for this to work, the constructor will need to know which pancake is under it. A default constructor assumes that there is no pancake under it. Then the next is set to NULL;

Finally we have the stack class:

Push puts a node that it was passed on the top of the stack. In order to do that it needs to make a new node and tell that node that it is on top of the old top, and then change top. Simmilarly for pop, it stores the old top, finds out what is under it, makes that the new top, and deletes the old top while returning its value (for convience). }