Last tray on, first tray off
Stacks as Tray Piles
The analogy
Clean trays stack up in the cafeteria. You put a tray on top, and the next person takes the top one — the tray at the bottom has been there since breakfast. You only ever touch the top. That is a stack.
Visualizer
The tray pile
step 1 / 14bottom
An empty tray pile. There is exactly one place you can reach: the top.empty
📖 In depth — the full reference
Stack operations — all of them
| operation | meaning | cost |
|---|---|---|
| push(x) | put x on top | O(1) |
| pop() | remove and return the top | O(1) |
| peek / top | look at the top without removing | O(1) |
| isEmpty | anything left? | O(1) |
| search / access by depth | NOT a stack operation | O(n) — if you need it, you wanted a different structure |
Where stacks hide
- The call stack (Module 0's vending machines) — every function call pushes a frame, every return pops one. "Stack overflow" is this stack hitting its ceiling.
- Undo/redo: two stacks — undo pops from history and pushes onto redo.
- Matching brackets/tags: push every opener, pop on each closer, and the pairs match iff the stack ends empty.
- DFS (Module 3) is a stack-driven walk; recursion is DFS borrowing the call stack.
Python: a list IS the stack
stack = [] stack.append(1) # push — O(1) amortized stack.append(2) top = stack[-1] # peek — O(1) x = stack.pop() # pop — O(1), returns 2 if not stack: ... # isEmpty — empty list is falsy # Never use insert(0)/pop(0) as a stack — wrong end, O(n)
stack = [] stack.append(4) # push stack.append(9) stack.append(2) stack.pop() # 2 — last in, first out stack[-1] # 9 — peek # a plain list IS the idiomatic Python stack
Check yourself
Push 1, 2, 3 then pop. What comes out?
Practice — write it yourself
reverse_with_stack(arr) pushes everything onto a stack (append), then pops it all — returning the reversed list. LIFO doing what LIFO does.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser