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

• What operations can occur on a stack
• How each element of the stack will be stored.

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 -

• Where the top of the stack is
• Where the next element of the stack can be found.

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 -

1. Create the new node
2. Copy the top link into the previous link of the new node
3. Set the top link to be the new node.

The pop operation is even simpler

1. Find the node pointed to by the top link
2. Copy the previous link and make it become the new top