Queues & Deques

The 10-second versionCopy Anchor Link

A queue is the checkout line: you join at the back and you leave from the front, so whoever arrived first is served first. That rule is first in, first out (FIFO), and it's exactly what you want whenever fairness or arrival order matters — jobs, print pages, network packets, graph vertices. The two core moves are enqueue (add at the back) and dequeue (remove from the front). A deque ("deck") loosens the rule to allow adding and removing from both ends. Cleverly implemented, every one of these is O(1).

Why this existedCopy Anchor Link

Early machines didn't need a queue. They ran one job at a time, straight through. The moment machines got busy — several jobs waiting, many users at once, a printer shared by everyone — the question stopped being "what should the machine do?" and became "what should it do next, and in what order?"

• 1950s — batch systems line up jobs and feed them to the mainframe one at a time, oldest first. The job queue is born out of sheer throughput.
• 1961 — CTSS at MIT time-shares a single machine among many users; a run queue decides which program gets the CPU next.
• 1960s — print spoolers queue documents so two programs printing at once don't scribble over each other's pages.
• 1970s onward — networking buffered packets in queues, and every layer since inherited the pattern.

Why it mattered: FIFO is the simplest possible definition of fair. Before queues, jobs got served in whatever order was convenient for the machine. With a queue, "first come, first served" became a property you could build a scheduler on — and trust.

Inside the inventor's headCopy Anchor Link

Here's the trap that every first attempt falls into. You reach for an array, put the front at index 0, and enqueue by writing at tail. Dequeue, though — the front is gone, so you have to close the gap:

Two failed attempts collapse into the fix. First, shifting everything on every dequeue is correct but O(n) — terrible. Second, leaving the hole behind by moving head is O(1), but the array now runs out of space at the back while the front is mostly empty. The pivot is to stop thinking of the array as a line and start thinking of it as a ring: when you reach the end, wrap to index 0. Modulo is the entire trick.

// Naive: keep the front at index 0 and shift everything down on dequeue.function dequeue(q) {  const front = q.shift();          // shifts every remaining element — O(n)  return front;}

// head advances instead of shifting; modulo wraps it to the front.function dequeue(r) {  if (r.size === 0) return undefined;      // empty  const front = r.data[r.head];  r.head = (r.head + 1) % r.cap;           // wrap around — O(1)  r.size--;  return front;}

The second version does no moving at all — it just nudges an index and lets it wrap. That's the circular buffer, and it powers almost every bounded queue you'll ever touch.

The final approachCopy Anchor Link

The memory pictureCopy Anchor Link

A circular buffer of capacity 6 holding A B C D, with the front at index 2:

head is where the next dequeue reads; the back is at (head + size) mod cap, where the next enqueue writes. When either index hits the end, it wraps.

The algorithmCopy Anchor Link

The invariantsCopy Anchor Link

• size counts live elements; head is the front. The back is always (head + size) mod cap — never stored, always derived, so the two can't drift apart.
• Emptiness and fullness are distinct. A ring can have head == tail while both empty and full, which is why we track size (or keep one slot empty as a sentinel). Get this wrong and you'll either lose data or spin forever.
• Every index wraps modulo cap. This is the property that makes the buffer reusable forever without ever copying.

It in codeCopy Anchor Link

class Queue {  #data; #cap; #head = 0; #size = 0;  constructor(cap) {    this.#cap = cap;    this.#data = new Array(cap);  }  enqueue(x) {                                        // add at the back    if (this.#size === this.#cap) return false;       // full    const tail = (this.#head + this.#size) % this.#cap;    this.#data[tail] = x;    this.#size++;    return true;  }  dequeue() {                                         // remove from the front    if (this.#size === 0) return undefined;           // empty    const x = this.#data[this.#head];    this.#head = (this.#head + 1) % this.#cap;        // wrap    this.#size--;    return x;  }}

A worked traceCopy Anchor Link

Capacity 4, starting empty. Watch head and size move; tail is always derived:

Notice E landed at index 0 even though we never moved anything — the ring came back around. That's the O(1) magic.

Deques and a teaserCopy Anchor Link

A deque (double-ended queue) allows push_front, push_back, pop_front, pop_back, all O(1). A doubly linked list gives that naturally; a growable ring buffer gives it with better locality. There's a lovely specialization, the monotonic deque, where you keep the deque sorted by popping "useless" elements off the back — it solves sliding-window-maximum in O(n). Hold that thought; it returns when we get to the sliding-window techniques.

ComplexityCopy Anchor Link

Space is O(n). The naive array queue is the odd one out: its dequeue is O(n), which is the whole reason the circular buffer exists.

Where you meet it todayCopy Anchor Link

• Breadth-first search. BFS visits vertices in increasing distance from the start, and a FIFO queue is precisely what enforces "explore everything at distance d before anything at distance d + 1." Swap in a stack and you get DFS instead.
• Operating systems & printers. Run queues, wait queues, and spoolers are queues: first come, first served.
• Message brokers. Kafka, RabbitMQ, and SQS deliver in order, which is FIFO made durable across machines.
• Thread pools & rate limiting. Work is queued, workers pull from the front; token-bucket rate limiters drain a queue at a fixed rate.

// BFS frontier: a queue of nodes still to visitfunction bfs(adj, start) {  const visited = new Set([start]);  const queue = [start];  let head = 0;                          // dequeue from the front  while (head < queue.length) {    const u = queue[head++];    for (const v of adj[u])      if (!visited.has(v)) {        visited.add(v);        queue.push(v);                   // enqueue at the back      }  }  return visited;}

RecapCopy Anchor Link

• A queue is FIFO: enqueue at the back, dequeue at the front, both O(1).
• The naive array queue hides an O(n) dequeue in the shifting; the fix is a circular buffer that wraps indices with modulo instead of moving data.
• A deque allows both ends; a monotonic deque keeps its contents sorted for sliding-window problems.
• The defining application is BFS — a queue is what makes breadth-first breadth-first.

Next up: Heaps & Priority Queues — when "first in, first out" isn't good enough and the most important item should go next.