Stacks & Queues — LIFO/FIFO in Practice

Review boundary and corrected contracts

Deque endpoint operations have approximately constant cost; list endpoint updates are amortised when resizing applies. Strict next-greater keeps equal values pending. BFS uses FIFO discovery on unit-weight edges and reconstructs to the actual start label. FIFO alone guarantees neither bounded latency nor global ordering in a distributed service.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Use stack (LIFO) and queue (FIFO) fluently in Python, own the monotonic-stack pattern for O(n) next-greater problems, and recognise them running underneath function calls, BFS, undo, and every real event loop.

Why this session exists

Stacks and queues are what happens when you take an ordinary sequence and restrict how you're allowed to touch it. That single restriction unlocks the algorithms that run every function call (call stack), undo/redo histories, FIFO job buffers, level-order graph traversal (BFS queue), and nested syntax (matching-brackets stacks). This session teaches both the abstract API and the two production-favourite variants: monotonic stack (O(n) next-greater-element) and deque (O(1) both-ends queue).

You will be able to

• State the difference between LIFO and FIFO in one sentence each.

• Choose the right Python container: list for stack, collections.deque for queue.

• Solve valid-parentheses, min-stack, and next-greater-element from memory.

• Implement BFS on an unweighted graph with a deque — and distinguish level-order discovery from a recursive depth-first walk.

• Recognise where stacks and queues appear inside the runtime you already use (call stack, event loop, print spooler).

Prerequisites

• S025 · Linked Lists — one way to implement endpoint operations; a circular array is another.
• S023 · Arrays & Strings — the two-pointer skills we'll build on.

Pre-read · skim before the session (25 min total)

Further reading: collections.deque

Further reading: Shunting-yard algorithm (Dijkstra, 1961)

Further reading: LeetCode · Stack tag

(a) Intuition · 5 min

Stack of plates vs line at the DMV

Real: A stack of plates in a cafeteria: you can only take the top plate and add to the top. Last plate in is the first plate out — LIFO. A queue at the DMV: whoever arrived first gets served first, everyone else lines up behind them — FIFO. Cutting the line breaks the invariant, and someone will yell at you.

 
    A stack has push and pop. With a Python list, endpoint updates are amortised O(1); peek and length are O(1). Everything happens at ‘the top’. A queue has enqueue at the back and dequeue at the front, both O(1) — as long as your implementation supports both ends cheaply (list.pop(0) is O(n)! Use deque).
    Once you spot the LIFO / FIFO pattern in a problem, the solution becomes almost mechanical: whatever you saw most recently must be handled first (stack) or whatever you saw first must be handled first (queue). Half of algorithm design is naming the right pattern.
  

The four operations you actually need to memorise

Stack + queue API — that's it

• Stack: push, pop, peek, is_empty. Python list.append/list.pop are amortised O(1); top and length are O(1). Empty pop/top raise IndexError.

• Queue: enqueue, dequeue, peek, is_empty. collections.deque supports approximately O(1) endpoints; circular buffers and head-index designs can also work. list.pop(0) shifts O(n) references.

• Monotonic stack: a stack where elements are always kept in increasing or decreasing order — pop while the new element breaks the invariant. Turns O(n²) into O(n) for next-greater / next-smaller.

• Priority queue: a distinct abstract data type that removes by priority, not arrival order. A binary heap is a common implementation, not its definition.

Avoid repeatedly removing index zero from a Python list

list.pop(0) shifts the remaining references. Draining n elements from the front moves n(n−1)/2 references overall. Use a deque for ordinary single-process FIFO operations. A list with a moving head index avoids per-pop shifts but must eventually compact and release consumed references; it is not the same algorithm as repeated pop(0). For producer/consumer synchronisation, use a queue API with explicit blocking and shutdown semantics.

Timeline — the stack rules everything you touch

The lasting historical ideas are nested subroutine return state, stack-based expression processing, bounded interprocess buffers, undo/redo history and explicit schedulable work frames. They solve different problems: a return address says where to resume; an operator stack delays precedence decisions; a pipe transports bytes, not application message boundaries; a browser session history also has a current position and forward entries.

