FIFO & Queue Mechanics

The opposite discipline

A queue restricts a container the other way around from a stack: add at the back (enqueue), remove from the front (dequeue). First in, first out. Where the stack modeled interrupted work — most recent first — the queue models fair work: things are served in arrival order. Print jobs, request buffers, message queues, and (in Stage 3–4) breadth-first search, which is nothing but "explore in discovery order."

The implementation problem stacks didn't have

A stack was free: both operations at the array's end. A queue needs both ends, and the array's front is its bad end — pop(0) / shift() moves every remaining element:

from collections import deque

bad = []
bad.append(1)          # enqueue: O(1)
bad.pop(0)             # dequeue: O(n) — shifts everything!

q = deque()            # doubly-ended queue — the right tool
q.append(1)            # enqueue        O(1)
q.append(2)
front = q[0]           # peek           O(1)
x = q.popleft()        # dequeue -> 1   O(1)

The SimpleQueue trick — advance a head index instead of shifting — is worth reading twice: it converts dequeue to O(1) by redefining where the front is rather than moving data. Concretely: start with items = ['A', 'B', 'C'], head = 0. dequeue() reads items[0] ('A'), clears that slot, and sets head = 1 — the array itself never moves, only the boundary that marks where the logical queue begins. enqueue('D') just appends: items = [_, 'B', 'C', 'D'], head unchanged. The logical queue (items[head..]) reads ['B', 'C', 'D'] — correct — while the physical array underneath was never shifted. Compare that to the shifting version: the same dequeue() would rewrite ['B', 'C', _], copying every remaining element one slot left. It's the difference between making every passenger on a bus physically shuffle forward one seat when the front seat empties, versus just relabeling which row now counts as "row one."

The tradeoff is head growing forever without bound, wasting the slots behind it — which is what the occasional compaction reclaims. The compaction condition (head past 1000 and past half the array's length) means: by the time it fires, at least 1000 dequeues have happened since the last reset (head only grows via dequeue), and the copy touches at most half the array. Spreading a ≤n/2 copy over ≥1000 prior dequeues gives O(1) amortized per operation — the same shape of argument as the dynamic array's doubling, just triggered by a position threshold instead of a capacity one. Two other O(1) designs you already own:

• Linked list with a tail pointer (Module 7): enqueue = push_back, dequeue = remove head — both O(1), no compaction needed. Note the asymmetry is forced: reverse the roles (enqueue at head, dequeue at tail) and dequeue would need to retarget tail to the previous node — but a singly linked node has no prev, so finding it means walking from the head, an O(n) search. The tail pointer only pays off when it's paired with head-side removal.
• Ring buffer (next lesson): array + modular indices — the tightest version, and the one worth building from scratch.

Recognizing queue-shaped problems

The cue is arrival order matters for service order: process requests as they came; expire the oldest entries first; explore neighbors before neighbors-of-neighbors (BFS's whole idea); buffer between a producer and a consumer. If the most-recent item is special → stack. If the oldest is → queue. If BOTH ends are active → deque (lesson 3).