S026 · Stacks & Queues — LIFO/FIFO in Practice

Module M03: Data Structures & Algorithms · Session 26 of 130 · Track: SW 📚

What you'll be able to do after this session

• Explain Stacks & Queues to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S025 — Linked Lists — Singly, Doubly, When They Win

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Stacks & Queues in 100 seconds + walkthrough (NeetCode) — LIFO vs FIFO, when each wins.
• 🎥 Deep dive (30–60 min) · MIT 6.006 — Stacks, Queues, and Amortization — the theory + amortised analysis.
• 🎥 Hands-on demo (10–20 min) · Implementing a stack and queue in Python (NeetCode) — three ways, with runtime trade-offs.
• 📖 Canonical article · Wikipedia — Stack (abstract data type) — the definition and canonical operations.
• 📖 Book chapter / tutorial · Python docs — Using Lists as Stacks and Queues — the Pythonic patterns.
• 📖 Engineering blog · AWS — Designing Event-Driven Architectures — queues at cloud scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Two shapes of order.

A stack is a spring-loaded plate dispenser in a cafeteria: you can only push a plate onto the top or take one from the top. Last In, First Out (LIFO). A queue is the line at the same cafeteria's cashier: first person in line is first to pay. First In, First Out (FIFO).

These sound too simple to matter, but they're everywhere. Every function call in your program is pushed onto a call stack; when the function returns, its frame is popped. The browser back button is a stack. Undo/redo is two stacks. Depth-first search uses a stack (often implicitly via recursion). Breadth-first search uses a queue. Every message broker (Kafka, RabbitMQ, SQS) is a queue with fancy durability guarantees.

The magic property both share: O(1) insert and O(1) remove — as long as you only touch the "right" end. Which end depends on the discipline.

One-sentence gotcha to carry forever: Using a Python list as a queue is a trap — list.pop(0) is O(n) because it shifts every element. Use collections.deque for queues in Python. Same trap exists in Java (ArrayList vs ArrayDeque) and JavaScript (Array.shift() is O(n)).

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Worked example — matching brackets with a stack:

Given "([]{[]})", is it balanced?

Empty stack at end → balanced. Any mismatch or non-empty stack → unbalanced. This is exactly how compilers and JSON parsers detect syntax errors.

Worked example — BFS over a tiny grid with a queue:

Grid:

S . .
. # .
. . E

Start at S (0,0), find shortest path to E (2,2). Use queue [(0,0, dist=0)]. Pop, mark visited, push unvisited neighbours with dist+1. Continue.

Shortest path = 4 steps. FIFO order is what guarantees "first time we see the target, we found it via a shortest path."

When to use which:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# stacks_queues_playground.py
from collections import deque
from time import perf_counter
 
# ---- 1. Stack via Python list ----
stack = []
stack.append(1); stack.append(2); stack.append(3)
print("stack top:", stack[-1], "  pop:", stack.pop(), "  now:", stack)
 
# ---- 2. Queue: the right way (deque) vs the trap (list) ----
n = 100_000
 
dq = deque(range(n))
t0 = perf_counter()
while dq: dq.popleft()
t1 = perf_counter()
 
lst = list(range(n))
t2 = perf_counter()
while lst: lst.pop(0)
t3 = perf_counter()
 
