Stacks, Queues & Heaps
In short: three answers to "what comes out next?" A stack always
hands back the item added most recently (LIFO) — a plain Python list
already is one, via append/pop. A queue always hands back the item
added least recently (FIFO) — don't use a list for this (pop(0) has
to shift everything left); use collections.deque, built so both ends are
equally cheap. A heap ignores insertion order completely and always
hands back the smallest item — heapq turns a plain list into one.
Three containers, three rules for what "next" means. The DSA course proves
the complexity of each; this is which tool fits which job.
Undo in a text editor
Every "undo" button is a stack: the most recent action is always the one to reverse first, not the oldest one.
append and pop (with no argument) both work on the same end — the
end of the list — which is exactly what makes a plain list a perfectly good
stack. The mistake people make is reaching for pop(0) instead, thinking
"oldest edit first" is what undo should mean. It isn't: undo always reverses
the most recent change, which is pop() with no index, reading from the
end where everything was pushed in the first place.
Ticket counter queue
A ticket counter serves whoever's been waiting longest — first in, first
out, the opposite rule from undo. list.pop(0) gives the right answer,
but it's the wrong tool:
queue = [1, 2, 3, 4, 5]
served = queue.pop(0)
print(served, queue)The mistake here isn't wrong output — it's a silently expensive habit. A
list's front is as costly to pop from as its front was to insert into, for
the same shifting reason as the playlist in the last lesson.
collections.deque is a list-like container built so both ends are
cheap, with no shifting:
Same result, and it stays cheap no matter how long the line at the counter gets — a deque is the right tool the moment "remove from the front" is a real, repeated operation rather than a one-off.
Patient triage at a clinic
A clinic doesn't see patients in arrival order — the most urgent case goes first, however late they walked in. That's not a queue, it's a heap: it ignores arrival order completely and only ever hands back the current smallest priority number.
heapq works directly on a plain list — heappush/heappop keep it
organised internally so the smallest item is always reachable in O(log n),
without ever fully sorting the rest. The mistake people make is building
the list by hand and expecting heappop to still find the smallest:
Run it — no crash, but the sprained ankle gets called before the chest pain. Heapify the list before popping from it.
heapq.heappop trusts that its input is already heap-ordered — it never
checks. Build a list by hand (append, or a literal) and the heap invariant
is just whatever order you happened to write it in; heapq.heapify(lst)
rearranges an existing list into real heap order in place before you start
popping from it.
Picking between the three
All three answer "what's next?" differently, and mixing them up is a design
bug, not a syntax error — the code runs fine either way, it just serves the
wrong item. Ask what "next" is supposed to mean for the real job: the most
recent thing (undo, a browser tab's back history) is a stack; the thing
that's been waiting longest (a ticket counter, a print queue) is a queue;
whatever currently matters most regardless of arrival order (triage, a
scheduler's next job) is a heap. list already gives you a stack for free;
reach for collections.deque the moment the front of a queue gets touched
repeatedly, and for heapq the moment "next" stops being about arrival
order at all.
Quick practice
from collections import deque
d = deque([1, 2, 3])
d.appendleft(0)
print(d.pop(), list(d))import heapq
waiting = []
heapq.heappush(waiting, (2, "walk-in"))
heapq.heappush(waiting, (2, "callback"))
heapq.heappush(waiting, (1, "emergency"))
print(heapq.heappop(waiting), end=" ")
print(heapq.heappop(waiting))Run it — it returns "page1", not the last page visited. Fix it to return the most recent page.
🎯 Your turn
Write process_orders(orders). Each order is (priority, name) — lower
number first. Push every order onto a heap, then pop them off in priority
order and return the names:
process_orders([(2, "b"), (1, "a"), (3, "c")])→["a", "b", "c"]process_orders([])→[]
Hint — heapq.heappush(h, (priority, name)) — tuples compare
element-by-element, so the heap sorts by priority automatically. Pop them
all with a while h: loop.
Press ▶ Run, try the Live App chips, then ✓ Check. After that, the practice set below checks balanced brackets with a stack and finds the smallest values with a heap.