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.

What Programmers Know

Contents

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

* Recently revised

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 retrieves 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.