print(f"
deque popleft ({n}): {(t1-t0)*1000:6.1f} ms")
print(f"list.pop(0)  ({n}): {(t3-t2)*1000:6.1f} ms   <-- linear-time trap")
 
# ---- 3. Balanced brackets ----
def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack
 
for s in ["([]{[]})", "([)]", "(((", "", "{{[]}}"]:
    print(f"is_balanced({s!r:12}) = {is_balanced(s)}")
 
# ---- 4. BFS on a small grid ----
def bfs_grid(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    q = deque([(start, 0)])
    visited = {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == end:
            return d
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr,nc) not in visited:
                visited.add((nr,nc))
                q.append(((nr,nc), d+1))
    return -1
 
grid = [
    ["S",".","."],
    [".","#","."],
    [".",".","E"],
]
print("
shortest path S to E:", bfs_grid(grid, (0,0), (2,2)))
 
# ---- 5. Stack-based expression eval (reverse polish notation) ----
def eval_rpn(tokens):
    st = []
    for t in tokens:
        if t in "+-*/":
            b = st.pop(); a = st.pop()
            st.append({"+":a+b,"-":a-b,"*":a*b,"/":int(a/b)}[t])
        else:
            st.append(int(t))
    return st[0]
 
print("RPN 3 4 + 2 *:", eval_rpn(["3","4","+","2","*"]))

Checklist:

1. deque.popleft is 100–1000x faster than list.pop(0) for 100k items.
2. Balanced checks return True, False, False, True, True.
3. BFS returns 4 for the grid.
4. RPN eval returns 14.
5. Try flipping the stack in is_balanced — the check breaks. That's LIFO's whole point.

Try this modification: implement a MinStack class with push, pop, top, and get_min all in O(1). Hint: keep a second stack that at each level stores the minimum of everything below it.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Stacks and queues underpin almost every distributed system:

1. Message queues at cloud scale. SQS (Amazon), Pub/Sub (Google), Kafka (LinkedIn/Confluent), RabbitMQ — all offer FIFO-ish semantics with durability, at-least-once delivery, and consumer groups. The abstraction the application sees is "a queue," but the reality is partitioned logs replicated across data centers. Common gotchas: head-of-line blocking (a stuck message holds up everyone behind it — solved by dead-letter queues), duplicate delivery (network retries mean at-least-once is the default; applications must be idempotent), and ordering guarantees only within a partition (Kafka's per-key order).

2. Call stacks and stack overflow. Every process has a call stack, typically 1-8 MB by default. Deep recursion (parsing a deeply nested JSON, walking a very tall tree) overflows it and crashes the whole thread. In production Python you'll see RecursionError: maximum recursion depth exceeded; in native code, a segfault. Common fix: rewrite recursion as an explicit loop with an explicit stack. This is not a theoretical concern — GraphQL server implementations, JSON parsers, and template engines have all shipped CVEs around adversary-controlled recursion depth.

3. Back-pressure and bounded queues. An unbounded in-memory queue is a memory leak waiting to happen. Every serious system uses bounded queues — when full, the producer must either block, drop, or spill to disk. Netflix's Hystrix (deprecated but instructive) and Resilience4j both provide bulkhead patterns to prevent one runaway producer from OOM-killing the process. The mental model: any queue you don't bound will eventually eat all your memory.

4. Undo/redo & event sourcing. Text editors, Figma, and CAD tools all use a stack pair for undo/redo. Zoom out and event-sourced architectures (Kafka + Debezium, EventStoreDB) treat the whole system as an append-only queue of events; state is derived by replaying the queue. The take-away: stacks and queues are not "algorithmic toys," they're the natural shape of "state as a history."

One incident pattern to memorise: a consumer slows down, its queue grows, memory pressure triggers GC, GC slows everything more, more messages pile up — spiral of death. Monitoring queue depth (and alerting on trend, not just threshold) catches this before it's an outage.

(e) Quiz + exercise · 10 min

1. Distinguish LIFO from FIFO in one sentence and give one algorithm that uses each.
2. Why is using a Python list as a queue a performance trap? What is the fix?
3. Walk through the state of the stack when checking whether "({[]})" is balanced.
4. Why does BFS specifically need a queue (not a stack) to find shortest paths in an unweighted graph?
5. What is head-of-line blocking in a message queue, and how do teams mitigate it?

Stretch (connects to S025 — Linked Lists): Implement a queue using two stacks. Analyze the amortised time complexity of enqueue and dequeue.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Stacks & Queues? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S027): Recursion — Call Stack, Base Case, Worked Examples
• Previous (S025): Linked Lists — Singly, Doubly, When They Win
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.