Queues
A queue removes items in insertion order: first in, first out. Enqueue occurs at the rear; dequeue and peek occur at the front.
from collections import deque
queue: deque[str] = deque()
queue.append("first")
queue.append("second")
front = queue[0]
removed = queue.popleft()
deque provides efficient endpoint operations. A Python list.pop(0) shifts
the remaining references and is , so it is not the default queue operation.
Implementations
- Linked endpoints: maintain front and rear nodes; enqueue and dequeue are when invariants are correct.
- Circular buffer: store elements in a fixed array with head and size/tail indexes modulo capacity; bounded operations are without shifting.
- Resizable deque: uses blocks or circular storage to grow while retaining efficient endpoint access.
Invariants and policy
An empty linked queue normally has both front and rear unset. A circular buffer must distinguish empty from full through size, a reserved slot, or an equivalent invariant.
Underflow and full-capacity behavior are part of the interface: raise, block, drop, overwrite, or apply backpressure. Those choices matter more in concurrent and asynchronous systems than the basic FIFO rule.
The bounded Asyncio batch puts backpressure into practice with waiting producers, timeouts, and failure handling.
Uses and boundaries
Queues drive breadth-first search, event loops, buffering, and work scheduling. A priority queue is different: removal follows priority rather than arrival order. Thread/process-safe message queues also require synchronization and delivery semantics beyond this in-memory ADT.
Follow a circular buffer through wraparound
For positive capacity C, maintain head (the next removal index) and size, with 0 <= size <= C. Logical position i lives at (head + i) % C. To enqueue when not full, write at (head + size) % C, then increment size. To dequeue when not empty, read and clear head, advance it to (head + 1) % C, then decrement size. Clearing releases the container's reference to a removed object.
With capacity 3, enqueue A, B, C into slots 0, 1, 2. Dequeue A: head = 1, size = 2. Enqueue D into (1 + 2) % 3 = 0. The physical slots now contain D, B, C, but the logical order is B, C, D. Size distinguishes empty from full even when head and the next insertion index coincide. This is the indexing mechanism used by array-based queues; resizing adds copying and changes the per-operation guarantee.
Open full-size imageRead downward: j is the head index and n is the size. Adding e wraps to slot 0 while a remains at the front; removing a advances j without shifting the other elements. This resizable ArrayQueue starts with six slots, unlike the fixed-capacity example above. The starred add(h) copies the six remaining elements in queue order into twelve slots, resets j to 0, then appends h.
Python capacity behavior
In the opening example, front and removed are "first" and the remaining element is "second". Empty queue[0] or queue.popleft() raises IndexError. The deque documentation specifies a different full-capacity policy for bounded appends:
recent = deque(["A", "B"], maxlen=2)
recent.append("C")
assert list(recent) == ["B", "C"]
This intentionally discards A; it is useful for recent-history buffers, not for a work queue that must retain every task. A deque alone also does not make a compound “check empty, then remove” sequence atomic. Blocking producers and consumers need a queue interface designed for that coordination.
Try the USF circular-queue animation: enqueue several values, dequeue some, then enqueue again. Follow the head and tail through wraparound, and read the logical queue from the head rather than from physical slot zero.