On this page

Queues, Deques & Circular Buffers

A queue is a sequence you add to at one end (the back, or tail) and remove from at the other (the front, or head). Whatever went in first comes out first: FIFO. A deque (double-ended queue, pronounced "deck") lets you add and remove at both ends, so it is a queue and a stack at once. A circular buffer (ring buffer) is the way you implement either on top of a fixed array without ever shifting elements: the indices wrap around modulo the capacity.

Stacks model nesting. Queues model waiting: requests waiting for a server, packets waiting for a link, vertices waiting to be explored, samples waiting to be averaged. Every scheduler, every network card, every breadth-first search, and every message broker has a queue at its heart, and most of them have a ring buffer under that. By the end of this page you will be able to implement a ring buffer that never confuses full with empty, resize it correctly when the data has wrapped, build a deque on it, prove why BFS visits vertices in distance order, and recognise the queue hiding inside a dozen interview problems.

Why this exists

The queue is the natural data structure of any system where work arrives faster than it can be served and fairness matters. Operating systems in the 1960s needed to hold runnable processes in arrival order; Dijkstra's 1965 bounded-buffer problem formalised the producer–consumer pattern that every pipeline since has copied; and telecom switches needed to buffer bursts of calls without dropping the oldest. The circular buffer solved a specific engineering problem these systems shared: a fixed-size region of memory that must behave like an infinite stream, where both producer and consumer move forward forever and the hardware cannot afford to copy data around. Knuth's The Art of Computer Programming Vol. 1 (1968) already presents the circular queue and the full/empty ambiguity with its standard fix, and credits E. J. Schweppe with coining the word "deque".

Queues also have a role inside algorithms that has nothing to do with waiting for resources. Breadth-first search (discovered by Konrad Zuse in 1945 and independently by E. F. Moore in 1959) uses a queue to guarantee that vertices are explored in nondecreasing order of distance from the source, which is why it finds shortest paths in unweighted graphs. Level-order traversal of a tree is BFS. The monotonic deque turns "maximum over every window of size " from to . These uses are about ordering, and the FIFO discipline is what makes the ordering proofs go through.

Finally, the ring buffer has become one of the most important structures in performance engineering. Network drivers hand packets to the kernel through descriptor rings; audio hardware streams samples through ring buffers so that neither producer nor consumer ever blocks; the Linux kernel's kfifo is a lock-free single-producer/single-consumer ring; and the LMAX Disruptor showed in 2011 that a pre-allocated ring with sequence counters could pass tens of millions of events per second between threads with latencies well under a microsecond, far beyond what a locked linked-list queue manages. The reason is cache behaviour: a ring buffer is a contiguous array touched sequentially, which is the memory access pattern hardware is best at.

Pattern triggers

If the problem says or has…Think of…
"first come first served", "in order of arrival", "process requests in order"Plain FIFO queue
"shortest path" in an unweighted graph or grid, "minimum number of steps/moves", "rotting", "spreading", "infection"BFS with a queue — see Graphs
"level by level", "zigzag", "right side view", "width of tree"Level-order traversal (BFS over a tree)
"last items", "moving average", "window of the most recent…"Fixed-capacity ring buffer with a running aggregate
"requests in the last 3000 ms", "hits in the last 5 minutes"Queue of timestamps, pop expired ones from the front
"sliding window maximum / minimum"Monotonic deque — see Monotonic Stack & Monotonic Deque
"design a circular queue / circular deque", "fixed size", "isFull"Ring buffer with head, tail, size (or the one-empty-slot rule)
"implement a queue using stacks" / "a stack using queues"Two-stack queue (amortized) / one-queue rotation
"round robin", "time slice", "take turns"Queue of tasks, requeue at the back after each slice
"producer / consumer", "bounded buffer", "backpressure"Blocking bounded queue
"front, middle and back" operationsTwo deques balanced around the middle
"0/1 weights", "some edges free"0-1 BFS with a deque
"task with cooldown", "reuse after steps"Queue of (item, available-at) pairs

Intuition & first principles

The queue ADT

OperationPromise
enqueue(x) (push_back, offer, append)x becomes the newest element
dequeue() (pop_front, poll, popleft)Removes and returns the oldest element present; error (or sentinel) if empty
front() / peek()Returns what dequeue would return, without removing it
isEmpty(), size()What they say

The algebraic law: elements leave in exactly the order they entered. A queue is a conveyor belt. The deque adds push_front, pop_back, and back(), and the laws become "the two ends are independent stacks that share storage".

The array queue and the shift problem

The first implementation anyone writes is "array; add at the end; remove from the start". Removing from the start of an array means either shifting every remaining element left by one, which is , or leaving a growing gap at the front, which leaks memory. Python's list.pop(0) and list.insert(0, x) do the shift: both are . JavaScript's Array.prototype.shift() and unshift() are specified as element moves too. V8 has an optimisation ("left-trimming") that can make shift cheap on many arrays by moving the object's start pointer rather than its contents, but it does not apply in all cases, is not part of the language, and does not exist in other engines, so treat shift as when it matters and measure if you disagree.

The fix with a head index is to never shift: keep head pointing at the first live element, and dequeue by returning a[head] and incrementing head. Now dequeue is , but the dead prefix a[0..head) is wasted. Two cures: periodically compact (copy the live elements to the front when head exceeds half the array, which is amortized per operation), or make the array circular.

The circular buffer

Give the array a fixed capacity cap, and let both head and tail move forward forever, but reduce them modulo cap when indexing. Enqueue writes at tail and advances it: tail = (tail + 1) % cap. Dequeue reads at head and advances it the same way. The live elements are a[head], a[(head+1) % cap], …, size of them. When tail reaches the end of the array it wraps around to index 0 and reuses the slots dequeue has freed. No element ever moves.

Full versus empty. The trap: when the buffer is empty, head == tail; when it is full, tail has gone all the way round and… head == tail again. The two indices alone cannot tell the states apart. Three standard resolutions:

  1. Keep a size counter. Empty iff size == 0, full iff size == cap. Simplest; costs one integer; the invariant is with size disambiguating the two cases where the congruence is 0. This is what the implementation below does.
  2. Leave one slot empty. Never let the buffer hold more than cap − 1 elements. Then empty iff head == tail, full iff (tail + 1) % cap == head, and size = (tail − head + cap) % cap is always exact. Wastes one slot but needs no counter, which matters when the two indices are updated by different threads and you want each thread to own exactly one variable.
  3. Unbounded counters. Let head and tail be monotonically increasing integers that are never reduced; index with % cap (or & (cap − 1) when cap is a power of two). size = tail − head, exact, no ambiguity. Natural unsigned overflow is harmless when cap is a power of two because the subtraction wraps consistently. This is the Linux kfifo and LMAX Disruptor design.

Resizing. If the buffer must grow, allocate a new array of, say, double the capacity and copy the live elements in logical order starting at index 0 of the new array: that is a[head..cap) followed by a[0..tail) when the data has wrapped, i.e. two memcpys, not one. Then set head = 0, tail = size. Copying the raw array unchanged and keeping the old indices is wrong once the data has wrapped: the wrapped part would land in the middle of the new, larger array with a gap after it.

The linked queue

A singly linked list with pointers to both the first node and the last node gives worst-case enqueue (append at last) and dequeue (remove first). No capacity, no resizing, no full/empty ambiguity, at the cost of one allocation per element, a pointer per element, and poor locality. It is the structure of choice when elements are large objects already on the heap, when latency spikes from resizing are unacceptable, or when you need to splice queues together in . For a queue of small values it loses to the ring buffer by a wide margin on real hardware.

The deque

A deque on a circular array is the ring buffer with one more trick: push_front must move head backwards with wraparound, head = (head − 1 + cap) % cap. The + cap is essential in C, C++, Java, and JavaScript, where % on a negative number returns a negative result (−1 % 8 is −1, not 7). Python's % returns a non-negative result for a positive modulus so (head − 1) % cap works there, but write the portable form anyway. pop_back is tail = (tail − 1 + cap) % cap then read a[tail].

The standard libraries differ in how they build theirs:

