There are few more wonderfully simple yet powerful ideas in computing than the stack.

I don’t know if Babbage ever thought of this particular idea – there were certainly mechanical examples of it in existence – but even if he did, it doesn’t really display its true glory until it is fully developed.

So let’s take a look at the stack.

Push and Pop

In fact we have already encountered the idea of a stack while looking at the fundamental design of the CPU. The “stack pointer” is a hardware register that holds the address of a memory location.

There are only two operations on a stack pointer, push and pop. The push operation stores the contents of another register on the stack and then moves the stack pointer on by one. The pop, sometimes called “pull”, operation just reverses the push operation – it moves the pointer back by one and then retrieves the value from the stack.

This is all there is to a stack, it is entirely simple and yet, as we shall see, very powerful.

There are lots of variations on how a stack can be implemented. Some stacks are made so that they start at a low address and grow upward. Some start high and grow down. Others change the stack pointer before storing a value; others change it after storing a value. The difference being that in the former case the stack pointer always points to the current item on the top of the stack and in the latter it points to the next free stack location.

If you want a physical representation of a stack all you have to think of is a self-service café – complete with a spring-loaded plate delivery system. The clean plates are pushed on top of the stack of plates against a spring that keeps the top plate at the same level.

Push a plate

When a customer comes along and takes a plate another one pops to the top to replace it.

Pop a plate

You can see a similar mechanism in action in one of those coin storage devices where you push a coin in at the top and take one out from the same slot.

These mechanical devices share that same basic principle of operation of a stack. They may not have the same internal workings, there is no stack pointer for example, but things are added to the stack at the top and taken from the top – the push and pop operations are the same.

<ASIN:0763741493>

<ASIN:0071460519>

<ASIN:0767917073>