PYTHON / DATA STRUCTURES AND ALGORITHMS
Stacks
Use a Python list as a LIFO stack to match brackets, track pending work, and replace recursion with an explicit loop.
What you will learn
- Push and pop at the end of a list so both operations stay O(1)
- Guard pops with `if stack:` instead of catching IndexError after the fact
- Turn a recursive walk into a while loop driven by an explicit stack
- Push children in reverse when you want them processed in natural order
Understanding Stacks
A stack exposes exactly one reachable element: the one added most recently. In Python you do not need a class for this, because a list already gives you the two operations at the cheap end: `append` puts an item on top and `pop()` with no argument removes and returns it. Both are O(1) because nothing after them has to move; `pop(0)` or `insert(0, x)` would shift every remaining element and turn each operation into O(n).
The reason a stack keeps showing up is that many problems have the shape "the newest unfinished thing must be finished first". A closing bracket has to match the most recent unclosed opener, not the first one. An undo has to reverse the last edit. A depth-first walk has to finish the node it just descended into before going back up. In each case the stack is a record of obligations, and popping is how you discharge the one that came due.
Python's own interpreter runs on a stack of frames, which is why deep recursion raises `RecursionError` around a thousand frames deep. Any recursive function is therefore rewritable as a loop plus a list you push onto yourself, and the rewrite is bounded only by memory. The one thing that changes is order: recursion visits children in the order you write them, while a stack pops them in reverse, so you push them reversed to get the same traversal.
pairs = {")": "(", "]": "[", "}": "{"}
def balanced(text):
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
for s in ["(a[b]{c})", "(a[b)]", "((", "))"]:
print(repr(s), balanced(s))A stack makes only the most recently pushed item reachable, which is exactly what you want when the newest pending obligation must be resolved before older ones.
Worked examples
Replacing recursion with an explicit stack
Flattens a nested list without recursion, and shows how push order decides output order.
def flatten(nested, rev=True):
out = []
stack = [nested]
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(reversed(item) if rev else item)
else:
out.append(item)
return out
data = [1, [2, [3, 4], 5], 6]
print(flatten(data))
print(flatten(data, rev=False))Example explained
Line 1`stack = [nested]` seeds the stack with one pending item, the whole structure.
Line 2`stack.pop()` always takes the deepest-most-recent pending item, which is what makes the walk depth-first.
Line 3`stack.extend(reversed(item))` pushes the last child first, so the first child ends up on top and comes out first.
Line 4Pushing without `reversed` produces the exact reverse, because a stack undoes insertion order.
Popping an empty stack
Shows the error `pop()` raises when the stack is empty and the idiomatic guard against it.
stack = [3]
print(stack.pop())
try:
stack.pop()
except IndexError as e:
print("IndexError:", e)
print(stack.pop() if stack else "empty")Example explained
Line 1`stack.pop()` returns the removed value, so the item is gone after you read it.
Line 2A second `pop()` on the now-empty list raises `IndexError: pop from empty list`.
Line 3`if stack` is the standard emptiness test: a list is falsy exactly when its length is zero.
Line 4Use `stack[-1]` when you only want to look at the top without removing it.
Tracking the minimum in O(1)
A second parallel stack keeps the minimum of the current contents available without scanning.
stack = []
mins = []
def push(x):
stack.append(x)
mins.append(x if not mins else min(x, mins[-1]))
def pop():
mins.pop()
return stack.pop()
for x in (5, 3, 7, 1):
push(x)
print("push", x, "-> min", mins[-1])
print("pop", pop(), "-> min", mins[-1])
print("pop", pop(), "-> min", mins[-1])Example explained
Line 1`mins[-1]` always holds the minimum of everything currently in `stack`.
Line 2`min(x, mins[-1])` stores a running minimum per level instead of recomputing it later.
Line 3The two stacks are popped together, so `mins` shrinks back to the value that was correct before the push.
Line 4This works only because pops undo pushes in exact reverse order.
Undo history
Applies text edits and rolls them back by popping recorded inverse operations.
text = "cat"
history = []
def apply(op, arg):
global text
history.append((text,))
text = text + arg if op == "append" else text.upper()
apply("append", "s")
apply("upper", "")
print(text)
while history:
text = history.pop()[0]
print("undo ->", text)Example explained
Line 1Each `apply` pushes the previous state before mutating, so the stack grows with the edits.
Line 2`history.pop()` returns the most recent snapshot first, giving reverse-chronological undo for free.
Line 3`while history:` drains the stack; when it is empty there is nothing left to undo.
Important notes
`list` is the right stack in Python; `collections.deque` only helps if you also need cheap access at the other end.
Pushing a mutable object stores a reference, not a copy, so mutating it afterwards changes what you later pop.
Common mistakes
Using `stack.pop(0)` and `stack.insert(0, x)`, which is still LIFO-correct at the wrong end and makes every operation O(n), so a loop over n items becomes quadratic.
Calling `stack.pop()` twice when only one value is needed, for example comparing `stack.pop() != x` and then using `stack.pop()` again; the second call removes an unrelated element or raises IndexError.
Forgetting that a bracket matcher must also check `not stack` at the end, so an input like `"(("` is wrongly reported as balanced.
Try it yourself
Change, predict, then run
Write `undo_moves(moves)` that processes a list of strings where a normal string is pushed and "undo" removes the last pushed string, returning the remaining list; check that `["a", "b", "undo", "c"]` gives `["a", "c"]` and that a leading "undo" does not crash.
Open the Python workspaceCheck your understanding
An iterative depth-first walk pushes a node's children onto a stack in left-to-right order, then pops one per iteration. In what order are the children visited?
- Right to left, because the last child pushed is on top
- Left to right, because pushes preserve insertion order
- Left to right, because pop() reads from the front of the list
- Unspecified, because list ordering depends on the number of elements
Show answer
A stack returns items in reverse of the order they went in, so the rightmost child pushed is popped first. "Left to right" would be true of a queue, which pops from the opposite end; with `list.pop()` you must push children reversed to get left-to-right visiting.