Stacks | |
A stack is a dynamic data structure where the first element into the stack is always the last to leave (FILO). A stack can be seen as a stack of books. When you remove a book from the stack it will always be at the top. Let us now look at how we could code a stack. First of all we need to know
The only two operations you need are to be adding an element to the stack (Push) or remove one (pop). The next thing you need to consider is how you are going to store elements within the list. There are two parts to this storage -
Each element of the stack, which we call nodes from now on, has a link to the previous node. With all of this information we can now define pseudo code on how to push and pop nodes to the stack. The diagram on the left shows the situation before while the one on the right shows the situation after a push occurs. The important thing to notice is what happens to the links. The node added, Sally, will initially have no previous set, so it will be NULL. What happens then is the link to the top, which is Fred, is copied into the new nodes previous. The top link then becomes the node you have just added. So the sequence of events are -
The pop operation is even simpler
|