LanguageTypeInternal structureRandom accessNotes
Pythoncollections.dequeDoubly linked list of fixed-size blocks (64 slots per block in CPython) in the middle (walks blocks), at the endsmaxlen turns it into a bounded ring that drops from the far end; rotate(k) is
Javajava.util.ArrayDequeSingle circular array, grows when full (by about half in current OpenJDK; Java 8 doubled to powers of two)None exposed (no get(i))Rejects null; not thread-safe; push/pop act on the head
C++std::dequeSegmented: a map of pointers to fixed-size blocks, so growth never relocates elements operator[] with two indirectionsBlock size is implementation-defined: 512 bytes in libstdc++, 16 bytes in MSVC (which is why MSVC's deque is notoriously slow for small T), the larger of 4096 bytes or 16 elements in libc++
JavaScript / TypeScriptnone built inUse Array for stack-like use; for a real deque write a circular array (as below) or a two-index object map—A "two-index map" deque keeps integer keys front..back in a plain object or Map, incrementing/decrementing the ends: amortized at both ends, no wraparound logic, but boxed storage

Complexity summary

Structureenqueue / push_backdequeue / pop_frontpush_frontpop_backRandom accessMemory per element
Array, remove by shift amortized1 slot
Array + head index, compaction amortized amortized—up to 2 slots
Circular buffer (fixed) worst worst worst worst1 slot (+1 if one-empty-slot)
Circular buffer (growable) amortized worst amortized worst1–2 slots
Linked list (head and tail pointers) worst worst worst if doubly linkedvalue + 1–2 pointers + header
Segmented array (std::deque) amortized amortized amortized amortized (two loads)≈1 slot + block map
Two stacks worst amortized, worst———1 slot

Mechanics

Ring buffer: enqueue and dequeue

flowchart LR
    subgraph RING["ring buffer, cap = 4"]
        direction LR
        S0["slot 0"] --> S1["slot 1"] --> S2["slot 2"] --> S3["slot 3"] --> S0
    end
    H["head: next to dequeue"] -.-> S1
    T["tail: next free slot"] -.-> S3
    ENQ["enqueue x"] -->|"a[tail] = x, tail = (tail + 1) mod cap, size++"| T
    DEQ["dequeue"] -->|"x = a[head], head = (head + 1) mod cap, size--"| H

Trace: capacity 4 under 10 operations (computed by script; . marks a free slot; tail is the next free index, and when size == cap it equals head):

StepOperationResultheadtailsizeSlots [0, 1, 2, 3]Logical contents (front → back)
1enqueue Aok011[A, ., ., .]A
2enqueue Bok022[A, B, ., .]A B
3enqueue Cok033[A, B, C, .]A B C
4dequeueA132[., B, C, .]B C
5enqueue Dok103[., B, C, D]B C D
6enqueue Eok114[E, B, C, D]B C D E
7dequeueB213[E, ., C, D]C D E
8dequeueC312[E, ., ., D]D E
9enqueue Fok323[E, F, ., D]D E F
10enqueue Gok334[E, F, G, D]D E F G

Three things to notice. At step 5 tail wrapped from 3 to 0 while head stayed at 1, so the slot array reads [., B, C, D] with the newest element at index 3 and the next write going to index 0. At step 6 the buffer is full and head == tail == 1; without size this would be indistinguishable from empty. At step 10 the physical order [E, F, G, D] bears no resemblance to the logical order D E F G; anyone who dumps the array to debug a ring buffer must rotate it by head first.

A further enqueue H at step 11 would be rejected (or trigger a resize, or overwrite D in an "overwrite oldest" ring such as a log buffer; which one is a policy decision the ADT must document).

Resizing a wrapped buffer

Take the state after step 10: head = 3, tail = 3, size = 4, slots [E, F, G, D]. Growing to capacity 8 by copying the array verbatim would give [E, F, G, D, ., ., ., .] with head = 3, and the next dequeue would correctly return D, but the one after would read slot 4, which is empty: the logical sequence is broken because E F G are "before" D physically but "after" it logically. The correct copy is two segments: a[head..cap) = [D], then a[0..tail) = [E, F, G], giving [D, E, F, G, ., ., ., .], head = 0, tail = 4. Every growable ring buffer bug I have seen in review was this one.

Deque on a ring

flowchart TD
    PF["push_front x"] -->|"head = (head - 1 + cap) mod cap<br/>a[head] = x, size++"| ST["state: head, tail, size"]
    PB["push_back x"] -->|"a[tail] = x<br/>tail = (tail + 1) mod cap, size++"| ST
    ST -->|"x = a[head], head = (head + 1) mod cap, size--"| POF["pop_front -> x"]
    ST -->|"tail = (tail - 1 + cap) mod cap<br/>x = a[tail], size--"| POB["pop_back -> x"]
    ST -->|"size == cap"| GROW["grow: copy two segments<br/>head = 0, tail = size"]

The four operations are symmetric pairs. push_front and pop_back move an index backward and need the + cap guard; push_back and pop_front move forward. The front element is a[head]; the back element is a[(tail − 1 + cap) % cap].

A queue from two stacks: the credit table

The stacks lesson introduced the construction; here is the amortized analysis with real numbers. Enqueue pushes onto inbox. Dequeue pops from outbox, first moving every element from inbox to outbox if outbox is empty. Use the potential function . The amortized cost of an operation is its actual cost plus the change in .

OperationActual stack opsinbox (bottom → top)outbox (bottom → top)Returns afterAmortized cost
enqueue 11[1][]–23
enqueue 21[1, 2][]–43
enqueue 31[1, 2, 3][]–63
dequeue7[][3, 2]101
dequeue1[][3]201
enqueue 41[4][3]–23
enqueue 51[4, 5][3]–43
dequeue1[4, 5][]341
dequeue5[][5]401
dequeue1[][]501

Total actual cost 20 for 10 operations; total amortized cost as well, as it must be when starts and ends at 0. The fourth row is the point: a dequeue that moves three elements costs 7 (three pops, three pushes, one pop) but releases 6 units of potential, so its amortized cost is 1. Every enqueue pays 3: one for itself and two banked for the move it will one day trigger. See Complexity Analysis for the potential method in general.

BFS: the canonical queue user

BFS(source):
    dist[source] = 0; enqueue(source)
    while queue not empty:
        u = dequeue()
        for each neighbour v of u with dist[v] unset:
            dist[v] = dist[u] + 1
            enqueue(v)

The queue is what makes dist correct: vertices are dequeued in nondecreasing order of distance (proved below), so when v is first discovered from u, no shorter path to v can exist. Level-order traversal of a tree is the same loop with "neighbours" = children and no visited set; to process one level at a time, record size() before the inner loop and dequeue exactly that many. Grid problems ("rotting oranges", "walls and gates") are BFS where the graph is implicit. The full treatment is in Graphs.

Other queue algorithms on this page

Moving average from a stream with window : a ring of capacity plus a running sum. On each new value, if the ring is full subtract the value about to be overwritten, write the new value, add it, and return sum / min(count, k). per sample. The ladder below develops it.

Recent counter ("how many requests in the last 3000 ms?"): a queue of timestamps. On ping(t), enqueue t, then dequeue from the front while front < t − 3000, and return size. Each timestamp is enqueued once and dequeued once, so amortized per ping. Because timestamps arrive in increasing order the front is always the oldest, which is what makes the single-ended eviction correct. The same shape, with a time-bucket array instead of a queue, is the hit counter and the sliding-window log in Rate Limiting.

Stack using queues. With one queue: push(x) enqueues x then rotates the queue size − 1 times (dequeue front, enqueue it at the back), which brings x to the front. pop and top are then plain dequeue and front. Push is , pop . Why rotation works: before the push the queue holds the stack bottom-to-top as front-to-back is top-to-bottom; after enqueuing x at the back and rotating the other size − 1 elements behind it, x is at the front and the rest keep their relative order. With two queues you can instead make pop by draining all but the last element into the other queue. Neither is used in practice; the exercise exists to make you think about which end does what.

Round-robin scheduling. A queue of runnable tasks; the scheduler dequeues the front, runs it for one time slice, and if it is not finished enqueues it at the back. Every task waits at most slices between runs: bounded starvation, which is the whole point. Real schedulers layer priorities and dynamic time slices on top; see CPU Scheduling.

Producer–consumer / bounded buffer. A fixed-capacity queue shared between threads: producers block (or fail, or drop) when it is full, consumers block when it is empty. Dijkstra's formulation with two semaphores (empty slots and full slots) plus a mutex is in Classic Synchronization Problems. The capacity bound is what provides backpressure: a fast producer is slowed to the consumer's pace instead of exhausting memory, which is why every serious message queue is bounded somewhere.

Lock-free SPSC ring. With one producer and one consumer, the one-empty-slot ring needs no lock at all: the producer owns tail and only reads head; the consumer owns head and only reads tail. Each side writes the element first and publishes its index second with a release store; the other side reads the index with an acquire load before touching the element. There is no contended write, so there is no need for compare-and-swap. Linux's kfifo works this way (with a power-of-two size and monotonically increasing in/out counters), as do most audio engines. Multi-producer or multi-consumer rings need CAS on the index and are much harder; see Lock-Free Programming.

Priority queue preview. When "next to serve" is not "oldest" but "most urgent", the queue becomes a heap: per operation instead of , in exchange for arbitrary ordering keys. Dijkstra's algorithm is BFS with a priority queue.

The ladder: moving average of the last k values

A stream of numbers arrives; after each one, report the mean of the most recent (or of all of them if fewer than have arrived).

Rung 0: store everything, recompute, per query. Append to a list; average the last by slicing. Correct, and unbounded memory: after a billion samples you hold a billion numbers to answer a question about the last 10.

Rung 1: keep only the window, recompute, per query and memory. Use a queue of capacity : enqueue the new value; if the size exceeds , dequeue the oldest. Sum the queue each time. Memory is now bounded, but each query still walks the window.

Rung 2: running sum, per query. Maintain sum alongside the queue. When a value enters, add it; when a value leaves, subtract it. The average is sum / size. With a ring buffer of capacity the "leaving" value is exactly the one about to be overwritten, so no separate dequeue is needed. Floating-point drift: after millions of additions and subtractions sum accumulates rounding error; for exact results use integers or periodically recompute the sum from the window (every steps costs amortized). The same idea with sums over an index range instead of a time window is the prefix sum.

RungMemoryPer sampleWhy it improves
0—
1drops what can never be needed again
2the window changes by one element in and one out, so the aggregate changes by a constant amount of work

Rung 2 generalises: any aggregate that supports "remove an element" in (sum, count, product without zeros, XOR) works. Aggregates that do not (max, min, median) need the monotonic deque or two heaps.

Correctness

Ring buffer invariant (size-counter variant)

State: array a of length cap, integers head, tail in , integer size in .

Invariant. (i) The logical contents are for , oldest first. (ii) , equivalently .

Initially head = tail = size = 0: no contents, and (ii) holds trivially.

Enqueue (precondition size < cap). Writes a[tail]. By (ii), tail = (head + size) mod cap, which is the slot that would be position size in the logical sequence, and since size < cap that slot is not one of the live slots (positions are distinct mod cap from position size when size < cap), so no live element is overwritten. Then tail advances by one and size by one; (ii) is preserved because both sides grew by one, and (i) is preserved because the new element is at logical position size − 1 (the back).

Dequeue (precondition size > 0). Returns a[head], the logical position 0, i.e. the oldest element, as (i) requires. Then head advances by one and size decreases by one; the logical positions shift down by one, which is exactly what (i) says after the update, and (ii) is preserved because tail is unchanged while head + size is unchanged.

Full/empty. size == 0 and size == cap both give tail == head by (ii), so the indices alone cannot separate them; size does.

One-empty-slot variant

Keep (i) and (ii) but drop size from the state and define it as (tail − head + cap) % cap. Require as an additional invariant. Now size is a function of head and tail, and it is exact precisely because the congruence in (ii) has a unique solution in once size = cap is excluded. Empty iff head == tail; full iff (tail + 1) % cap == head. Enqueue must check the full condition before writing; otherwise the write lands on a[head] and destroys the oldest element. The usable capacity is cap − 1, so allocate one extra slot if the user asked for cap.

Unbounded-counter variant

Let head and tail be unsigned integers that only increase; index with & (cap − 1) where cap is a power of two. Then size = tail − head exactly (as unsigned arithmetic, even across wraparound of the counter, because tail − head is always less than cap and the wraparound of a power-of-two-width integer is itself a modulus compatible with cap). Empty iff head == tail; full iff tail − head == cap. No wasted slot, no counter to synchronise, and the reason kfifo insists on power-of-two sizes.

BFS dequeues in nondecreasing distance (sketch)

Claim. At every moment the queue holds vertices whose dist values are nondecreasing from front to back and differ by at most 1.

Proof by induction over dequeue steps. Initially the queue holds only the source at distance 0. Suppose the claim holds and we dequeue u with dist[u] = d; every remaining vertex has distance or . The neighbours enqueued now get dist = d + 1, which is every distance already in the queue and exceeds the smallest, , by at most 1. So the claim holds after the step. Consequently dequeue order is nondecreasing in distance, so when v is discovered from u with dist[v] = dist[u] + 1, every vertex at distance has already been dequeued and did not reach v; dist[v] is therefore the true shortest distance. The full proof is CLRS 4th ed., Theorem 20.5 (Correctness of breadth-first search).

Complexity

OperationRing bufferGrowable ringLinked queueTwo-stack queue
enqueue worst amortized, worst on grow worst (+ allocation) worst
dequeue worst worst worst amortized, worst
front / back / isEmpty / sizefront amortized
spacecap slots fixedbetween and slots nodes with pointer overhead slots across two arrays

For the algorithms: BFS is with queue space; level-order traversal with space; moving average per sample with space; recent counter amortized per ping with space; one-queue stack push , pop .

Constants are where ring buffers earn their reputation. Enqueue and dequeue are each a load or store, an increment, a compare-and-branch for the wrap (or a mask), and a counter update; there is no allocation and the touched memory is sequential, so a tight loop pushing and popping integers runs at a few nanoseconds per operation and the hardware prefetcher keeps up. A linked queue pays an allocation and a dependent pointer load per element; in a managed language it also creates garbage. Python's collections.deque sits in between: its 64-slot blocks mean one allocation per 64 appends and sequential access within a block. The SPSC lock-free ring adds one more constant: head and tail must live on different cache lines (pad them), or the producer's and consumer's cores will ping-pong the line between them and throughput drops by an order of magnitude, the false sharing problem the Disruptor paper spends a section on.

Implementation

Two classes, identical behaviour and tests in all four languages:

  • CircularQueue(k) — fixed capacity k, the LeetCode 622 interface: enqueue and dequeue return false when full / empty, front and rear return -1 when empty, plus isEmpty and isFull.
  • Deque — growable circular array with pushFront, pushBack, popFront, popBack, front, back, size, isEmpty. Pop on empty throws. Growth doubles the capacity and copies the two segments.
from __future__ import annotations


class CircularQueue:
    """Fixed-capacity FIFO ring buffer using head, tail and a size counter."""

    def __init__(self, k: int) -> None:
        self._a: list[int] = [0] * k
        self._cap = k
        self._head = 0
        self._tail = 0
        self._size = 0

    def enqueue(self, value: int) -> bool:
        if self.is_full():
            return False
        self._a[self._tail] = value
        self._tail = (self._tail + 1) % self._cap
        self._size += 1
        return True

    def dequeue(self) -> bool:
        if self.is_empty():
            return False
        self._head = (self._head + 1) % self._cap
        self._size -= 1
        return True

    def front(self) -> int:
        return -1 if self.is_empty() else self._a[self._head]

    def rear(self) -> int:
        return -1 if self.is_empty() else self._a[(self._tail - 1 + self._cap) % self._cap]

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._cap


class Deque:
    """Growable double-ended queue on a circular array."""

    def __init__(self, capacity: int = 4) -> None:
        self._a: list[int] = [0] * max(1, capacity)
        self._head = 0
        self._size = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def _grow(self) -> None:
        cap = len(self._a)
        new = [0] * (cap * 2)
        # copy in logical order: two segments if the data has wrapped
        for j in range(self._size):
            new[j] = self._a[(self._head + j) % cap]
        self._a = new
        self._head = 0

    def push_back(self, x: int) -> None:
        if self._size == len(self._a):
            self._grow()
        self._a[(self._head + self._size) % len(self._a)] = x
        self._size += 1

    def push_front(self, x: int) -> None:
        if self._size == len(self._a):
            self._grow()
        cap = len(self._a)
        self._head = (self._head - 1 + cap) % cap
        self._a[self._head] = x
        self._size += 1

    def pop_front(self) -> int:
        if self._size == 0:
            raise IndexError("pop_front from empty deque")
        x = self._a[self._head]
        self._head = (self._head + 1) % len(self._a)
        self._size -= 1
        return x

    def pop_back(self) -> int:
        if self._size == 0:
            raise IndexError("pop_back from empty deque")
        self._size -= 1
        return self._a[(self._head + self._size) % len(self._a)]

    def front(self) -> int:
        return self._a[self._head]

    def back(self) -> int:
        return self._a[(self._head + self._size - 1) % len(self._a)]


if __name__ == "__main__":
    q = CircularQueue(3)
    assert q.enqueue(1) and q.enqueue(2) and q.enqueue(3)
    assert not q.enqueue(4)
    assert q.front() == 1 and q.rear() == 3 and q.is_full()
    assert q.dequeue()
    assert q.enqueue(4)
    assert q.rear() == 4 and q.front() == 2
    assert q.dequeue() and q.dequeue() and q.dequeue()
    assert q.is_empty() and not q.dequeue()
    assert q.front() == -1 and q.rear() == -1

    d = Deque(4)
    d.push_back(1); d.push_back(2); d.push_front(0); d.push_front(-1)
    assert len(d) == 4 and d.front() == -1 and d.back() == 2
    d.push_back(3)                       # forces a grow while wrapped
    assert len(d) == 5
    assert d.pop_front() == -1
    assert d.pop_back() == 3
    assert d.pop_front() == 0
    assert d.pop_front() == 1
    assert d.pop_back() == 2
    assert d.is_empty()
    try:
        d.pop_front()
        raise AssertionError("expected IndexError")
    except IndexError:
        pass
    # stress against the stdlib deque
    from collections import deque
    import random
    rnd = random.Random(7)
    ref: deque[int] = deque()
    d = Deque(1)
    for _ in range(5000):
        op = rnd.randrange(6)
        if op == 0:
            v = rnd.randrange(1000); ref.append(v); d.push_back(v)
        elif op == 1:
            v = rnd.randrange(1000); ref.appendleft(v); d.push_front(v)
        elif op == 2 and ref:
            assert ref.pop() == d.pop_back()
        elif op == 3 and ref:
            assert ref.popleft() == d.pop_front()
        elif ref:
            assert ref[0] == d.front() and ref[-1] == d.back()
        assert len(ref) == len(d)
    print("queues: all tests passed")
import java.util.ArrayDeque;
import java.util.NoSuchElementException;
import java.util.Random;

public class QueuesAndDeques {

    /** Fixed-capacity FIFO ring buffer using head, tail and a size counter. */
    static final class CircularQueue {
        private final int[] a;
        private final int cap;
        private int head = 0, tail = 0, size = 0;

        CircularQueue(int k) { a = new int[k]; cap = k; }

        boolean enqueue(int value) {
            if (isFull()) return false;
            a[tail] = value;
            tail = (tail + 1) % cap;
            size++;
            return true;
        }

        boolean dequeue() {
            if (isEmpty()) return false;
            head = (head + 1) % cap;
            size--;
            return true;
        }

        int front() { return isEmpty() ? -1 : a[head]; }
        int rear() { return isEmpty() ? -1 : a[(tail - 1 + cap) % cap]; }
        boolean isEmpty() { return size == 0; }
        boolean isFull() { return size == cap; }
    }

    /** Growable double-ended queue on a circular array. */
    static final class Deque {
        private int[] a;
        private int head = 0, size = 0;

        Deque(int capacity) { a = new int[Math.max(1, capacity)]; }

        int size() { return size; }
        boolean isEmpty() { return size == 0; }

        private void grow() {
            int cap = a.length;
            int[] next = new int[cap * 2];
            for (int j = 0; j < size; j++) next[j] = a[(head + j) % cap]; // two segments, logical order
            a = next;
            head = 0;
        }

        void pushBack(int x) {
            if (size == a.length) grow();
            a[(head + size) % a.length] = x;
            size++;
        }

        void pushFront(int x) {
            if (size == a.length) grow();
            head = (head - 1 + a.length) % a.length;   // '+ a.length' keeps it non-negative
            a[head] = x;
            size++;
        }

        int popFront() {
            if (size == 0) throw new NoSuchElementException("popFront from empty deque");
            int x = a[head];
            head = (head + 1) % a.length;
            size--;
            return x;
        }

        int popBack() {
            if (size == 0) throw new NoSuchElementException("popBack from empty deque");
            size--;
            return a[(head + size) % a.length];
        }

        int front() { return a[head]; }
        int back() { return a[(head + size - 1) % a.length]; }
    }

    static void check(boolean cond, String msg) {
        if (!cond) throw new AssertionError(msg);
    }

    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(3);
        check(q.enqueue(1) && q.enqueue(2) && q.enqueue(3), "fill");
        check(!q.enqueue(4), "full rejects");
        check(q.front() == 1 && q.rear() == 3 && q.isFull(), "front/rear/full");
        check(q.dequeue(), "dequeue");
        check(q.enqueue(4), "enqueue after wrap");
        check(q.rear() == 4 && q.front() == 2, "wrapped rear/front");
        check(q.dequeue() && q.dequeue() && q.dequeue(), "drain");
        check(q.isEmpty() && !q.dequeue(), "empty rejects");
        check(q.front() == -1 && q.rear() == -1, "empty sentinels");

        Deque d = new Deque(4);
        d.pushBack(1); d.pushBack(2); d.pushFront(0); d.pushFront(-1);
        check(d.size() == 4 && d.front() == -1 && d.back() == 2, "deque fill");
        d.pushBack(3);                                   // forces a grow while wrapped
        check(d.size() == 5, "grew");
        check(d.popFront() == -1, "popFront -1");
        check(d.popBack() == 3, "popBack 3");
        check(d.popFront() == 0, "popFront 0");
        check(d.popFront() == 1, "popFront 1");
        check(d.popBack() == 2, "popBack 2");
        check(d.isEmpty(), "empty");
        boolean threw = false;
        try { d.popFront(); } catch (NoSuchElementException e) { threw = true; }
        check(threw, "pop on empty throws");

        // stress against java.util.ArrayDeque
        Random rnd = new Random(7);
        ArrayDeque<Integer> ref = new ArrayDeque<>();
        Deque mine = new Deque(1);
        for (int i = 0; i < 5000; i++) {
            int op = rnd.nextInt(6);
            if (op == 0) { int v = rnd.nextInt(1000); ref.addLast(v); mine.pushBack(v); }
            else if (op == 1) { int v = rnd.nextInt(1000); ref.addFirst(v); mine.pushFront(v); }
            else if (op == 2 && !ref.isEmpty()) check(ref.removeLast() == mine.popBack(), "popBack mismatch");
            else if (op == 3 && !ref.isEmpty()) check(ref.removeFirst() == mine.popFront(), "popFront mismatch");
            else if (!ref.isEmpty()) check(ref.peekFirst() == mine.front() && ref.peekLast() == mine.back(), "peek mismatch");
            check(ref.size() == mine.size(), "size mismatch");
        }
        System.out.println("queues: all tests passed");
    }
}
#include <cstdlib>
#include <deque>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>

