The LIFO Stack - A Gentle Guide
Written by Harry Fairhead   
Thursday, 21 March 2019
Article Index
The LIFO Stack - A Gentle Guide
Last In First Out
The Function Stack
RPN

Reverse Polish -RPN

This stack operator algorithm is well known and there are lots of variations on it. It also gives rise to the once very well-known Reverse Polish (RP) notation.

If you write operator expressions so that each operator acts on the two items to its left then the expression can be evaluated using an even simpler stack algorithm.

For example, in RP the expression 2+3*4 would be written 2, 3,4*,+ and it can be evaluated simply by scanning from left to right and pushing values on the stack.

Each time you hit an operator you pop the top two items from the stack, apply the operator and push the result back on the stack.

When you get to the end of the RP expression the result is on the top of the stack.

Try it and you will discover it works. In fact you can use a stack to convert standard operator, known as infix, expressions to RP.

Back in the days when hardware was more expensive it was thought to be a good idea to get people to work directly in RP. You could and still can buy calculators that work in RP notation.

To add 2 and 3 you enter 2, then 3 and press the plus button.

Burroughs even built a mainframe computer that didn’t have any other type of working memory than a stack. Everything it did was effectively in RP notation applied to the central stack. The stack machine architecture was simple but not fast enough to compete with more general architectures.

However the stack approach to computing hasn't completely died a death. For example, the difference between the usual Java Virtual Machine - JVM and the one used in Android - Dalvik is the use of a stack. The standard JVM is  register based machine but this is too expensive and power hungry for a mobile device hence the Dalvik VM is a stack oriented VM.

Forth

Perhaps the longest standing overuse of the stack approach was, and is, the language Forth and its many derivatives.

It turns out that with a little effort you can build an entire programming language that can be written down as operators in RP notation.

Of course making it work is just a matter of using a stack to push operators and operands onto.This makes it easy to implement but arguably difficult to use.

However the fun that people had thinking in RP is such that they became really good at it!

The fascination for this sort of language is so great that you still find it in use in niche environments particularly where hardware is limited and it has its enthusiast following.

The LIFO stack is a wonderful invention but it isn’t the only thing computer science has to offer us as a practical tool!

If all you know is the LIFO stack then everything looks like a pop or push.

Related Articles

Introduction to data structures

Stack architecture demystified

Reverse Polish Notation - RPN

Brackets are Trees

Javascript data structures - Stacks

 

What Programmers Know

knowcover

Contents

  1. The Computer - What's The Big Idea?
  2. The Memory Principle - Computer Memory and Pigeonholes
  3. Principles of Execution - The CPU
  4. The Essence Of Programming
  5. Variables - Scope, Lifetime And More
  6. Binary Arithmetic
  7. Hexadecimal
  8. Binary - Negative Numbers
  9. Floating Point Numbers
  10. Inside the Computer - Addressing
  11. The Mod Function
  12. Recursion
  13. The Lost Art Of The Storage Mapping Function *
  14. Hashing - The Greatest Idea In Programming
  15. XOR - The Magic Swap
  16. Programmer's Introduction to XML
  17. From Data To Objects*
  18. What Exactly Is A First Class Function - And Why You Should Care*
  19. Stacks And Trees
  20. The LIFO Stack - A Gentle Guide*
  21. Data Structures - Trees
  22. Inside Random Numbers
  23. The Monte Carlo Method
  24. Cache Memory And The Caching Principle
  25. Data Compression The Dictionary Way
  26. Dates Are Difficult
  27. Magic of Merging
  28. Power of Operators
  29. The Heart Of A Compiler
  30. The Fundamentals of Pointers
  31. Public Key Encryption
  32. Quick Median
  33. Functional And Dysfunctional Programming*

* Recently revised

appC

 



 

Comments




or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

Banner


Quick Median

You have probably heard of Quicksort but what about Quick Median? This is another of the many partitioning algorithms that work in clever ways to do things faster. Quick Median is a useful and  i [ ... ]



Programmer's Introduction to XML

XML is a general purpose markup language that can be used to control the structure of data. Despite the fact that many prefer the simplicity of JSON, it still has many advantages. What makes it so goo [ ... ]


Other Articles

 

<ASIN:B000TDRHG8>

<ASIN:B00004TFL6>



Last Updated ( Thursday, 21 March 2019 )