React Fiber's architecture notes describe virtual stack frames and interruptible work. This is not a claim that React introduced Fiber in 2013, that Back history started in 1998, or that every parser uses shunting-yard. The original unsourced milestone dates are not relied on here.

Optional archived videos

Original optional pointers: stack/queue intuition, valid parentheses, and monotonic-stack walkthrough. Playback, attributions and durations remain unverified. The written mechanisms and executable answers below do not require them.

(b) Removal order becomes an algorithm · 15 min

The applications above range from function calls to event loops, but the useful distinction is smaller: which waiting item can leave next? Start with the two removal points, then use the stack to remember unanswered questions.

Stack (LIFO) vs Queue (FIFO)

Read each chain from its labelled removal end. The stack exposes the most recently pushed value, 3; the queue serves A while new arrivals join behind C. The links show the logical order, not a required storage layout.

The restriction is the algorithmic advantage: a stack makes the newest unfinished item immediately available, while a queue keeps older work ahead of new work. For next-greater-element queries, that unfinished item is an index whose answer has not appeared yet.

The monotonic-stack pattern — from O(n²) to O(n)

Iterate left → right

Desc: For each element x, we want to know ‘what is the next element to the right that's greater than x?’

Keep a stack of INDICES with non-increasing values

Desc: This is the invariant: the top of the stack always holds the smallest ‘still unanswered’ value seen so far.

While top of stack < x, pop it

Desc: The current x is the answer for the popped index. Record it.

Push current index

Desc: It's now waiting for its own answer.

Analysis

Desc: Each index is pushed and popped at most once. Total O(n) — even though it looks like a nested loop.

An index leaves the monotonic stack as soon as its answer arrives; it never needs to be reconsidered. That push-once, pop-once accounting is why the inner loop does not make the total work quadratic. Runtime stacks use the same idea of retaining unfinished work, although the reason for popping differs.

Where stacks show up in the runtime you already use

Function calls: pending callers retain local state and a return continuation. Normal nested returns are LIFO. Runtime implementations differ; Python usually raises RecursionError at its interpreter limit rather than guaranteeing a segfault. Modern CPython does not allocate one C-stack frame for every Python-to-Python call.

Expression parsing: shunting-yard delays operators on a stack according to precedence/associativity. It can emit postfix output or use a value stack to evaluate. JSON nesting can use a stack, but SQL/regex/parser generators are not all shunting-yard implementations.

Back/forward and undo/redo: two stacks can model movement between past and future. Navigating after Back discards the abandoned future branch in the simple model. Real browser session history also involves documents and a current index, not just one push/pop stack.

React Fiber: work is represented in heap objects so a scheduler can retain continuations and yield between units. The crucial contrast is with a synchronous recursive traversal that runs until it returns; recursion expressed with generators or other suspension mechanisms is not inherently impossible to pause.

Where queues show up in the systems you already use

Queues in the wild

Name: BFS traversal

Desc: Standard breadth-first search on any graph or tree. Dequeue a node, enqueue its unvisited neighbours. See S028 and S030.

Name: Print / job spoolers

Desc: FIFO is one possible scheduling policy. Priorities, retries, concurrency and job duration can change start/completion order; do not assume every spooler or worker service is strict FIFO.

Name: Message queues (Kafka, SQS, RabbitMQ)

Desc: Producers and consumers are decoupled, but ordering depends on the service and configuration. Kafka is a retained partitioned log: consumers track offsets; reading does not dequeue/delete a record. Ordering is per partition, not a global topic FIFO.

Name: Event loops

Desc: Runtimes schedule callbacks using more than one queue/phase. A zero-delay timer is eligible after its threshold, not a promise to run next; other work and runtime rules affect when it executes.

Name: Rate limiting (leaky bucket)

Desc: Requests enter a fixed-size queue at the back, are processed off the front at a steady rate. Excess is dropped.

