Queues and deques

coreCommon atGoogleAmazonCloudflareDatabricksAnthropicRead firstArraysStacksPractise in the Sandbox →

A queue adds at the back and removes from the front (FIFO), both in O(1). A deque (double-ended queue) does O(1) at both ends. The classic implementation is a ring buffer: a fixed array plus a head index and a size, with positions wrapping around % capacity, so nothing ever shifts.

The idea in plain words

A queue is a line at a coffee shop. New people join at the back; the barista serves the front. Whoever has waited longest goes next. That fairness is why queues run schedulers, print spoolers, message brokers and network buffers.

It’s also why breadth-first search uses one: if you process places in the order you discovered them, you explore everything 1 step away before anything 2 steps away, so the first time you reach a node is along a shortest path.

The implementation trap: an array is great at its end, terrible at its front. Removing a[0] slides everything left (O(n)). Two fixes:

• Don’t move the data, move the index. Keep head pointing at the oldest item. Dequeue is head += 1.
• Reuse the freed space. When the back reaches the end of the array, wrap around to slot 0, which the front has already vacated. That’s a ring buffer (also called a circular buffer).

See it

The ring and the flat row are the same memory. Enqueue until the tail wraps past the end, dequeue a few, then fill it completely. Notice that head and the next-write slot coincide both when it’s empty and when it’s full: that’s why you track size.

Ring buffer: a queue that never shifts

sandbox

valueenqueuedequeue

the same memory, as a flat array

H

·

·

·

11

12

·

012345

T

head3

size2

tail(3+2)%6 = 5

queue[11, 12]

live itemsjust writtenjust readblocked: full

log (newest first)

Nothing yet. Try an operation.

When to reach for it

The problem says…	Why a queue fits
“fewest steps / moves / hops”, “level by level”	BFS: a FIFO queue visits nodes in order of distance. See BFS.
“process in arrival order”, “tasks wait their turn”	FIFO is the fairness rule. See scheduling.
“in the last N seconds / last N events”	A queue of timestamps: append new ones at the back, drop expired ones from the front.
“fixed-size buffer”, “keep only the latest N”	Ring buffer: bounded memory, O(1) per operation.
“add or remove at both ends”, “sliding window max/min”	A deque. See monotonic queue.
producer/consumer, “workers pull jobs”	A (blocking, thread-safe) queue between them. See concurrency.

How it works

Ring buffer mechanics

1. Allocate an array of capacity slots. Keep head (index of the oldest item) and size.
2. The next write goes at (head + size) % capacity. Writing increments size.
3. A read takes slots[head], then head = (head + 1) % capacity and size -= 1.
4. size == 0 means empty; size == capacity means full. Decide what “full” does: reject the write, grow (copy into a bigger array, unrolling the wrap), block the producer, or overwrite the oldest item.

Two pointers or a size?

Some implementations keep head and tail instead of size. Then head == tail is ambiguous (empty or full?), so they either waste one slot (“full” means tail + 1 == head) or keep an extra flag. Tracking size is the simplest way to avoid that bug. With a power-of-two capacity, % capacity becomes the cheaper & (capacity - 1).

BFS: the queue’s most common job

1. Enqueue the start and mark it seen with distance 0.
2. Dequeue a node; for each neighbour not seen yet, record distance + 1, mark it, enqueue it.
3. Repeat until the queue is empty. Nodes leave the queue in non-decreasing distance order.

Python

distances.py

from collections import deque


def distances(graph: dict[int, list[int]], source: int) -> dict[int, int]:
    """Fewest edges from `source` to every reachable node of an unweighted graph."""
    dist = {source: 0}
    q = deque([source])  # 1. FIFO: nodes come out in order of distance
    while q:
        node = q.popleft()  # 2. O(1) at the front (list.pop(0) would be O(n))
        for nxt in graph.get(node, []):
            if nxt not in dist:  # 3. mark when enqueuing, so nothing is queued twice
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist


