Skip to main content

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 O(n)O(n), so it is not the default queue operation.

Implementations​

  • Linked endpoints: maintain front and rear nodes; enqueue and dequeue are O(1)O(1) when invariants are correct.
  • Circular buffer: store elements in a fixed array with head and size/tail indexes modulo capacity; bounded operations are O(1)O(1) 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.

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.

Source​