A stack is a stateful ‘remember the recent past’ oracle

Whenever a problem has the phrase ‘the most recent X that…’ or ‘the next greater / smaller…’, a stack is almost certainly the shape of the answer. For minimum edge-count paths in an unweighted graph, FIFO BFS is appropriate. Weighted shortest paths need additional assumptions and often another algorithm, such as Dijkstra with nonnegative weights.

These applications differ in what they store, but the next comparison holds storage fixed and changes only the removal policy. That isolates why replacing a stack with a queue can change the answer, not just the speed.

FIFO discovery and the shortest-path invariant

Stack and queue are different abstract data types that can share a deque implementation. Changing the removal policy changes the traversal invariant. With FIFO, vertices at distance d leave before distance d+1; a newly discovered neighbour therefore gets a shortest unit-edge distance. Mark on enqueue so each vertex is queued once.

A LIFO frontier may discover a vertex along a longer route first. This concrete example returns a parent path, not merely a visitation order:

from collections import deque
 
def first_discovery_path(graph, start, goal, use_stack=False):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        node = frontier.pop() if use_stack else frontier.popleft()
        if node == goal:
            out = [node]
            while out[-1] != start:
                out.append(parent[out[-1]])
            return out[::-1]
        for neighbour in graph.get(node, []):
            if neighbour not in parent:
                parent[neighbour] = node
                frontier.append(neighbour)
    return None
 
g = {"A": ["B", "C"], "B": ["G"], "C": ["D"], "D": ["G"], "G": []}
assert first_discovery_path(g, "A", "G") == ["A", "B", "G"]
assert first_discovery_path(g, "A", "G", True) == ["A", "C", "D", "G"]

The LIFO version is a depth-biased first-discovery search, not a claim that simply swapping one method reproduces every recursive DFS tree/finishing-order convention. The witness disproves shortest-first parent assignment for this policy, not the possibility of finding shortest paths by exhaustive search.

Question: Why is list.pop(0) O(n) while deque.popleft() is O(1)? Both remove one element. The difference is not an optimisation someone forgot.

CPython implements a list as a contiguous array of object references. In its pop implementation, removing an interior item shifts the suffix; index zero moves n−1 references. The need for shifts comes from this storage design, not from O(1) indexing alone: a circular array can maintain a logical head offset and still index in O(1).

A deque uses endpoint-oriented storage. Its end accesses are O(1), but access toward the middle slows to O(n). Removing from one end does not shift the whole container. The documented costs are approximately constant endpoint operations, not hard real-time latency guarantees.

Draining a list is Θ(n²) reference movements versus Θ(n) deque pops. For BFS this adds up to O(V²+E) worst-case work rather than O(V+E), under constant-cost vertex operations. A broad star graph exhibits the queue-shift cost; a narrow chain need not. The demo below uses only 2,000 elements; elapsed-time ratios vary by runtime and hardware.

Name: Plate stack vs. ticket line

Picture: A stack is a spring-loaded plate dispenser: the last plate in is the first out. It naturally models nesting — you must finish the inner thing before returning to the outer thing. Function calls, brackets, undo history, HTML tags: all nesting, all stacks.A queue is a ticket line: first in, first served. It naturally models fairness and distance — everyone at distance k is served before anyone at distance k+1. That is the FIFO invariant behind efficient unit-edge BFS. It is not the only possible algorithm for shortest paths.

• Stack = nesting and backtracking. If the problem says "matching", "innermost", or "undo", it is a stack.

• Queue = arrival order and BFS layers. Minimum edge-count paths fit FIFO; weighted shortest paths and latency fairness need additional rules.

• A direct simulation of recursive calls can make their continuation stack explicit. Some problems also admit a different loop algorithm requiring less stored state.

• A recursive traversal has interpreter-depth risk. An explicit stack/queue has heap-capacity risk; eagerly pushing all children can make even a LIFO frontier wide. Neither structure is safe without input/work bounds.

