Stacks
Understand the LIFO principle that makes stacks useful for call tracking, undo history, expression evaluation, and bracket matching.
- Define a stack and explain the LIFO (last-in, first-out) principle
- Identify real-world patterns that a stack models naturally
- Implement a stack using a Python list with append and pop
A stack is a sequence where you can only add or remove from one end — the top. The last thing you push on is the first thing you get back when you pop. That ordering is called LIFO: last in, first out.
The name comes from a physical stack of plates. You place plates on top and take them from the top. You cannot grab a plate from the middle without disturbing everything above it. The same constraint applies in software — and it is exactly the right constraint for several important problems.
The call stack: the canonical example
You already use a stack constantly without naming it. Every time Python calls a function, it pushes a stack frame onto the call stack. The frame stores the function's local variables and the return address — the point in the calling function where execution should resume when this call finishes.
When factorial(3) calls factorial(2), which calls factorial(1), three
frames stack up. The most recent call is at the top. As each returns, its frame
is popped and execution resumes in the frame below. The call stack grows on call,
shrinks on return — pure LIFO.
This is also why RecursionError: maximum recursion depth exceeded mentions a
depth: the call stack has a finite size. When recursion never hits a base case,
frames pile up until the stack is full.
Other stack patterns
Undo and redo. Every text editor with undo maintains a stack of changes. Each edit pushes a new entry. Ctrl-Z pops the top entry and reverses it. Redo pushes the reversed change onto a second stack. LIFO maps perfectly to "reverse the most recent action."
Bracket matching. To check {[()]} is balanced, scan left to right. Push
each opening bracket. When you hit a closing bracket, pop the stack and check
that the popped bracket is the matching opener. If the stack is empty at the end,
all brackets matched. Any mismatch or leftover entry means unbalanced.
Expression evaluation. Reverse Polish Notation (RPN) pushes operands onto a
stack. When an operator is encountered, pop two operands, apply the operator, and
push the result. 3 4 + 2 * becomes (3 + 4) * 2 = 14.
Python implementation
Python lists support stack operations directly:
stack = []
stack.append(10) # push → [10]
stack.append(20) # push → [10, 20]
stack.append(30) # push → [10, 20, 30]
top = stack.pop() # pop → 30, stack is [10, 20]
top = stack.pop() # pop → 20, stack is [10]
# Peek without removing:
if stack:
print(stack[-1]) # 10Both append() and pop() (at the end) are O(1) amortised. You never need a
separate class — a list is a stack. The naming convention stack.append() and
stack.pop() is the contract; the implementation is the built-in list.
Never use list.pop(0) to simulate a stack. It removes from the front, which
requires shifting every remaining element — O(n). A stack's pop is always from
the end (top), which is O(1). Confusing these two is a common source of
accidental quadratic behaviour.
Recognising stack problems
Ask: "do I need the most recently seen thing?" If yes, reach for a stack. Bracket matching needs the most recently opened bracket. Undo needs the most recent change. DFS (depth-first search) explores the most recently discovered node first. All of these are stacks in disguise.
Where to go next
Next: stacks in practice — implementing is_balanced(s) for bracket
matching and evaluate_rpn(tokens) for reverse Polish notation, both using a
Python list as a stack.