if __name__ == "__main__":
    g = {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5], 5: []}
    assert distances(g, 0) == {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}
    assert distances(g, 5) == {5: 0}
    assert distances({}, 7) == {7: 0}
    print("ok")

TypeScript

distances.ts

import assert from "node:assert/strict";

/** Fewest edges from `source` to every reachable node of an unweighted graph. */
export function distances(graph: Map<number, number[]>, source: number): Map<number, number> {
  const dist = new Map<number, number>([[source, 0]]);
  const q: number[] = [source]; // 1. FIFO: nodes come out in order of distance
  let head = 0; // 2. dequeue by advancing an index; shift() would be O(n)
  while (head < q.length) {
    const node = q[head++];
    for (const nxt of graph.get(node) ?? []) {
      if (!dist.has(nxt)) { // 3. mark when enqueuing, so nothing is queued twice
        dist.set(nxt, dist.get(node)! + 1);
        q.push(nxt);
      }
    }
  }
  return dist;
}

const g = new Map<number, number[]>([[0, [1, 2]], [1, [3]], [2, [3, 4]], [3, [5]], [4, [5]], [5, []]]);
assert.deepEqual([...distances(g, 0)].sort((a, b) => a[0] - b[0]), [[0, 0], [1, 1], [2, 1], [3, 2], [4, 2], [5, 3]]);
assert.deepEqual([...distances(g, 5)], [[5, 0]]);
assert.deepEqual([...distances(new Map(), 7)], [[7, 0]]);
console.log("ok");

C#

distances.cs

// Fewest edges from `source` to every reachable node of an unweighted graph.
static Dictionary<int, int> Distances(Dictionary<int, int[]> graph, int source)
{
    var dist = new Dictionary<int, int> { [source] = 0 };
    var q = new Queue<int>();               // 1. FIFO: nodes come out in order of distance
    q.Enqueue(source);
    while (q.TryDequeue(out int node))      // 2. O(1); Queue<T> is a ring buffer inside
    {
        foreach (int nxt in graph.GetValueOrDefault(node, []))
        {
            if (dist.TryAdd(nxt, dist[node] + 1)) // 3. mark when enqueuing (TryAdd is false if seen)
                q.Enqueue(nxt);
        }
    }
    return dist;
}

var g = new Dictionary<int, int[]> { [0] = [1, 2], [1] = [3], [2] = [3, 4], [3] = [5], [4] = [5], [5] = [] };
var d = Distances(g, 0);
int[] expected = [0, 1, 1, 2, 2, 3];
for (int i = 0; i < expected.Length; i++)
    if (d[i] != expected[i]) throw new Exception($"node {i}");
if (Distances(g, 5).Count != 1) throw new Exception("sink");
if (Distances([], 7)[7] != 0) throw new Exception("lonely");
Console.WriteLine("ok");

Rotating a queue

Moving items from the front to the back is the queue version of “go around the circle”.

Python

elimination_order.py

from collections import deque


def elimination_order(n: int, k: int) -> list[int]:
    """People 1..n stand in a circle; every k-th is removed. Return the removal order."""
    circle = deque(range(1, n + 1))
    order: list[int] = []
    while circle:
        circle.rotate(-(k - 1))  # 1. move k-1 people from the front to the back, O(k)
        order.append(circle.popleft())  # 2. the k-th is now at the front: remove it
    return order


if __name__ == "__main__":
    assert elimination_order(7, 3) == [3, 6, 2, 7, 5, 1, 4]
    assert elimination_order(5, 1) == [1, 2, 3, 4, 5]
    assert elimination_order(1, 4) == [1]
    assert elimination_order(0, 2) == []
    print("ok")

TypeScript

elimination_order.ts

import assert from "node:assert/strict";