Trigger: Fire this model the moment you see: bracket or tag matching · undo/redo · a call trace · expression parsing · "fewest number of steps" · a task backlog or work queue · Kafka consumer offsets · Airflow's ready-task pool · any producer/consumer buffer.

Decision: You are processing a backlog of work items that themselves spawn more work. Drain it LIFO (stack) or FIFO (queue)?

Name: LIFO — stack

Gain: a recursive-style stack of iterators can retain O(depth) frames, and LIFO can exploit recent locality. Eagerly pushing all children can instead retain a large frontier; a star is a counterexample to a universal O(depth) stack bound. General graph traversal also stores O(V) visited state.

Cost: starvation — an item pushed early can wait arbitrarily long while newer work keeps arriving; latency for the oldest item is unbounded

Pick: work is a deep tree, memory is the binding constraint, and per-item latency does not matter — crawlers doing depth-limited exploration, dependency resolution, cycle detection

Name: FIFO — queue

Gain: FIFO chooses the oldest waiting item, which supports BFS level order. Latency is not bounded without workload/service assumptions, and oldest-first is not freshest-first

Cost: a BFS frontier can grow exponentially with depth in a branching tree, up to the finite graph size. Retaining older work can reduce locality, but the actual cache cost is workload-dependent

Pick: you need arrival-order service or unweighted BFS levels. An SLA additionally requires bounded work, admission control and sufficient service capacity.

Name: Priority queue

Gain: you choose the ordering explicitly rather than inheriting it from the container; can encode deadline, cost, or business priority

Cost: a binary heap gives O(log n) insertion/removal and O(1) peek; priority policy can starve low-priority work unless fairness is addressed

Pick: items genuinely differ in urgency and you can name the priority function — otherwise you have added complexity to reimplement FIFO badly

Verdict: write down the ordering requirement first. FIFO serves oldest waiting work, but cannot bound latency if arrival rate exceeds service rate or one job runs indefinitely. LIFO is useful for depth-oriented exploration; account for how many children are pushed and whether visited state is retained. Priority scheduling needs an explicit priority and fairness rule. Container choice does not create capacity or a service guarantee.

(c) Hands-on · 25 min

Save as stacks_queues.py. Zero deps beyond stdlib.

"""stacks_queues.py — the interview canon for stacks + queues.
 
Run:  python stacks_queues.py
"""
from __future__ import annotations
from collections import deque
 
 
# ------------------------------------------------------------------
# 1) Valid Parentheses — the canonical stack problem
# ------------------------------------------------------------------
def valid_parentheses(s: str) -> bool:
    # Non-bracket characters are ignored; this is not a full expression parser.
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
 
 
# ------------------------------------------------------------------
# 2) MinStack — get_min in O(1) with an auxiliary stack
# ------------------------------------------------------------------
class MinStack:
    """O(1) top/min, amortised list push/pop; IndexError on empty reads/pops."""
    def __init__(self) -> None:
        self._data: list[int] = []
        self._mins: list[int] = []
 
    def push(self, x: int) -> None:
        self._data.append(x)
        self._mins.append(x if not self._mins else min(x, self._mins[-1]))
 
    def pop(self) -> int:
        self._mins.pop()
        return self._data.pop()
 
    def top(self) -> int:
        return self._data[-1]
 
    def get_min(self) -> int:
        return self._mins[-1]
 
 
# ------------------------------------------------------------------
# 3) Next Greater Element — the monotonic-stack pattern
# ------------------------------------------------------------------
def next_greater(nums: list[int]) -> list[int]:
    """For each element, the next-to-the-right greater value, or -1 if none. O(n)."""
    n = len(nums)
    ans = [-1] * n
    stack: list[int] = []                # stack of INDICES with non-increasing values
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans
 
 
# ------------------------------------------------------------------
# 4) Daily Temperatures — same monotonic-stack idea, different question
# ------------------------------------------------------------------
def daily_temperatures(temps: list[int]) -> list[int]:
    """For each day, days until a warmer temperature (0 if never). O(n)."""
    n = len(temps)
    ans = [0] * n
    stack: list[int] = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans
 
 
