↩ 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.

Core operations

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

• enqueue(x) — add x at the rear.
• dequeue() — remove and return the item at the front.
• peek() (or front()) — return the front item without removing it.
• isEmpty() — whether there's anything to dequeue or peek.

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.

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

• Breadth-first search. BFS is the queue's mirror to DFS's stack: visit a node, enqueue its unvisited neighbors, repeat. That processes the graph one distance-from-start "layer" at a time, which is exactly what a FIFO order guarantees.
• Task and print queues. Jobs are handled in the order they were submitted — first requested, first served.
• Message and event queues. Producers enqueue events or messages; consumers dequeue and process them in arrival order, decoupling how fast each side runs.
• Round-robin scheduling. A CPU scheduler can cycle through ready processes by dequeuing one, giving it a time slice, and enqueuing it again at the rear if it's not done — a queue used as a rotating line.

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.