/** People 1..n stand in a circle; every k-th is removed. Return the removal order. */
export function eliminationOrder(n: number, k: number): number[] {
  // JS has no deque: use an array plus a head index, appending to the back.
  const q = Array.from({ length: n }, (_, i) => i + 1);
  let head = 0;
  const order: number[] = [];
  while (head < q.length) {
    for (let s = 0; s < k - 1; s++) q.push(q[head++]); // 1. front to back, k-1 times
    order.push(q[head++]); // 2. the k-th is now at the front: remove it
  }
  return order; // (q grows by about n·k slots; compact it if that matters)
}

assert.deepEqual(eliminationOrder(7, 3), [3, 6, 2, 7, 5, 1, 4]);
assert.deepEqual(eliminationOrder(5, 1), [1, 2, 3, 4, 5]);
assert.deepEqual(eliminationOrder(1, 4), [1]);
assert.deepEqual(eliminationOrder(0, 2), []);
console.log("ok");

C#

elimination_order.cs

// People 1..n stand in a circle; every k-th is removed. Return the removal order.
static List<int> EliminationOrder(int n, int k)
{
    var circle = new Queue<int>(Enumerable.Range(1, n));
    var order = new List<int>();
    while (circle.Count > 0)
    {
        for (int s = 0; s < k - 1; s++)
            circle.Enqueue(circle.Dequeue()); // 1. front to back, k-1 times, O(1) each
        order.Add(circle.Dequeue());          // 2. the k-th is now at the front: remove it
    }
    return order;
}

if (!EliminationOrder(7, 3).SequenceEqual([3, 6, 2, 7, 5, 1, 4])) throw new Exception("case 1");
if (!EliminationOrder(5, 1).SequenceEqual([1, 2, 3, 4, 5])) throw new Exception("case 2");
if (!EliminationOrder(1, 4).SequenceEqual([1])) throw new Exception("case 3");
if (EliminationOrder(0, 2).Count != 0) throw new Exception("empty");
Console.WriteLine("ok");

Time windows

To answer “how many events in the last W seconds?”, keep event timestamps in a queue in arrival order. On each new event or query at time now, pop from the front while the front is too old (outside (now − W, now]), then the queue length is the answer. Each timestamp is enqueued once and dequeued once, so the cost is amortized O(1) per event, the same argument as a sliding window. If events can arrive out of order or memory must be bounded regardless of rate, the plain queue stops being enough; that’s where bucketed counters (one slot per second, in a ring) come in. See rate limiting.

Queues in each language

	Python	TypeScript	C#
queue / deque	collections.deque	none built in: array + head index, or write a ring buffer	Queue<T> (FIFO only)
enqueue	q.append(x)	q.push(x)	q.Enqueue(x)
dequeue	q.popleft()	q[head++] (avoid q.shift(), O(n))	q.Dequeue() / TryDequeue(out x)
peek front	q[0]	q[head]	q.Peek() / TryPeek(out x)
both ends	appendleft, pop, rotate(k)	ring buffer	no built-in deque: LinkedList<T> (AddFirst, RemoveLast…) or a ring buffer
bounded	deque(maxlen=n) drops from the other end when full	write it	write it, or Channel.CreateBounded<T>
thread-safe	queue.Queue (blocking)	n/a (single thread + event loop)	ConcurrentQueue<T>, Channel<T>, BlockingCollection<T>

Inside, .NET’s Queue<T> is a ring buffer over an array that doubles when full; CPython’s deque is a doubly linked list of fixed-size blocks. Both make front operations O(1).

What it costs

Operation	deque / ring buffer	array with pop(0) / shift()	linked list
enqueue (back)	O(1) (amortized if it grows)	O(1) amortized	O(1)
dequeue (front)	O(1)	O(n)	O(1)
peek	O(1)	O(1)	O(1)
index q[i]	O(1) ring buffer; Python deque[i] is O(n) toward the middle	O(1)	O(n)
memory	contiguous, cache friendly	contiguous	one node + pointers per item

Draining n items: front-removal from an array vs a real queue

drag the slider

n = 1,024

list.pop(0) / arr.shift()