# ------------------------------------------------------------------
# 5) Implement a Queue with deque
# ------------------------------------------------------------------
class Queue:
    def __init__(self) -> None:
        self._d: deque = deque()
 
    def enqueue(self, x) -> None:
        self._d.append(x)
 
    def dequeue(self):
        return self._d.popleft()          # O(1) — the whole point of deque
 
    def peek(self):
        return self._d[0]
 
    def __len__(self) -> int:
        return len(self._d)
 
 
# ------------------------------------------------------------------
# 6) BFS on a graph — a queue in its natural habitat
# ------------------------------------------------------------------
def bfs_shortest_path(graph: dict[int, list[int]], start: int, goal: int) -> list[int] | None:
    """Unit-edge graph: shortest node list or None; expected O(V+E) table work."""
    if start == goal:
        return [start]
    seen = {start}
    parent: dict[int, int] = {}
    q: deque = deque([start])
    while q:
        node = q.popleft()
        for nbr in graph.get(node, []):
            if nbr in seen:
                continue
            seen.add(nbr)
            parent[nbr] = node
            if nbr == goal:
                # Reconstruct path by walking parents backwards
                path: list[int] = [nbr]
                while path[-1] != start:
                    path.append(parent[path[-1]])
                path.reverse()
                return path
            q.append(nbr)
    return None
 
 
# ------------------------------------------------------------------
# 7) Perf demo — list.pop(0) vs deque.popleft
# ------------------------------------------------------------------
def perf_demo(n: int = 2_000) -> None:
    import time
 
    lst = list(range(n))
    t = time.perf_counter()
    while lst:
        lst.pop(0)
    print(f"list.pop(0)  n={n:>7} : {time.perf_counter()-t:.3f}s  (O(n^2))")
 
    dq = deque(range(n))
    t = time.perf_counter()
    while dq:
        dq.popleft()
    print(f"deque.popleft n={n:>7} : {time.perf_counter()-t:.3f}s  (O(n))")
 
 
