Stacks & Play History
Every track you play in Tunebox lands on top of the one before it. Press back and the app lifts the top one off, which is always the most recent track and never the first. A structure you may only touch at the top is a stack. That one restriction is what makes undo, bracket matching and even function calls work.
Last in, first out
A stack has three operations. Push puts an item on top, pop takes the top item off, and peek looks at the top without removing it. The rule behind all three is LIFO: last in, first out.
A Python list is already a stack, as long as you only ever use its end:
stack = []
for track in ["A", "B", "C"]:
stack.append(track)
stack.pop()
stack.append("D")
print(stack[-1], len(stack))❓ Cross-question — "Why the end of the list and not the front?" Because the end is free.
appendandpop()only touch the last slot, so they're O(1).insert(0, x)andpop(0)shift every other item, which is the O(n) cost from the linked-list lesson. You'd get the same LIFO behaviour at a very different speed.
Coming from Java/JS: JS arrays work the same way with
pushandpop. In Java, skip the oldStackclass (it's built on the synchronisedVector) and useArrayDequewithpush,popandpeek.
Peek, and the empty stack
Pressing back with no history is the classic stack bug:
history = ["Intro"]
history.pop()
print(history.pop())So guard every pop and peek on a stack that can run empty:
Matching brackets
People type Tunebox's smart-playlist rules by hand, for example
(genre = jazz or [year < 1970]), so the app checks the brackets before running
anything. Every closing bracket must match the most recent opening bracket
that is still open, and "most recent" is exactly what a stack gives you. Push
each opener. On a closer, pop and compare:
Step through the failing case and watch what's on the stack when ) arrives:
Evaluating an expression
Calculators and virtual machines evaluate postfix notation, also called Reverse
Polish notation, where the operator comes after its operands: 3 4 + 2 * means
(3 + 4) * 2. You don't need brackets or precedence rules, just a stack. Push each
number. When an operator arrives, pop two numbers, apply the operator, and push
the result:
Most bugs here come from popping the two operands in the wrong order:
`10 4 -` means 10 - 4, so this should print 6. It prints -6.
Monotonic stacks: the next greater element
For each day's play count, Tunebox's trends page asks: which later count beat it first? The brute-force answer checks every later day for every day, which is O(n²). A monotonic stack does it in one pass. The stack holds days still waiting for a bigger number, and when a big day arrives it answers every smaller day on top of the stack:
It stores indices rather than counts, so the answer can be written back to the
right position. Each index is pushed once and popped at most once, so the inner
while does O(n) work in total and the whole function is O(n), not O(n²).
nums = [5, 3, 4, 6, 2]
stack = []
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
stack.pop()
stack.append(i)
print([nums[i] for i in stack])The call stack: why recursion is a stack
Python keeps a stack of its own. Calling a function pushes a frame holding its local variables and where to resume, and returning pops that frame. So the most recently called function always finishes first:
That means you can rewrite any recursion with a stack of your own. This matters
when the input is deep enough to hit Python's limit of about 1000 frames, which
raises RecursionError. Here the explicit version counts the tracks in playlists
nested inside playlists:
❓ Cross-question — "Is the explicit version faster?" Not in any way that matters, since both are O(n). What it gives you is control: there's no depth limit, and you can pause, inspect or reorder the work still waiting. Depth-first search on a graph (Section 5) is this same loop.
What it costs
| operation | list used as a stack |
|---|---|
push: append(x) |
O(1) amortized |
pop: pop() |
O(1) |
peek: stack[-1] |
O(1) |
is it empty? if stack: |
O(1) |
| find an item | O(n) |
push or pop at the front: insert(0, x) / pop(0) |
O(n), so don't |
Idioms & real-world patterns
while stack:empties a stack, andstack[-1] if stack else Nonepeeks safely.- Push indices when the answer goes back into a position, as
next_greaterdoes. - Push tuples to carry extra state, such as
stack.append((folder, depth)). - Undo and redo use two stacks. Undo pops from one and pushes onto the other, and any new action clears the redo stack.
- Where stacks live: browser back buttons, editor undo, compilers and JSON parsers matching brackets, the CPython and JVM interpreters (both are stack machines), and depth-first search.
⚡ Advanced — why append is only amortized O(1)
A list keeps some spare slots. When they run out, Python allocates a bigger block and copies every item across, which is an O(n) step. The block grows by a fixed proportion each time, so those copies happen rarely enough that n appends cost O(n) in total, or O(1) each on average:
⚡ Advanced — a stack that knows its minimum
Say Tunebox wants the quietest track in the history at any moment, in O(1). Keep a second stack whose entries are the minimum so far, and push and pop both stacks together:
🎯 Your turn
Build undo_history(actions), Tunebox's play history. Replay each action on a stack:
["play", title]pushestitle.["back"]pops the most recent track, and does nothing if the history is empty.
Return the history that's left, oldest first:
undo_history([["play", "A"], ["play", "B"], ["back"]])→["A"]undo_history([["back"]])→[]
Hint: a list is your stack. Call append on play, and on back call pop() only
if stack:.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