The LIFO Stack - A Gentle Guide
Written by Harry Fairhead   
Article Index
The LIFO Stack - A Gentle Guide
LIFO - Last In First Out
The Function Stack
Stacking Operators

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.

 

push1

Push the plates in the order 1,2,3

push2

They sit on the stack so that the last on is the first off


push3

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:

  1. Push 1
  2. Push 2
  3. Push 3

And when you do:

  1. Pop
  2. Pop
  3. 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.

 

trains

Can you shunt a train without a LIFO stack?

<ASIN:1893115232>

<ASIN:0201558025>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.