if __name__ == "__main__":
    print("valid '(()[]{})':", valid_parentheses("(()[]{})"))
    print("valid '(]':      ", valid_parentheses("(]"))
 
    ms = MinStack()
    for v in [3, 5, 2, 6, 1, 4]:
        ms.push(v)
    print("MinStack get_min after pushes:", ms.get_min())    # 1
    ms.pop(); ms.pop()                                        # pop 4, 1
    print("MinStack get_min after pops:", ms.get_min())       # 2
 
    print("next_greater [2,1,2,4,3]:", next_greater([2, 1, 2, 4, 3]))
    print("daily_temperatures [73,74,75,71,69,72,76,73]:", daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
 
    graph = {1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: []}
    print("BFS 1 -> 6:", bfs_shortest_path(graph, 1, 6))
 
    perf_demo()

Anatomy of the script

What each block teaches

Name: valid_parentheses

Desc: Push openers, pop on closers and require a matching type. Non-bracket text is ignored; empty input is valid. This validates nesting only, not full syntax or operator precedence.

Name: MinStack

Desc: The auxiliary-stack trick: pushing (value, running_min) pairs (or a parallel stack) makes get_min O(1) without scanning.

Name: next_greater

Desc: Monotonic stack template. Stack holds INDICES with non-increasing values. When a bigger value arrives, it answers all the smaller pending indices at once.

Name: daily_temperatures

Desc: Same pattern as next_greater but the answer is a DISTANCE, not a value. Notice how ans[j] = i - j uses stored indices.

Name: Queue class

Desc: Thin deque wrapper: enqueue/dequeue/peek, with IndexError for empty dequeue/peek. Values are retained by reference, not copied; this is not a synchronised producer/consumer queue.

Name: bfs_shortest_path

Desc: BFS is a queue in action. First-time-you-see-a-node is via the shortest number of edges → the queue pops the closest nodes first.

Name: perf_demo

Desc: A bounded timing illustration, not a benchmark guarantee. It prints two times for n=2,000; the reference-movement argument establishes the complexity, not one noisy run.

What to observe when you run it

ClassName: ml-4 list-decimal space-y-1

valid: True / False for the two test strings. MinStack get_min tracks the running minimum through pushes AND pops correctly. next_greater [2,1,2,4,3] → [4,2,4,-1,-1]. Every index pushed and popped at most once — O(n). daily_temperatures returns [1,1,4,2,1,1,0,0] — waits for the next warmer day. BFS 1→6 returns [1,2,4,6] for the shown neighbour order: four vertices, three edges. [1,3,4,6] is also a shortest path but is not the actual deterministic output of this input. perf_demo uses n=2,000. Do not infer a universal timing ratio; larger front-drain workloads perform quadratically many list-reference shifts.

Contracts and duplicate-sensitive invariants

For MinStack, _mins[i] equals the minimum of _data[:i+1]; storing a minimum at every position keeps duplicate minima correct. Push 3,1,1, then pop once: the minimum remains 1. Empty top, pop and get_min raise IndexError.

For next_greater and daily_temperatures, equal values remain pending: pop only on <, not <=. On [2,2,3], both 2s are answered by 3. Each index is pushed once and popped at most once, so the nested while loop performs O(n) total operations; auxiliary stack/output storage is O(n). The next-greater return value −1 doubles as the missing marker: on negative input it cannot distinguish a real next-greater value of −1 from absence. Return optional indices instead if that distinction matters; do not change this exercise's declared value convention silently.

BFS accepts a finite adjacency-list graph of integer labels, including −1. Missing adjacency entries are sinks. Edges are directed unless supplied both ways; loops and duplicate edges are allowed. start == goal returns [start] even when absent from the mapping. It does not mutate the graph. With V reachable vertices and E scanned adjacency entries it uses O(V) auxiliary storage and expected O(V+E) hash-table work. Weighted costs are outside this shortest-edge-count contract.

Goal: Implement a queue using two stacks and analyse the amortised cost

Hint: One stack for ‘input’, one for ‘output’. On dequeue, if output is empty, pop everything from input into output (reversing the order). Each element is pushed/popped once per stack → amortised O(1) per operation across a sequence starting empty.

class QueueFromStacks:
    def __init__(self):
        self.inbox = []
        self.outbox = []
 
    def enqueue(self, x):
        self.inbox.append(x)
 
    def dequeue(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())   # reverse into outbox
        return self.outbox.pop()
 
q = QueueFromStacks()
for x in [1, 2, 3, 4]:
    q.enqueue(x)
print(q.dequeue(), q.dequeue(), q.dequeue(), q.dequeue())   # 1 2 3 4

Exercise answer: the logical queue is reversed(outbox) followed by inbox. After enqueue 1,2,3 and dequeue 1, enqueue 4 leaves outbox [3,2] and inbox [4]; dequeue still returns 2, then 3, then 4. Only transfer when outbox is empty, or newer values would jump ahead. A dequeue on an empty queue raises IndexError. A single transfer can take O(n), but each item participates in at most four list endpoint operations over its lifetime.

This is a classic design review follow-up. The elegance is in the amortised analysis: any single dequeue could be O(n), but over any sequence of n operations the total work is O(n) — average O(1) per op.

(d) Production reality · 15 min

Logs, offsets and ordering boundaries

A durable log lets producers append independently of consumer progress. Kafka's documentation guarantees record order within a partition; it does not make an entire multi-partition topic one FIFO queue. For partition P0 holding A,C and P1 holding B,D, each local order is preserved while a consumer's merged order can vary. Retries, processing concurrency and acknowledgement semantics require separate treatment. The earlier unsourced LinkedIn message-volume and global-FIFO story is not an operational guarantee.

The front-pop tax without a made-up outage

For a crawler that drains n queued URLs, n(n−1)/2 reference shifts can occur with repeated list.pop(0). At n=2,000 that is 1,999,000 reference moves, versus 2,000 deque pops. This operation count explains the mechanism without asserting an eight-hour incident or a fixed network-crawl speedup. Fetch latency, concurrency, robots rules and memory bounds still matter.

Backpressure, timers and bounded work

Serial await makes independent calls wait one after another; it does not by itself prove an unbounded microtask backlog or an OOM. Unbounded parallel submission can overload the database instead. Use a bounded worker count, cap the waiting backlog, and measure service time, active work and queue age. Node's event-loop guide has multiple phases; a zero timer is not simply the next item in one universal FIFO.

A synchronous bounded model can demonstrate admission policy without starting workers:

from queue import Queue as BlockingQueue, Full
jobs = BlockingQueue(maxsize=2)
jobs.put_nowait("A")
jobs.put_nowait("B")
try:
    jobs.put_nowait("C")
except Full:
    print("reject or retry C according to the application policy")
assert jobs.get_nowait() == "A"
 
from collections import deque
recent = deque(["A", "B"], maxlen=2)
recent.append("C")
assert list(recent) == ["B", "C"]  # discards A; NOT producer backpressure

Blocking, rejecting, dropping oldest/newest, persisting and retrying are different full-buffer policies. Choose deliberately. FIFO plus finite capacity still needs a service-time/admission model for a latency bound.

Where this shows up in the rest of the plan

Root: Stacks + queues appear everywhere

Label: S027 · Recursion

Desc: Nested calls retain LIFO continuation state. A direct recursive/explicit-stack translation can preserve that state, but not every iterative algorithm is a stack simulation.

Label: S028 · Trees & BSTs

Desc: DFS uses depth-oriented continuation state; FIFO BFS uses distance layers. A method swap changes discovery order but does not automatically preserve recursive DFS finishing order.

Label: S029 · Heaps & PQs

Desc: Priority queue is an abstract removal-by-priority interface, commonly implemented by a heap.

Label: S030 · Graphs

Desc: DFS, BFS and Dijkstra illustrate different frontier policies and assumptions; they are not an exhaustive classification of graph algorithms.

Label: Distributed messaging and partitioned logs

Desc: Distributed messaging and partitioned logs decouple producers/consumers; check each ordering and delivery contract rather than assuming global FIFO.

Label: Event loops and concurrency

Desc: Event loops schedule ready work using runtime-specific queues and phases, not one universal FIFO.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click to reveal

Q: State the difference between a stack and a queue in one sentence each.

A: Stack: last-in, first-out (LIFO) — everything happens at the top. Queue: first-in, first-out (FIFO) — enqueue at the back, dequeue at the front.

Q: In Python, what's the correct container for a stack? For a queue?

A: Use list append/pop for a simple stack (amortised O(1) updates; O(1) peek) and deque append/popleft for approximately O(1) FIFO endpoints. Repeated list.pop(0) shifts O(n) references. A blocking queue is a different API for synchronised producer/consumer work.

Q: Explain the monotonic-stack pattern in two sentences.

A: For next strictly greater, keep indices with non-increasing values, retaining ties; while the top value is strictly smaller than the new value, pop and assign its answer. Each index is pushed and popped at most once, giving O(n) total work.

Q: Why does BFS use a queue, not a stack?

A: FIFO processes nondecreasing distance layers, so first discovery gives a shortest path by edge count in an unweighted graph. A LIFO first-discovery frontier can choose a longer parent path, as the A–C–D–G witness shows. Weighted paths need a different invariant; BFS is not a weighted shortest-path solver.

Q: How would you implement a queue with two stacks, and what's the amortised cost?

A: Inbox stack for enqueues, outbox stack for dequeues. On empty outbox, drain inbox into outbox (reverses the order). Each element is pushed and popped at most twice → amortised O(1) per operation.

Q: How does MinStack achieve O(1) get_min?

A: Keep a running minimum for every data-stack position and pop the two stacks together. Duplicate minima each have an entry. Min/top reads are O(1), list push/pop updates amortised O(1), and space O(n); empty reads/pops raise IndexError.

Q: What is a bounded queue, and why do production systems use them?

A: A queue with a capacity can block, reject or drop when full; the policy must be specified. Python queue.Queue(maxsize=...) can block put or raise Full, while deque(maxlen=...) discards from the opposite end on append. Only a policy that slows/rejects producers supplies backpressure; finite capacity alone does not guarantee latency.

Q: You use a stack to check balanced parentheses. What extra state would let you also validate operator precedence?

A: Shunting-yard uses an operator stack plus a precedence/associativity table; it may emit postfix output or use a value stack for evaluation. For 2+3*4, delay + while * is pending, yielding 2 3 4 * + = 14. Bracket matching alone neither evaluates nor validates a complete expression grammar.

Q: Why is ‘the call stack’ actually a stack, not something else?

A: Function calls are LIFO by definition: the currently-executing function must finish (or be paused) before the calling function can resume. Each call pushes a frame (locals + return address); each return pops one.

Q: Stretch — design a MaxQueue supporting enqueue, dequeue, and get_max in amortised O(1). Sketch the data structure.

A: Keep a FIFO deque and a non-increasing candidate deque. On enqueue pop candidates strictly smaller than the new value, retaining equal values; on dequeue remove one candidate front if it equals the removed value. The executable answer below preserves duplicate maxima. Each value enters and leaves each deque at most once; get_max is O(1), updates amortised O(1), and storage O(n). Empty operations raise IndexError.

MaxQueue: an executable stretch answer

from collections import deque
 
class MaxQueue:
    def __init__(self):
        self.values = deque()
        self.candidates = deque()
 
    def enqueue(self, value):
        self.values.append(value)
        while self.candidates and self.candidates[-1] < value:
            self.candidates.pop()
        self.candidates.append(value)
 
    def dequeue(self):
        value = self.values.popleft()
        if self.candidates[0] == value:
            self.candidates.popleft()
        return value
 
    def get_max(self):
        return self.candidates[0]
 
mq = MaxQueue()
for value in [3, 3, 1]:
    mq.enqueue(value)
assert mq.dequeue() == 3 and mq.get_max() == 3
assert mq.dequeue() == 3 and mq.get_max() == 1

The contract uses comparable integers. Changing < to <= without adding duplicate counts loses the second 3 when the first leaves. This is a value-storing design; an index-storing window deque can use a different duplicate rule if its expiry invariant is correct.

Explain-out-loud test

Teach these three in one minute each, no notes:

1. What's the difference between a stack and a queue, and give one everyday example of each.
2. Why is list.pop(0) a performance bug and what should you use instead?
3. What's the monotonic-stack pattern in one breath — and what problem does it solve?

Explain-out-loud answer guide

1. LIFO pops the newest item, like nested pending function calls; FIFO serves the oldest waiting item, like an arrival-ordered job buffer.
2. CPython list.pop(0) shifts the suffix; a deque removes an endpoint without shifting the whole container. A moving-head circular buffer is another design, so constant indexing itself does not force shifts.
3. Keep unanswered indices in non-increasing value order. A new larger value answers every smaller pending top, and each index can leave only once.

Grind this pattern in the LeetCode track

This session builds the mental model for stacks & queues. Related pattern lessons live in the dedicated LeetCode series; their full contents are outside this three-lesson review:

L16 · Stacks · L17 · Monotonic Stack · L18 · Queues & Deques

Do the concept here, then go there to build the reflex.

What comes next

Next: S027 · Recursion — Call Stack, Base Case, Worked Examples

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• Python 3.14 collections — endpoint costs, middle indexing and bounded-deque discard semantics.
• Python queue — blocking/full/empty contracts, distinct from deque.
• CPython v3.14.0 list source — interior-pop reference movement.
• Kafka introduction, Node event loop, and Fiber architecture — qualified production connections, not reproduced services.

Sources checked 2026-10-10. No fixed timing multiplier or production workload is certified.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.