ADT Stack
By Daniel D'Agostino, 14th November 2006
Concept
A stack is simply a pile. It could be a pile of books, a pile of paper, a pile of junk... a pile of anything, really. This is why we call it an Abstract Data Type (ADT) - it is a data structure which works in a uniform way for various different data types. To make it easy to understand, we will consider two particular stacks: a stack of books, and a stack of Pringles.
Consider a stack of books. You cannot take out the book at the bottom without dropping all the rest. You probably saw this being done with tin cans which were stacked on top of each other... some dumbass took out a tin can at the bottom and everything fell over. Anyway, the important thing here is that, in a stack, you can only manipulate the top element. There is no way of accessing other elements without first removing all the other elements on top of it.
Operations
Consider a stack of Pringles. There are two things you can do to the stack.
One operation, which is appropriately associated with Pringles, is to pop (remove) an element off the stack. With Pringles, it gets a bit dangerous though: once you pop, you can't stop.
The other operation is to push (add) elements onto the stack. With Pringles, you normally don't do this.
Other functions
It is possible to use the top element without removing it from the stack. We normally do this by using a pointer to the top of the stack. The image above illustrates this in a rather strange way.
You can also check whether the stack is empty.
Implementation
In this section I will briefly explain, algorithmically (i.e. not using any specific computer language), how a stack data structure is encoded in programming. Such implementation requires the use of pointers. If you don't know how to use pointers, you might still want to read on; the implementation of such a data structure will give you a reason to learn and use pointers.
A stack is a linked list of nodes containing two items: a pointer to the next node, and the actual data. You can think of it as a stack of Pringles where each Pringle has an arrow pointing to the Pringle beneath it.
The only thing the actual stack contains is a pointer to the top node. The bottom element has nothing beneath it, so its pointer is null. Thus we can easily check whether the stack is empty by checking whether the top pointer is null. Thus we have already implemented both 'other functions' described above.
Now, to implement the pop operation, we need to do the following things:
- Store the value of the top element's pointer (so we get a new 'top' node).
- Dispose of the old top element (each programming language has its own way of freeing memory).
- Set the top pointer to point to the address we stored in #1.
To push a new element onto the stack, we just need to set the new element's pointer to point to the current top node, and then set the top pointer to point to the new node.
What's next?
Eat your Pringles. They aren't only good as stacks, you know.