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.

You do:

Push 1
Push 2
Push 3

And when you do:

Pop
Pop
Pop

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?

<ASIN:1893115232>

<ASIN:0201558025>

<ASIN:0763741493>

<ASIN:0071460519>

<ASIN:0767917073>