static void check(bool cond, const std::string& msg) {
    if (!cond) { std::cerr << "FAIL: " << msg << "\n"; std::exit(1); }
}

// Fixed-capacity FIFO ring buffer using head, tail and a size counter.
class CircularQueue {
    std::vector<int> a_;
    int cap_, head_ = 0, tail_ = 0, size_ = 0;
public:
    explicit CircularQueue(int k) : a_(k), cap_(k) {}

    bool enqueue(int value) {
        if (isFull()) return false;
        a_[tail_] = value;
        tail_ = (tail_ + 1) % cap_;
        ++size_;
        return true;
    }
    bool dequeue() {
        if (isEmpty()) return false;
        head_ = (head_ + 1) % cap_;
        --size_;
        return true;
    }
    int front() const { return isEmpty() ? -1 : a_[head_]; }
    int rear() const { return isEmpty() ? -1 : a_[(tail_ - 1 + cap_) % cap_]; }
    bool isEmpty() const { return size_ == 0; }
    bool isFull() const { return size_ == cap_; }
};

// Growable double-ended queue on a circular array.
class Deque {
    std::vector<int> a_;
    int head_ = 0, size_ = 0;

    void grow() {
        int cap = static_cast<int>(a_.size());
        std::vector<int> next(cap * 2);
        for (int j = 0; j < size_; ++j) next[j] = a_[(head_ + j) % cap];  // two segments, logical order
        a_.swap(next);
        head_ = 0;
    }
public:
    explicit Deque(int capacity = 4) : a_(capacity < 1 ? 1 : capacity) {}

