Queues and Deques

A queue is an abstract data type maintaining a sequence with two restricted access points: elements are added only at the rear (`enqueue`) and removed only from the front (`dequeue`). This enforces First-In-First-Out order — the element that has waited longest is served next. Contrast this with a stack, which is Last-In-First-Out (LIFO), removing the most recently added element. A deque relaxes the queue's restriction: both ends allow insertion and removal. Formally, a deque supports `pushFront(x)`, `pushBack(x)`, `popFront()`, and `popBack()`, all in O(1) time. A deque is strictly more general than a queue (use only `pushBack`/`popFront`) and a stack (use only `pushBack`/`popBack`), which is why standard libraries often implement `deque` as the single underlying container and derive `queue` and `stack` as restricted interfaces over it. The central engineering challenge is avoiding the O(n) cost of shifting elements in a plain array. Two efficient strategies dominate in practice. The first is the circular buffer (also called a ring buffer): a fixed-capacity array where a `front` index and a `back` index each advance using arithmetic modulo the capacity, "wrapping around" to index 0 after reaching the end. The second is a doubly linked list, where `head` and `tail` pointers let you splice nodes in or out at either end in O(1) with no arithmetic at all, at the cost of per-element pointer storage and worse cache locality. Both strategies also generalize naturally to a dynamic-array-backed deque, which resizes (doubling/halving) exactly as a dynamic array does, giving amortized O(1) operations even without a fixed capacity.

Circular buffer queue

The circular buffer stores elements in a fixed array `A[0..N-1]`. Two indices, `front` and `back`, track the logical ends of the queue, and a `count` tracks how many elements are currently stored (this sidesteps the full-vs-empty ambiguity described below). `enqueue` writes at `back` and then advances `back = (back + 1) mod N`; `dequeue` reads at `front` and then advances `front = (front + 1) mod N`. ``` structure CircularQueue: array A[0..N-1] integer front = 0 // index of the front element integer back = 0 // index where the next element will be written integer count = 0 // number of elements currently stored function isEmpty(): return count == 0 function isFull(): return count == N function enqueue(x): if isFull(): error "queue overflow" // or: resize A to 2N and re-index A[back] = x back = (back + 1) mod N count = count + 1 function dequeue(): if isEmpty(): error "queue underflow" x = A[front] front = (front + 1) mod N count = count - 1 return x function peekFront(): if isEmpty(): error "empty queue" return A[front] ```

Circular buffer deque

Extending this to a deque adds symmetric operations at the front. The trick is that `pushFront` must move backward from `front`, which in modular arithmetic means adding `N - 1` (equivalently subtracting 1 and wrapping) rather than subtracting 1 directly, since most languages' `mod` on negative numbers behaves inconsistently. ``` structure CircularDeque: array A[0..N-1] integer front = 0 integer back = 0 integer count = 0 function pushBack(x): if count == N: resize() A[back] = x back = (back + 1) mod N count = count + 1 function pushFront(x): if count == N: resize() front = (front - 1 + N) mod N // step backward, safely A[front] = x count = count + 1 function popBack(): if count == 0: error "empty" back = (back - 1 + N) mod N x = A[back] count = count - 1 return x function popFront(): if count == 0: error "empty" x = A[front] front = (front + 1) mod N count = count - 1 return x ``` When capacity is exhausted, `resize()` allocates a new array of size `2N`, copies elements starting at `front` in logical order into positions `0..count-1` of the new array, and resets `front = 0`, `back = count`. This is the same doubling trick used for dynamic arrays, and it delivers amortized O(1) `pushBack`/`pushFront` even though a resize itself costs O(n).

Linked-list deque

The alternative representation uses a doubly linked list with `head` and `tail` pointers. Every node stores a value plus `prev` and `next` pointers. ``` structure Node: value prev, next structure LinkedDeque: Node head = null Node tail = null integer count = 0 function pushFront(x): n = new Node(value=x, prev=null, next=head) if head != null: head.prev = n else: tail = n // list was empty head = n count = count + 1 function pushBack(x): n = new Node(value=x, prev=tail, next=null) if tail != null: tail.next = n else: head = n // list was empty tail = n count = count + 1 function popFront(): if head == null: error "empty" x = head.value head = head.next if head != null: head.prev = null else: tail = null // list became empty count = count - 1 return x function popBack(): if tail == null: error "empty" x = tail.value tail = tail.prev if tail != null: tail.next = null else: head = null // list became empty count = count - 1 return x ``` This version has no amortization: every operation is O(1) in the worst case, not just on average, since there is never a resize. The price is a pointer-per-element memory overhead and weaker cache locality compared to the array version.

Time complexity. For the circular-buffer implementation: `enqueue`/`dequeue` (queue) and `pushFront`/`pushBack`/`popFront`/`popBack` (deque) are all O(1) worst case when capacity is fixed and not exceeded, because each operation performs a constant number of array accesses and one modular addition. When the buffer must grow, resizing costs O(n) for that one call but happens so rarely (doubling means the buffer must fill up again before the next resize) that the amortized cost per operation remains O(1) — the same aggregate/accounting argument used for dynamic array growth. Concretely, after a resize to capacity $2N$, at least $N$ more insertions must occur before the next resize, so the total resizing work across $m$ operations is $O(m)$, giving $O(1)$ amortized per operation. For the linked-list implementation, every operation touches only `head`, `tail`, and at most one node's neighbors — O(1) worst case, with no amortization needed since there is no resizing at all.

