Cairn
data structures · FIFO · O(1) enqueue/dequeue

↩ back to Linear

Queue

A queue holds a sequence of items with one rule: you add at one end — the rear — and remove from the other — the front. That makes it first in, first out (FIFO): whatever's been waiting longest is the first thing that comes back out. It's the same shape as a line at a checkout counter, a print queue, or messages waiting to be processed in the order they arrived. See Stack for its mirror image — same "add/remove from an end" shape, opposite ordering.

Try it

Enqueue values at the rear, dequeue them from the front, or peek at the front without removing it. The solid block is always the front — the only element a queue lets you remove. The outlined block is the rear — where new items join.

Loaded a sample queue. Enqueue, dequeue, peek, or clear — try dequeuing past empty.

Core operations

Like a stack, a queue has a small, deliberate interface — it's a stack with the removal end flipped:

There's no get(i) here either, and no way to cut the line — an item leaves only once everything ahead of it already has.

Reference implementation

class Queue {
  #items = [];
  #head = 0;

  enqueue(x) {
    this.#items.push(x);
  }

  dequeue() {
    if (this.isEmpty()) throw new Error('dequeue on empty queue (underflow)');
    const x = this.#items[this.#head];
    this.#head++;
    // reclaim the wasted prefix once it dominates what's left
    if (this.#head > 16 && this.#head * 2 > this.#items.length) {
      this.#items = this.#items.slice(this.#head);
      this.#head = 0;
    }
    return x;
  }

  peek() {
    if (this.isEmpty()) throw new Error('peek on empty queue');
    return this.#items[this.#head];
  }

  isEmpty() {
    return this.#head >= this.#items.length;
  }
}

The naive version of this class would call this.#items.shift() in dequeue() — but shift() removes from the front of a JavaScript array by re-indexing every remaining element, which is O(n) per call. This version instead advances a #head pointer and leaves dequeued slots in place, making dequeue() O(1) — and only pays the cost of compacting the array (a slice) once the dead prefix has grown past half the array, so that cost amortizes to O(1) too. A ring buffer (fixed-size array, wrapping indices) or a linked list with head and tail pointers are the other standard ways to get the same O(1) guarantee.

Pitfalls

Underflow. Dequeuing or peeking an empty queue is the same class of bug as stack underflow. Know what your implementation does — throw, return a sentinel, or (like a raw array's .shift() on an empty array) quietly hand back undefined. The demo above logs the underflow instead of throwing, on purpose, so you can see what it looks like.

The shift() trap. It's tempting to implement a queue as push() + shift() on a plain array — and it's correct, but silently O(n) per dequeue instead of O(1). That's invisible until the queue gets long, at which point it becomes a real bottleneck. This is the single most common queue performance bug.

Measure it instead of taking "invisible until it's long" on faith. This race loads a queue of n items, then runs n dequeue-then-enqueue cycles — keeping the queue at size n throughout, the way a long-running queue actually behaves — and counts every real array element touched: the naive push() + shift() version against the #head-pointer reference implementation above (including its real slice compaction cost, not an idealized O(1)).

Press "Run race" to count real array touches for both implementations over n dequeue+enqueue cycles.

At n = 1,000 — 1,000 dequeue+enqueue cycles on a queue held at size 1,000 — the naive shift() version touches 1,000,000 array elements (n per dequeue, n times over); the #head-pointer version, compaction included, touches 2,999 — a 333x difference. That ratio isn't fixed: at n = 200 it's 67x, and at n = 5,000 it's 1,667x, growing roughly linearly with queue depth because the naive version's total cost is O(n) per call while the head-pointer version's stays flat per call — exactly the "invisible until the queue gets long" shape the Pitfall above describes, not just asserts.

Confusing it with a stack. Enqueue/dequeue and push/pop look like the same "add and remove from an end" shape in code, but a queue removes from the opposite end it adds to, while a stack uses the same end for both. Mixing them up silently reverses the order everything comes out in.

Where queues show up

Complexity

Time: with a head pointer or ring buffer, enqueue, dequeue, and peek are all O(1) (amortized for the array-backed version). Searching for an arbitrary element is O(n) — the only sanctioned access points are the two ends. Space: O(n) for n stored items. Same trade as a stack: refusing to do anything but add-at-rear and remove-at-front is what makes both ends cheap.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.