    int size() const { return size_; }
    bool isEmpty() const { return size_ == 0; }

    void pushBack(int x) {
        if (size_ == static_cast<int>(a_.size())) grow();
        a_[(head_ + size_) % a_.size()] = x;
        ++size_;
    }
    void pushFront(int x) {
        if (size_ == static_cast<int>(a_.size())) grow();
        int cap = static_cast<int>(a_.size());
        head_ = (head_ - 1 + cap) % cap;    // '+ cap' keeps it non-negative
        a_[head_] = x;
        ++size_;
    }
    int popFront() {
        if (size_ == 0) throw std::out_of_range("popFront from empty deque");
        int x = a_[head_];
        head_ = (head_ + 1) % static_cast<int>(a_.size());
        --size_;
        return x;
    }
    int popBack() {
        if (size_ == 0) throw std::out_of_range("popBack from empty deque");
        --size_;
        return a_[(head_ + size_) % a_.size()];
    }
    int front() const { return a_[head_]; }
    int back() const { return a_[(head_ + size_ - 1) % a_.size()]; }
};

int main() {
    CircularQueue q(3);
    check(q.enqueue(1) && q.enqueue(2) && q.enqueue(3), "fill");
    check(!q.enqueue(4), "full rejects");
    check(q.front() == 1 && q.rear() == 3 && q.isFull(), "front/rear/full");
    check(q.dequeue(), "dequeue");
    check(q.enqueue(4), "enqueue after wrap");
    check(q.rear() == 4 && q.front() == 2, "wrapped rear/front");
    check(q.dequeue() && q.dequeue() && q.dequeue(), "drain");
    check(q.isEmpty() && !q.dequeue(), "empty rejects");
    check(q.front() == -1 && q.rear() == -1, "empty sentinels");

    Deque d(4);
    d.pushBack(1); d.pushBack(2); d.pushFront(0); d.pushFront(-1);
    check(d.size() == 4 && d.front() == -1 && d.back() == 2, "deque fill");
    d.pushBack(3);                                   // forces a grow while wrapped
    check(d.size() == 5, "grew");
    check(d.popFront() == -1, "popFront -1");
    check(d.popBack() == 3, "popBack 3");
    check(d.popFront() == 0, "popFront 0");
    check(d.popFront() == 1, "popFront 1");
    check(d.popBack() == 2, "popBack 2");
    check(d.isEmpty(), "empty");
    bool threw = false;
    try { d.popFront(); } catch (const std::out_of_range&) { threw = true; }
    check(threw, "pop on empty throws");

    // stress against std::deque
    std::mt19937 rnd(7);
    std::deque<int> ref;
    Deque mine(1);
    for (int i = 0; i < 5000; ++i) {
        int op = static_cast<int>(rnd() % 6);
        if (op == 0) { int v = static_cast<int>(rnd() % 1000); ref.push_back(v); mine.pushBack(v); }
        else if (op == 1) { int v = static_cast<int>(rnd() % 1000); ref.push_front(v); mine.pushFront(v); }
        else if (op == 2 && !ref.empty()) { int r = ref.back(); ref.pop_back(); check(r == mine.popBack(), "popBack mismatch"); }
        else if (op == 3 && !ref.empty()) { int r = ref.front(); ref.pop_front(); check(r == mine.popFront(), "popFront mismatch"); }
        else if (!ref.empty()) check(ref.front() == mine.front() && ref.back() == mine.back(), "peek mismatch");
        check(static_cast<int>(ref.size()) == mine.size(), "size mismatch");
    }
    std::cout << "queues: all tests passed\n";
    return 0;
}
/** Fixed-capacity FIFO ring buffer using head, tail and a size counter. */
class CircularQueue {
  private a: number[];
  private cap: number;
  private head = 0;
  private tail = 0;
  private size = 0;