Space complexity. The circular buffer uses O(N) space where N is the allocated capacity, which may exceed the actual element count by up to a factor of 2 right after a resize (this is the standard dynamic-array space/time tradeoff). The linked list uses O(n) space exactly proportional to the number of elements, but each element carries the overhead of two extra pointers, which typically costs more per element in practice despite the tighter asymptotic bound.

Correctness — circular buffer. The key invariant is: > At all times, the `count` elements logically in the queue occupy exactly the array slots > $A[\text{front}], A[(\text{front}+1) \bmod N], \dots, A[(\text{front}+\text{count}-1) \bmod N]$, > in that order from front to back. Proof sketch by induction on the operation sequence. Initially `count = 0`, and the invariant holds vacuously. Assume it holds before an operation.

• `enqueue(x)` writes `x` at index `back`. Since `back = (front + count) mod N` is maintained as an invariant consequence (verify: initially `front = back = 0 = (0+0) mod N`), writing there and incrementing `count` extends the occupied range by exactly one slot at the correct position, and `back` advances to `(front + count) mod N` for the new count — invariant preserved.
• `dequeue()` reads `A[front]`, which by the invariant is the oldest remaining element (FIFO correctness), then advances `front` and decrements `count`, shrinking the occupied range from the left — invariant preserved.

The `isFull`/`isEmpty` checks guard against `count` leaving the valid range `[0, N]`, which is exactly what prevents overwriting live data (silent corruption) or reading stale data. This is why tracking `count` explicitly is essential: distinguishing "empty" (front == back, count = 0) from "full" (front == back, count = N) is impossible from `front` and `back` alone, since both conditions produce the identical index pattern. Some implementations instead always leave one slot empty (never let the buffer fill completely) so that `front == back` unambiguously means "empty" — this trades one slot of capacity for removing the need for a `count` field.

Correctness — linked list. The invariant is that the list, followed from `head` via `next` pointers, produces the elements in front-to-back order, and following from `tail` via `prev` pointers produces the reverse. Each push/pop operation splices in or unlinks exactly one node while restoring both pointer directions and the `head`/`tail` sentinels for the empty-list edge case — the case analysis for "list becomes empty" or "list was empty" in the pseudocode above handles the only subtlety.

Tradeoffs. Circular buffers are cache-friendly and memory-compact but need a resize strategy (or a hard capacity cap, undesirable for many applications). Linked lists have no resizing and no wasted capacity, but suffer from pointer-chasing cache misses and roughly 2–3× per-element memory overhead. In practice, production systems (Python's `collections.deque`, Java's `ArrayDeque`) use a variant of the circular buffer — often as a linked list of fixed-size arrays ("unrolled" or "chunked" deque) — to get array-like cache locality with linked-list-like resizing behavior.

Trace a circular buffer of capacity $N = 4$ processing this sequence of operations: ``` enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), dequeue(), dequeue() ```

Step 6 is the interesting one: `back` was 0 before the call, so `enqueue(50)` writes `A[0] = 50` (overwriting the now-logically-removed slot vacated when 10 was dequeued) and then `back = (0+1) mod 4 = 1`. Note `back` now numerically equals `front`, but `count = 4 = N` correctly signals "full," not "empty" — exactly the ambiguity the `count` field resolves. At step 7, `dequeue()` correctly returns 20 (not 50), since `front = 1` points at the true oldest surviving element; the value 50 sits at index 0 but is logically the newest element, third in line behind 20 and 30. This confirms the circular index arithmetic tracks logical order correctly even after wraparound, which is the crux of the structure's correctness.

The queue as an abstract concept predates computing by centuries — it formalizes the everyday notion of "waiting in line," and the mathematical theory of queues (queueing theory) was developed by Agner Krarup Erlang in the early 1900s to analyze telephone traffic. In computer science, queues and deques entered the field as fundamental data structures alongside stacks during the formalization of data structures in the 1950s–60s, becoming a mainstay of algorithm textbooks once breadth-first search, scheduling algorithms, and buffer management made their utility concrete. The circular buffer specifically emerged from hardware and operating-systems practice, where fixed-size memory regions for I/O buffering needed a way to reuse space without shifting bytes — a pattern still visible today in network interface card ring buffers and audio/video streaming pipelines.

Operating system schedulers use queues (often multiple priority queues) to decide which process or thread runs next, ensuring fairness among waiting tasks. Network devices use circular buffers extensively: a network interface card's receive ring buffer stores incoming packets in a fixed-size array that the kernel drains continuously, exactly the enqueue/dequeue pattern described here, chosen specifically because it avoids the cost of shifting packet data. Message-queueing middleware — RabbitMQ, Apache Kafka, Amazon SQS — implements the FIFO queue contract at a distributed-systems scale, using techniques descended from the same core index-management ideas, layered with persistence and replication. Breadth-first search and its many derivatives (level-order tree traversal, shortest paths in unweighted graphs, and the frontier expansion at the heart of many search algorithms that eventually generalize toward structures like B-Trees for on-disk level-by-level access) rely on a plain FIFO queue to process nodes in order of distance from a source. Deques specifically power sliding-window algorithms (finding the maximum in every window of size $k$ in O(n) total time via a monotonic deque), undo/redo stacks that also support "redo-of-redo" from either end, work-stealing schedulers where idle threads steal tasks from the opposite end of a busy thread's deque to minimize contention, and the double-ended `deque` containers ubiquitous in Python, C++, and Java standard libraries.

Ask the tutor: How would you adapt a circular-buffer deque to support efficient random access (`get(i)`) in addition to O(1) push/pop at both ends?