The stack: push and pop

The LIFO principle

A stack is a data structure where the last element added is always the first to come out. This principle is called LIFO, for « Last In, First Out ». Picture a stack of plates: you always put the new plate on top, and when you take one off, you necessarily take the top one, never the one at the bottom.

The two basic operations

A stack offers only two essential operations:

• push: add an element to the top of the stack;
• pop: remove and return the element at the top of the stack.

A peek operation is often added, which looks at the top element without removing it, along with an is_empty test.

Diagram: how a stack evolves

Empty stack:                []

push(3)     ->               [3]
push(7)     ->               [3, 7]
push(9)     ->               [3, 7, 9]        (9 is on top)

pop() -> 9                    [3, 7]          (9 comes out first, it was the last one in)
pop() -> 7                    [3]

vertical view:
   +---+
   | 9 |   (top, last to arrive)
   +---+
   | 7 |
   +---+
   | 3 |   (bottom, first to arrive)
   +---+

Guaranteed reverse order

What makes a stack useful is that the output order is always the exact reverse of the input order. If you push 3, then 7, then 9, you are certain to get back 9 first, then 7, then 3 last.

Common pitfall

Do not confuse popping and reading the top: popping actually removes the element (the stack shrinks), whereas simply looking at the top (peek) changes nothing. Forgetting to check that a stack is not empty before popping is also a frequent mistake: it causes a runtime error, since there is nothing to remove.