  constructor(k: number) {
    this.a = new Array<number>(k).fill(0);
    this.cap = k;
  }

  enqueue(value: number): boolean {
    if (this.isFull()) return false;
    this.a[this.tail] = value;
    this.tail = (this.tail + 1) % this.cap;
    this.size++;
    return true;
  }

  dequeue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.cap;
    this.size--;
    return true;
  }

  front(): number { return this.isEmpty() ? -1 : this.a[this.head]; }
  rear(): number { return this.isEmpty() ? -1 : this.a[(this.tail - 1 + this.cap) % this.cap]; }
  isEmpty(): boolean { return this.size === 0; }
  isFull(): boolean { return this.size === this.cap; }
}

/** Growable double-ended queue on a circular array. */
class Deque {
  private a: number[];
  private head = 0;
  private n = 0;

  constructor(capacity: number = 4) {
    this.a = new Array<number>(Math.max(1, capacity)).fill(0);
  }

  size(): number { return this.n; }
  isEmpty(): boolean { return this.n === 0; }

  private grow(): void {
    const cap = this.a.length;
    const next = new Array<number>(cap * 2).fill(0);
    for (let j = 0; j < this.n; j++) next[j] = this.a[(this.head + j) % cap]; // two segments, logical order
    this.a = next;
    this.head = 0;
  }

  pushBack(x: number): void {
    if (this.n === this.a.length) this.grow();
    this.a[(this.head + this.n) % this.a.length] = x;
    this.n++;
  }

  pushFront(x: number): void {
    if (this.n === this.a.length) this.grow();
    const cap = this.a.length;
    this.head = (this.head - 1 + cap) % cap; // '+ cap': JS % keeps the sign of the dividend
    this.a[this.head] = x;
    this.n++;
  }

  popFront(): number {
    if (this.n === 0) throw new RangeError("popFront from empty deque");
    const x = this.a[this.head];
    this.head = (this.head + 1) % this.a.length;
    this.n--;
    return x;
  }

  popBack(): number {
    if (this.n === 0) throw new RangeError("popBack from empty deque");
    this.n--;
    return this.a[(this.head + this.n) % this.a.length];
  }

  front(): number { return this.a[this.head]; }
  back(): number { return this.a[(this.head + this.n - 1) % this.a.length]; }
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error("FAIL: " + msg);
}

const q = new CircularQueue(3);
check(q.enqueue(1) && q.enqueue(2) && q.enqueue(3), "fill");
check(!q.enqueue(4), "full rejects");
check(q.front() === 1 && q.rear() === 3 && q.isFull(), "front/rear/full");
check(q.dequeue(), "dequeue");
check(q.enqueue(4), "enqueue after wrap");
check(q.rear() === 4 && q.front() === 2, "wrapped rear/front");
check(q.dequeue() && q.dequeue() && q.dequeue(), "drain");
check(q.isEmpty() && !q.dequeue(), "empty rejects");
check(q.front() === -1 && q.rear() === -1, "empty sentinels");

const d = new Deque(4);
d.pushBack(1); d.pushBack(2); d.pushFront(0); d.pushFront(-1);
check(d.size() === 4 && d.front() === -1 && d.back() === 2, "deque fill");
d.pushBack(3); // forces a grow while wrapped
check(d.size() === 5, "grew");
check(d.popFront() === -1, "popFront -1");
check(d.popBack() === 3, "popBack 3");
check(d.popFront() === 0, "popFront 0");
check(d.popFront() === 1, "popFront 1");
check(d.popBack() === 2, "popBack 2");
check(d.isEmpty(), "empty");
let threw = false;
try { d.popFront(); } catch (e) { threw = e instanceof RangeError; }
check(threw, "pop on empty throws");

