|The LIFO Stack - A Gentle Guide|
|Written by Harry Fairhead|
|Wednesday, 10 October 2012|
Page 1 of 2
The stack is a very simple idea. It is a data structure that has only two simple operations and yet not only is it powerful, it is at the heart of modern computing, both theory and practice. Let's find out more about it.
There are few more wonderfully simple yet powerful ideas in computing than the stack.
I don't know when the stack was invented but it could be an idea that predates the computer. There were and are lots of mechanical examples of a stack that make it a relatively obvious concept. However it is one thing just to notice that there are such things in nature and quite another to put them to good use. When ever the stack was first invented it certainly didn't reach its true potential until the computer came along.
So let’s take a close look at the stack - where it originates, its basic operation and what it can do for us.
Push and Pop
A stack has two fundamental operations - Push and Pop.
The Push operation stores something on the top of the stack and the Pop operation retrives something from the top of the stack.
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 but things are added to the stack at the top and taken from the top – the push and pop operations are the same.
And this is the key idea about stack storage - you can only access and work with the top of the stack.
The Hardware Stack
The plate stacker is a really good way to imagine how a stack operates and what you can do with it but in software it looks a little different - no plates for example.
We have already encountered the idea of a stack while looking at the fundamental design of the CPU in another article.
The “stack pointer” is a hardware register that holds the address of a memory location.
As you would expect there are only two basic 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 it has hidden depths.
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. In other words some add to the stack pointer on a pop and some subtract.
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.
These differences are minor and don't alter the basic operation of the stack. but they can be confusing.
Last In First Out
The key part of the behavior of a stack, due to the nature of push and pop, is the “Last In First Out”, or LIFO, principle. Indeed this is so fundamental that a stack is often called a LIFO stack to distinguish it from lesser varieties such as the First In First Out, or FIFO stack.
If you think about any of the physical models of a LIFO stack you can begin to see why it is LIFO by nature.
If you take a set of three plates and number them, one, two and three – don’t try this at home – and push them onto a LIFO stack in this order, what order do they pop off?
The answer is obviously three, two and finally one.
Push the plates in the order 1,2,3
They sit on the stack so that the last on is the first off
And when they are popped they are in the order 3,2,1
It is all too easy to miss how important this is.
And when you do:
you get back 3,2,1, i.e. the sequence reversed.
It is this strange order reversing property of a stack that makes it so valuable in so many situations.
The Shunting Yard Algorithm
Suppose you have a train of goods wagons and a single siding for shunting (switching) .
How can you reverse the order of the trucks?
Now that you know about LIFO stacks and their remarkable order reversing property this question should be easy.
You push each truck into the siding in the order 1,2,3 and then pop them out of the siding in the order 3,2,1.
Can you shunt a train without a LIFO stack?
|Last Updated ( Thursday, 18 May 2017 )|