523,776

deque / Queue<T> / head index

1,024

Removing from the front of an array slides every remaining element left: n(n−1)/2 moves in total, O(n²). A deque, a ring buffer or a moving head index does one step per dequeue: O(n). At n = 2²⁰ that's about 550 billion moves versus 1 million. (V8 sometimes avoids the copy for small arrays, but you can't count on it.)

Variations you’ll meet

• Bounded / overwriting buffer. Fixed capacity; a write when full either fails or replaces the oldest item. Common for logs, metrics, audio and network buffers.
• Blocking queue. put waits when full, get waits when empty. The textbook producer/consumer coordination.
• Priority queue. Not FIFO at all: removes the smallest key first. That’s a heap.
• Multi-source BFS. Start with several nodes in the queue at distance 0. Everything spreads from all of them at once.
• 0-1 BFS. Edges of weight 0 or 1: push weight-0 neighbours to the front of a deque and weight-1 to the back. Shortest paths in O(V + E).
• Two-stack queue. Push onto an “in” stack, pop from an “out” stack, refilling it only when empty. Amortized O(1).

Pitfalls

• list.pop(0) / arr.shift() in a loop. Quietly O(n²). In Python use deque; in TS use a head index.
• Marking BFS nodes when dequeued instead of when enqueued. The same node gets queued many times; on dense graphs that’s a blow-up.
• Off-by-one wraparound. Use % capacity everywhere, and remember that in JS/C#, % of a negative number is negative (-1 % 5 === -1). For “one step back”, use (i - 1 + capacity) % capacity.
• Empty vs full ambiguity with only head and tail. Track size.
• Time windows with an inclusive/exclusive mix-up. “Last 60 seconds” at time 100: is an event at 40 in or out? Ask, then write the comparison once.

In the interview

• Ask what happens when the buffer is full (reject, block, grow, overwrite?) and when it’s empty (return null, throw, block?). Those are API decisions, and interviewers want you to raise them.
• Say why FIFO: “BFS needs nodes in discovery order so the first visit is the shortest.”
• Call out the language gap: “TypeScript has no deque; I’ll use a head index so dequeue stays O(1).”
• Follow-ups: “make it thread-safe” (a lock around head/size, or a lock-free single-producer/single-consumer ring), “make it unbounded” (grow and copy, unrolling the wrap), “events arrive out of order”, “memory must stay constant”.

Check yourself

Check yourself

pick one

A ring buffer has capacity 8, head = 6 and size = 5. At which index does the next enqueue write?

A11B3C5D2

Check yourself

pick one

A ring buffer stores only head and tail (next write). head == tail. What can you conclude?

AIt is emptyBIt is fullCEither; you need a size counter or a wasted slot to tell

Check yourself

pick one

Your Python BFS uses a list and q.pop(0). On a grid of 1,000 × 1,000 cells, roughly how much work goes into the pops alone?

AAbout 10⁶ element movesBAbout 10¹¹ to 10¹² element movesCConstant

Practice on your own

Classic textbook exercises, not gym questions:

• Level-order traversal of a binary tree, one list per level.
• Minimum knight moves between two squares on a chessboard (BFS over positions).
• Implement a queue with two stacks; then a stack with one queue.
• Open the lock: fewest single-wheel turns to reach a 4-digit code while avoiding forbidden codes (BFS over states).

Go deeper

• Sedgewick and Wayne, Algorithms, §1.3 “Bags, Queues, and Stacks” (resizing-array and linked queues).
• CLRS, §10.1: the array-with-wraparound queue and its overflow/underflow conditions.
• Python docs, collections.deque (maxlen, rotate, O(1) ends, O(n) middle indexing).
• Microsoft Learn, Queue<T> and System.Threading.Channels.

Related

Breadth-first searchThe queue's signature algorithm.

Monotonic stack / queueA deque for window max and min.

HeapsWhen the next item isn't the oldest one.

Rate limitingTime windows over request streams.