// stress against a plain array used as a reference deque (shift/unshift are fine for a test)
let seed = 7;
const rnd = (m: number): number => { seed = (seed * 1103515245 + 12345) % 2147483648; return seed % m; };
const ref: number[] = [];
const mine = new Deque(1);
for (let i = 0; i < 5000; i++) {
  const op = rnd(6);
  if (op === 0) { const v = rnd(1000); ref.push(v); mine.pushBack(v); }
  else if (op === 1) { const v = rnd(1000); ref.unshift(v); mine.pushFront(v); }
  else if (op === 2 && ref.length > 0) check(ref.pop() === mine.popBack(), "popBack mismatch");
  else if (op === 3 && ref.length > 0) check(ref.shift() === mine.popFront(), "popFront mismatch");
  else if (ref.length > 0) check(ref[0] === mine.front() && ref[ref.length - 1] === mine.back(), "peek mismatch");
  check(ref.length === mine.size(), "size mismatch");
}
console.log("queues: all tests passed");

Design notes:

  • The Deque tracks head and size only and derives tail as (head + size) % cap. Storing tail as well is a second source of truth that must be kept in sync; deriving it removes a class of bugs.
  • grow() copies element by element through the modulo, which is the two-segment copy expressed as one loop. In C++ you would use two std::copy calls for speed; the loop is kept for clarity and because the four versions should read the same.
  • The Python version is a teaching implementation. In production Python use collections.deque, which is C-implemented and faster than anything written in Python.
  • The JavaScript stress test uses an Array with shift/unshift as the reference. That is fine for 5,000 operations in a test and would be exactly the wrong choice for a hot path.

Variant: the one-empty-slot ring

class RingOneSlot:
    """Capacity k usable slots using k + 1 storage and no size counter."""

    def __init__(self, k: int) -> None:
        self._a = [0] * (k + 1)
        self._cap = k + 1
        self._head = 0
        self._tail = 0

    def is_empty(self) -> bool:
        return self._head == self._tail

    def is_full(self) -> bool:
        return (self._tail + 1) % self._cap == self._head

    def size(self) -> int:
        return (self._tail - self._head + self._cap) % self._cap

    def enqueue(self, x: int) -> bool:
        if self.is_full():
            return False
        self._a[self._tail] = x
        self._tail = (self._tail + 1) % self._cap
        return True

    def dequeue(self) -> int | None:
        if self.is_empty():
            return None
        x = self._a[self._head]
        self._head = (self._head + 1) % self._cap
        return x


r = RingOneSlot(3)
assert r.enqueue(1) and r.enqueue(2) and r.enqueue(3) and not r.enqueue(4)
assert r.size() == 3 and r.is_full()
assert r.dequeue() == 1 and r.enqueue(4) and r.size() == 3
assert [r.dequeue() for _ in range(3)] == [2, 3, 4]
assert r.is_empty() and r.dequeue() is None and r.size() == 0

Variant: moving average with a ring and running sum

class MovingAverage:
    def __init__(self, k: int) -> None:
        self._ring = [0] * k
        self._k = k
        self._i = 0        # next write position
        self._count = 0
        self._sum = 0

    def next(self, val: int) -> float:
        if self._count == self._k:
            self._sum -= self._ring[self._i]       # value about to be overwritten leaves the window
        else:
            self._count += 1
        self._ring[self._i] = val
        self._sum += val
        self._i = (self._i + 1) % self._k
        return self._sum / self._count


m = MovingAverage(3)
assert [m.next(v) for v in (1, 10, 3, 5)] == [1.0, 5.5, 14 / 3, 6.0]

Real-world uses

Network interface rings. Every modern NIC exchanges packets with the driver through descriptor rings in memory: the driver fills receive descriptors with buffer addresses, the hardware writes packets and advances a tail pointer, the driver consumes from the head and refills. Transmit works in reverse. Ring size (often 256–4096 descriptors) is a tuning knob visible via ethtool -g. The one-empty-slot or unbounded-counter design is used because producer (hardware) and consumer (CPU) cannot share a lock. See TCP/IP Deep Dive for where this sits in the stack.

Audio. Sound cards stream samples through a ring buffer in a DMA region; the application writes ahead of the hardware's read position. If the writer falls behind, the hardware reads stale data and you hear a click: the buffer underrun. Latency is the distance between the write and read positions, which is why low-latency audio means small rings and tight scheduling.

Linux kfifo. The kernel's generic byte FIFO (lib/kfifo.c) is a power-of-two ring with monotonically increasing in and out counters, indexing by & (size − 1), safe without locking for one producer and one consumer, with memory barriers between the data copy and the counter update. It is used by serial drivers, input devices, and many others.

LMAX Disruptor. Thompson, Farley, Barker, Gee & Stewart's 2011 paper described a pre-allocated ring buffer of event objects with a monotonically increasing sequence number per publisher and per consumer, cache-line padding to avoid false sharing, and no locks or allocation on the hot path. It replaced bounded ArrayBlockingQueues in a financial exchange's matching engine and reported throughput improvements of roughly an order of magnitude over the locked queue on their hardware. The design is now standard in low-latency Java and C++ systems.

Message brokers. Kafka partitions are append-only logs consumed in order, a persistent queue with offsets playing the role of head per consumer; RabbitMQ queues are in-memory FIFOs with disk paging; Redis Streams are a log with consumer groups. The bounded-buffer semantics (what happens when the queue is full: block, drop, or spill to disk) determine the system's behaviour under load. See Message Queues and Backpressure Patterns.

Schedulers. The run queue of a round-robin or multi-level feedback queue scheduler is a FIFO per priority level; the Linux SCHED_RR and SCHED_FIFO real-time policies are literally named after the discipline. CPU Scheduling covers how CFS replaced the plain queue with a red-black tree for the normal class.

Event loops. Node.js, browsers, and GUI toolkits run a loop that dequeues the next event or callback and runs it to completion. The "task queue" and "microtask queue" of the HTML event-loop specification are FIFO queues with a precedence rule between them, which is why Promise.then callbacks run before setTimeout callbacks posted at the same time.

BFS in production. Garbage collectors that use Cheney's copying algorithm perform a BFS over the object graph using the to-space itself as the queue (scan pointer = head, allocation pointer = tail), a beautiful trick where the queue costs no extra memory. Web crawlers, social-graph "friends of friends" queries, and shortest-hop routing all use BFS. Chess engines' iterative deepening and Dijkstra with unit weights are BFS in disguise.

