5. Linked Implementation Of Stacks

Let us now consider how we can use node-and-arc diagrams to design the algorithms for a particular data structure. We'll look at stacks, since they are simple and you are familiar with them.

Consider the stack of integers S = 29,7,11 (29 is the top, 11 the bottom). The logical order of the values in a stack is very clear; first comes the top element, next comes the element just below the top element, etc. In a linked implementation, this relationship will be explicitly represented: the memory cell containing the top element will also contain a pointer to the second element, the memory cell containing the second element will contain a pointer to the third element, etc. What about the memory cell containing the bottom element?

So this is our basic implementation:

There will be one memory cell for each element in the stack; in this memory cell we need to store two things: the value of the element, which is an integer in this example but could be anything, and a pointer to the memory cell of the next element.

Having decided this, we can now draw the node-and-arc diagram representing S.

What about S itself? It will be a variable in our program, explicitly declared. So it will be a box. What is in the box? Well, one thing for sure, we need to store a pointer to the top element. In addition, we could store anything else we like.

In terms of actually coding this in C, some things are already settled.

The memory cells for stack elements contain two pieces of information, a value and a `next' pointer, therefore they will have to be records/structures.
S is probably a different type than the `elements' in the stack, because it has no associated value, just a pointer to the top stack element.

Knowing these two things, it is now easy to write the TOP operation - all it has to do is follow the pointer from S and look up the value stored in that memory cell.

An important question is, how will we represent the EMPTY stack? There are actually several possibilities.

In S we could store the number of elements that it contains, in which case the empty stack would be represented by setting this value to zero.
Or we could have a boolean (logical) variable telling us whether or not S is empty.
The simplest solution is to set S's TOP pointer to NULL when S is empty (of course we are sure it will be non-NULL when S is non-empty).

Having decided this, it is now very straightforward to write the code for the two operations CREATE_STACK and IS_EMPTY.

The remaining operations - POP, PUSH, and DESTROY_STACK - are a little more complex because they actually involve allocating or freeing of memory. I will show you how to design one of them: the method of design I use is completely general and I recommend that you use it for designing all operations on all the data structures you ever implement.

This design method works exclusively with the node-and-arc diagrams. Yet it works out the step-by-step details of how to implement the operation, so all that remains to be done is to translate each step into C code (each step typically needs one or two simple lines of code, so this process is almost 100% mechanical).

All you do is draw a before and after picture - two node-and-arc diagrams, one showing the values passed to the operation before it is executed, the other showing the values created/changed by the operation after it has finished. For example, consider the POP operation.

A typical input to the POP operation is the stack S (as above):

That is our before diagram. Here is what S will look like after the POP:

That is our after diagram. All we have to do, to design the inner workings of the POP operation, is to list all the differences between the before and after diagrams. How many can you see?

The memory cell containing 29 is gone.
In S, the TOP pointer is pointing at a different cell.

Now, let us work out exactly what needs to be done to achieve these 2 changes.

Change 1

What operation must be used to return the cell containing 29? Answer: RETURN_MEMORY.
What information do we need to pass to RETURN_MEMORY? Answer: a pointer to the cell we want to get rid of.
Where can we get this information? We must look for it in the before diagram, since that is our starting point. Answer: The TOP pointer in S.

So, pseudocode for change 1 consists of the following two steps:

(step 1a) Get_Rid_of_This = S's TOP pointer
(step 1b) RETURN_MEMORY(Get_Rid_of_This)

Change 2

What operation can be used to change the value of S's top pointer? Answer: the assignment operation
What information do we need for this operation? Answer: a pointer to the cell we want S to point at.
Where (in the before diagram) can we get this information? Answer: It is in `next' pointer of the cell that is deleted by change 1. As we decided above, S's TOP pointer gives us a pointer to this cell.

So, pseudocode for change 2 consists of the following two steps:

(step 2a) Top_Cell = dereference (follow) S's TOP pointer
(step 2b) S's Top Pointer = the next pointer in Top_Cell

I hope you see that it is extremely simple now to translate this into any programming language you like. But, we are not actually finished yet. We said that S was a typical input to POP. But the POP operation must work for all inputs, not just typical ones. Can you think of any input for which the steps we've defined will not work?

Well, there is one case that always deserves close scrutiny, because it often requires special processing. What happens if there is only one element in S, and we POP it off making S empty. This might be different than a typical case, because, an empty stack does not `look the same' as a non-empty one (partly this depends on exactly how we choose to represent the empty stack). Let's see:

After doing steps 1a and 2a, we will have:

where Top_Cell is a copy of the cell S is currently pointing to.

Everything looks like it will work. Step 1b will free up the cell, and the `next' pointer in Top_Cell, which is destined to become S's TOP pointer (by step 2b) is NULL, as it should be. So, these four steps, in this order, will work on all valid inputs. However, sometimes this is not the case; sometimes different inputs require different processing, and you have to do before/after analysis for each of the different kinds of inputs.

The very last thing we need to consider before turning all this into code is: in what order should these steps be done in?

Obviously we must not delete the TOP cell (step 1b) until we have grabbed the pointer in it that we need (for change 2). But rather than thinking too hard about these intricate interactions, here is a very easy, and completely general-purpose way to sequence these operations.

The trick is to do all the steps without changing the before diagram; but to store things you need in temporary variables, e.g. Get_Rid_of_This, Top_Cell, etc.

Then when you have collected into temporary variables all the information you need, you can make the changes to the data structure in any order you like. Here is how this strategy works on the four steps needed to implement the POP operation. Steps 1b and 2b are the ones that actually change the given data structure S, so they are done last (in any order you like). Step 2a and 1a are done first, in either order. After doing 1a and 2a to our original `before' diagram we get:

And now we can finish off with the final steps - 1b and 2b - in either order.

But they key idea in this strategy - the main thing to remember - is the idea of using the differences between before and after diagrams to define what steps are needed to implement the operation. If you do this, you will have no trouble implementing PUSH, DESTROY_STACK, or any other operation on any linked data structure.

One last thing to remember: these procedures can call each other. This can be very useful. For example, you will find it very easy to write DESTROY_STACK if you first write IS_EMPTY and POP and then use them in the implementation of of DESTROY_STACK.