Work-stealing deques. Fork-join thread pools (Java's ForkJoinPool, Go's scheduler, Cilk, Rust's rayon) give each worker a deque of tasks: the owner pushes and pops at one end like a stack (good locality, LIFO keeps the working set hot), while idle thieves steal from the other end (taking the oldest, largest tasks and reducing contention). The Chase–Lev deque (2005) is the standard lock-free implementation; see Concurrency Patterns.

Pitfalls & edge cases

  1. Full vs empty with head == tail. Pick one of the three disambiguation strategies and write the isFull test before the write in enqueue. The one-empty-slot ring has usable capacity cap − 1; allocate accordingly.
  2. Negative modulo. (head − 1) % cap is negative in C, C++, Java, and JavaScript when head == 0. Always write (head − 1 + cap) % cap, or use & (cap − 1) with a power-of-two capacity, or use Math.floorMod in Java.
  3. Resizing a wrapped buffer by copying the raw array. The live data is two segments; copy them in logical order and reset head = 0.
  4. list.pop(0) and Array.shift() in loops. each, so a BFS that uses them is . Use collections.deque in Python; in JavaScript use a head-index array or a ring.
  5. Thread-safety assumptions. collections.deque's append/popleft are atomic in CPython thanks to the GIL, but a check-then-pop sequence is not. ArrayDeque is not thread-safe at all; use ArrayBlockingQueue or ConcurrentLinkedDeque. std::deque offers no guarantees. The SPSC lock-free ring is correct for exactly one producer and one consumer; adding a second producer silently corrupts it.
  6. Unbounded growth. A queue between a fast producer and a slow consumer grows until memory runs out. Bound it, and decide what happens when it is full (block, reject, drop oldest, drop newest). "Drop oldest" is a ring that overwrites; "drop newest" is a ring that rejects.
  7. Level-order traversal without snapshotting the size. for _ in range(len(q)) evaluates the length once in Python, which is what you want; while (!q.isEmpty()) without a level counter mixes levels. In JavaScript, for (let i = 0; i < q.length; i++) re-evaluates q.length every iteration and is wrong once you enqueue children.
  8. Enqueuing without marking visited in BFS. A vertex reachable from several frontier vertices gets enqueued several times; on dense graphs this is an blow-up in queue size and on grids it is the difference between passing and timing out. Mark on enqueue, not on dequeue.
  9. Recent-counter eviction with equality. "Last 3000 ms" is usually inclusive: evict while front < t − 3000, not <=. Read the problem statement.
  10. Floating-point drift in running sums. Subtracting and adding doubles millions of times accumulates error. Use integers if the data allows, or recompute from the window every steps.
  11. Deque indexing in the middle. collections.deque[i] is (it walks blocks), not like a list. If you need random access and both-end operations, use std::deque in C++ or a ring with get(i) = a[(head + i) % cap].
  12. ArrayDeque and null. It throws on null; use a sentinel. LinkedList accepts null but is slower and heavier.

Variations

  • Double-ended priority queue (min-max heap or two heaps with cross-references): pop_min and pop_max in . Used for sliding-window median variants. See Heaps & Priority Queues.
  • Deque of indices (monotonic deque): the window maximum/minimum structure, where the deque holds indices in order and values in monotone order. The entire next lesson.
  • Bounded blocking queue: a ring plus a mutex and two condition variables (notEmpty, notFull), or two semaphores. Java's ArrayBlockingQueue is exactly this; see Classic Synchronization Problems.
  • Work-stealing deque (Chase–Lev): owner uses one end LIFO, thieves steal from the other with a CAS; the array grows by copying into a larger circular array while stealers may still be reading the old one, which is why the paper is subtle.
  • 0-1 BFS: when edge weights are 0 or 1, push a vertex reached by a 0-edge to the front of the deque and by a 1-edge to the back. The deque stays sorted by distance (two levels at most), so it replaces Dijkstra's heap and runs in .
  • Front-middle-back queue: two deques balanced so that the "middle" is the back of the left deque or front of the right one; rebalance by moving one element after each operation. per operation.
  • Queue with getMin: two min-stacks forming a two-stack queue, getMin = min(inbox.min, outbox.min), amortized; or the monotonic deque.
  • Circular buffer that overwrites: enqueue on a full ring advances head too, dropping the oldest. The structure behind log ring buffers (dmesg), flight recorders, and collections.deque(maxlen=k).
  • Persistent / functional queue (Okasaki): two lists with lazy reversal, amortized per operation even with sharing. The two-stack queue is its strict ancestor.

Practice ladder

Each problem is described in my own words. Solutions are Python and are run as part of this page's checks.

1. Design Circular Queue (LeetCode 622) — Medium. Fixed-capacity FIFO with enqueue, dequeue, front, rear, isEmpty, isFull. The canonical implementation above solves it; teaches the full/empty distinction.

Hint

Head, tail, and a size counter. rear is at (tail − 1 + cap) % cap.

2. Design Circular Deque (LeetCode 641) — Medium. Same as above with insert and delete at both ends. Teaches backward wraparound.

Hint

insertFront moves head to (head − 1 + cap) % cap before writing. Everything else mirrors the queue.

3. Implement Queue using Stacks (LeetCode 232) — Easy. Teaches the inbox/outbox transfer and the amortized argument.

Hint

Transfer only when outbox is empty. Each element is moved at most once in its lifetime.

4. Implement Stack using Queues (LeetCode 225) — Easy. Teaches rotation.

Hint

After enqueuing the new element, rotate the queue size − 1 times so it reaches the front.

Solution
from collections import deque


class StackViaQueue:
    def __init__(self) -> None:
        self._q: deque[int] = deque()

    def push(self, x: int) -> None:
        self._q.append(x)
        for _ in range(len(self._q) - 1):      # rotate the older elements behind x
            self._q.append(self._q.popleft())

    def pop(self) -> int:
        return self._q.popleft()

    def top(self) -> int:
        return self._q[0]

    def empty(self) -> bool:
        return not self._q


s = StackViaQueue()
s.push(1); s.push(2); s.push(3)
assert s.top() == 3 and s.pop() == 3 and s.pop() == 2
s.push(4)
assert s.pop() == 4 and s.pop() == 1 and s.empty()

Push , pop and top , space . After push(x) the queue reads x, …older elements in their previous order…, which is the stack from top to bottom.

5. Moving Average from Data Stream (LeetCode 346) — Easy (premium). The ladder problem of this page. Teaches ring plus running sum.

Hint

Capacity- ring; before overwriting a slot subtract its old value from the sum.

Solution
class MovingAverage:
    def __init__(self, size: int) -> None:
        self._ring = [0] * size
        self._k = size
        self._i = 0
        self._count = 0
        self._sum = 0

    def next(self, val: int) -> float:
        if self._count == self._k:
            self._sum -= self._ring[self._i]
        else:
            self._count += 1
        self._ring[self._i] = val
        self._sum += val
        self._i = (self._i + 1) % self._k
        return self._sum / self._count


m = MovingAverage(3)
assert [m.next(v) for v in (1, 10, 3, 5)] == [1.0, 5.5, 14 / 3, 6.0]
m1 = MovingAverage(1)
assert [m1.next(v) for v in (4, 8)] == [4.0, 8.0]

time per call, space.

6. Number of Recent Calls (LeetCode 933) — Easy. Count pings in the last 3000 ms given strictly increasing timestamps. Teaches front-eviction by time.

Hint

Enqueue t; pop from the front while front < t − 3000; return the size.

Solution
from collections import deque


class RecentCounter:
    def __init__(self) -> None:
        self._q: deque[int] = deque()

    def ping(self, t: int) -> int:
        self._q.append(t)
        while self._q[0] < t - 3000:
            self._q.popleft()
        return len(self._q)


rc = RecentCounter()
assert [rc.ping(t) for t in (1, 100, 3001, 3002)] == [1, 2, 3, 3]

Amortized per ping (each timestamp enters and leaves once); space . Timestamps increase, so the front is always the oldest.

7. Design Hit Counter (LeetCode 362) — Medium (premium). Hits in the last 300 seconds, possibly many per second. Teaches the bucket-array alternative to a per-event queue.

Hint

Either a queue of (timestamp, count) pairs, or 300 buckets indexed by t % 300 storing (timestamp, count); reset a bucket when its stored timestamp is stale.

8. Binary Tree Level Order Traversal (LeetCode 102) — Medium. Teaches BFS with level snapshots.

Hint

Record len(queue) at the start of each level and dequeue exactly that many nodes.

9. Rotting Oranges (LeetCode 994) — Medium. Multi-source BFS on a grid, counting levels until no fresh cells remain. Teaches seeding the queue with all sources.

Hint

Enqueue every rotten cell at time 0, BFS level by level, return the number of levels, or −1 if a fresh orange is unreachable.

10. Design Front Middle Back Queue (LeetCode 1670) — Medium. Push and pop at front, middle, and back. Teaches two balanced deques.

Hint

Keep left and right deques with len(left) <= len(right) <= len(left) + 1; the middle is right[0] when sizes differ or left[-1] when equal (for pop), and insertions go to left's back when the sizes are equal. Rebalance after every operation.

Solution
from collections import deque


class FrontMiddleBackQueue:
    def __init__(self) -> None:
        self.left: deque[int] = deque()
        self.right: deque[int] = deque()

    def _balance(self) -> None:
        # invariant: len(left) <= len(right) <= len(left) + 1
        if len(self.left) > len(self.right):
            self.right.appendleft(self.left.pop())
        elif len(self.right) > len(self.left) + 1:
            self.left.append(self.right.popleft())

    def pushFront(self, val: int) -> None:
        self.left.appendleft(val); self._balance()

    def pushMiddle(self, val: int) -> None:
        if len(self.left) < len(self.right):
            self.left.append(val)
        else:
            self.right.appendleft(val)
        self._balance()

    def pushBack(self, val: int) -> None:
        self.right.append(val); self._balance()

    def popFront(self) -> int:
        if not self.right:
            return -1
        v = self.left.popleft() if self.left else self.right.popleft()
        self._balance()
        return v

    def popMiddle(self) -> int:
        if not self.right:
            return -1
        v = self.left.pop() if len(self.left) == len(self.right) else self.right.popleft()
        self._balance()
        return v

    def popBack(self) -> int:
        if not self.right:
            return -1
        v = self.right.pop()
        self._balance()
        return v


q = FrontMiddleBackQueue()
q.pushFront(1); q.pushBack(2); q.pushMiddle(3); q.pushMiddle(4)   # [1, 4, 3, 2]
assert q.popFront() == 1      # [4, 3, 2]
assert q.popMiddle() == 3     # [4, 2]
assert q.popMiddle() == 4     # [2]
assert q.popBack() == 2       # []
assert q.popFront() == -1

# brute-force cross-check
import random
rnd = random.Random(3)
q = FrontMiddleBackQueue(); ref: list[int] = []
for _ in range(3000):
    op = rnd.randrange(6); v = rnd.randrange(100)
    if op == 0: q.pushFront(v); ref.insert(0, v)
    elif op == 1: q.pushMiddle(v); ref.insert(len(ref) // 2, v)
    elif op == 2: q.pushBack(v); ref.append(v)
    elif op == 3: assert q.popFront() == (ref.pop(0) if ref else -1)
    elif op == 4: assert q.popMiddle() == (ref.pop((len(ref) - 1) // 2) if ref else -1)
    else: assert q.popBack() == (ref.pop() if ref else -1)

Every operation is . The two-deque split with a size invariant is the standard way to expose a "middle" pointer.

11. Sliding Window Maximum (LeetCode 239) — Hard. Teaches the monotonic deque; developed fully in the next lesson.

Hint

Deque of indices with decreasing values; pop the front when it leaves the window; pop the back while its value is ≤ the new one.

12. Shortest Subarray with Sum at Least K (LeetCode 862) — Hard. Prefix sums plus a monotonic deque. Teaches that the deque can be a candidate list for a left endpoint.

Hint

Deque of prefix-sum indices with increasing prefix values. For each new prefix, pop from the front while prefix[i] − prefix[front] ≥ K (recording the length), and pop from the back while prefix[back] ≥ prefix[i].

13. Constrained Subsequence Sum (LeetCode 1425) — Hard. DP where each state takes the best of the previous states. Teaches the monotonic deque as a sliding-window-max over DP values.

Hint

dp[i] = nums[i] + max(0, max(dp[i−k..i−1])); the window maximum is the monotonic deque from problem 11.

14. Message Route (CSES 1667) — BFS with parent pointers on a graph of up to nodes; reconstruct the path. Teaches BFS as shortest path and path reconstruction.

Hint

BFS from node 1 recording parent. If node is unreached print IMPOSSIBLE; otherwise walk parents back from and reverse.

15. Open the Lock (LeetCode 752) — Medium. Shortest sequence of single-wheel turns on a 4-digit lock avoiding forbidden states. Teaches BFS over an implicit state space of 10,000 nodes.

Hint

Each state has 8 neighbours. BFS from "0000" with the dead-end set pre-marked as visited.

Common mistakes & interview follow-ups

"Your ring buffer is fixed size. How would you make it grow, and what breaks?" Double the capacity and copy the two segments in logical order, resetting head = 0. What breaks: worst-case on the growing enqueue (amortized still), and any lock-free protocol, because other threads may hold indices into the old array. The Chase–Lev deque handles exactly this and it is the hard part of that paper.

"Make the queue thread-safe." Clarify producers and consumers. One each: the SPSC ring with acquire/release on the indices, no lock. Many: a mutex plus two condition variables, or a lock-free MPMC queue (Michael–Scott for linked, Vyukov's bounded MPMC for arrays), with a frank statement that MPMC lock-free is hard to get right and usually not worth it unless measured.

"What if the stream is infinite and we need the last ?" Ring of capacity that overwrites; the aggregate update is the only thing that changes with the question (sum: subtract outgoing; max: monotonic deque; median: two heaps with lazy deletion or an order-statistics tree).

"Why is BFS correct for shortest paths but DFS is not?" Because the queue dequeues in nondecreasing distance (the invariant above), so first discovery is shortest discovery. DFS follows one path to its end and can discover a vertex via a long path before the short one.

"BFS uses too much memory on this graph. Options?" Bidirectional BFS (frontiers meet in the middle, roughly square-rooting the explored set), iterative deepening DFS (linear memory, repeated work), or exploiting structure (grids: store visited as a bitset). Mention that BFS memory is proportional to the frontier, which for a branching factor and depth is .

"Implement a queue with getMax in ." Two max-stacks as inbox/outbox: getMax = max(inbox.max, outbox.max), amortized . Or the monotonic deque if elements are removed in FIFO order only.

"Why does Python's deque have indexing if it's array-based?" It is not one array; it is a doubly linked list of 64-slot blocks, so indexing walks blocks. The design favours worst-case both-end operations and never relocating elements over random access.

"Why does the Disruptor pad its sequence counters?" Two counters updated by different cores in the same 64-byte cache line cause false sharing: every write invalidates the other core's copy of the line. Padding each counter to its own line removes the coherence traffic.

Common mistakes seen in interviews: pop(0) on a Python list in BFS; forgetting + cap before % when moving backwards; computing the level size inside the loop; not marking visited on enqueue; declaring isFull as head == tail; and reaching for a linked list "for dequeue" when the ring buffer gives the same complexity with a fraction of the constant.

Quick quiz

  1. A ring buffer with capacity 8 has head = 6, tail = 2. How many elements does it hold under the one-empty-slot rule, and which slots are live?
Answer

size = (2 − 6 + 8) % 8 = 4. Live slots are 6, 7, 0, 1 (logical order). Slot 2 is where the next enqueue goes; slots 3, 4, 5 are free, and the rule forbids the buffer from ever holding 8.

  1. Why does (head − 1) % cap fail in Java but work in Python?
Answer

Java's % takes the sign of the dividend, so −1 % 8 == −1, an invalid index. Python's % takes the sign of the divisor, so −1 % 8 == 7. Write (head − 1 + cap) % cap in every language, or use Math.floorMod in Java.

  1. In the two-stack queue with potential , why is the amortized cost of a dequeue that moves elements equal to 1?
Answer

Actual cost is ( pops, pushes, one final pop). The potential drops from to 0. Amortized cost .

  1. You grow a wrapped ring from capacity 4 to 8 by Arrays.copyOf. State after growth: head = 3, size = 4, slots [E, F, G, D, _, _, _, _]. What does the second dequeue return, and what should it have returned?
Answer

First dequeue returns D (slot 3) and moves head to 4; the second reads slot 4, which is empty garbage. It should have returned E. The correct growth copies [D, E, F, G] to the front and resets head = 0.

  1. Why does BFS mark vertices visited when they are enqueued rather than when they are dequeued?
Answer

Marking on dequeue lets a vertex be enqueued once per frontier neighbour before any copy is processed; on a grid a cell can be enqueued up to four times, and on dense graphs the queue can grow to . Marking on enqueue guarantees each vertex is enqueued exactly once, so the queue is and the running time . Correctness is unaffected because the first enqueue is already at the shortest distance.

Further reading / sources

  • Knuth, The Art of Computer Programming, Vol. 1, §2.2.1 "Stacks, Queues, and Deques" — the circular queue, the full/empty problem, and the origin of the word "deque".
  • Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., §10.1 (queues), §20.2 (BFS, including Theorem 20.5 on correctness), Chapter 16 (amortized analysis).
  • Sedgewick & Wayne, Algorithms, 4th ed., §1.3 — resizing-array queue and its amortized analysis.
  • M. Thompson, D. Farley, M. Barker, P. Gee & A. Stewart, "Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads", LMAX technical paper, 2011. lmax-exchange.github.io/disruptor.
  • D. Chase & Y. Lev, "Dynamic Circular Work-Stealing Deque", SPAA 2005. DOI 10.1145/1073970.1073974.
  • E. W. Dijkstra, "Cooperating sequential processes", 1965 (EWD123) — the bounded buffer.
  • Linux kernel source, include/linux/kfifo.h and lib/kfifo.c — the SPSC power-of-two ring.
  • CPython source, Modules/_collectionsmodule.c — BLOCKLEN 64 and the block-list design of deque.
  • C. Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998, Chapter 5 — amortized queues.
  • cp-algorithms, Minimum stack / Minimum queue.

Prev: Stacks · Next: Monotonic Stack & Monotonic Deque

Related: Module 1 — Linear Data Structures · Graphs · Trees · Heaps & Priority Queues · Linked Lists · Sliding Window · Prefix Sums & Difference Arrays · Complexity Analysis · Lock-Free Programming · DSA: Zero to Mastery