Queues

Array.shift is O(n), so a real queue needs either the two-stack amortized trick or a singly-linked list to keep both enqueue and dequeue at O(1).

5 min read Level 2/5 #dsa#queue#fifo

What you'll learn

Explain why Array.shift makes a naive array queue O(n) per dequeue
Implement a queue with two stacks using amortized O(1) dequeue
Implement a linked-list queue with true O(1) enqueue and dequeue

A queue follows the first-in, first-out (FIFO) principle — the item that has been waiting the longest is served first. Queues model real-world waiting lines: print spoolers, event loops, BFS traversal, and task schedulers all rely on them.

Why Array.shift Is Problematic

JavaScript arrays store elements contiguously. Removing from the front with shift() forces the engine to slide every remaining element one position to the left — that is O(n) work per dequeue. For small queues it is fine, but at scale it becomes a bottleneck.

// Naive — DO NOT use for performance-sensitive queues
const queue = [];
queue.push("a"); // enqueue O(1)
queue.push("b");
queue.shift();   // dequeue O(n) — slides all elements left

Two-Stack Queue (Amortized O(1))

Keep an inbox stack for enqueue and an outbox stack for dequeue. When the outbox is empty, pour the entire inbox into it (reversing order so the oldest item lands on top). Each element crosses from inbox to outbox exactly once, so dequeue is O(1) amortized.

class Queue {
  #inbox = [];
  #outbox = [];

  enqueue(value) {
    this.#inbox.push(value);
  }

  dequeue() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length) {
        this.#outbox.push(this.#inbox.pop()); // reverse into outbox
      }
    }
    if (this.#outbox.length === 0) throw new Error("Queue is empty");
    return this.#outbox.pop();
  }

  peek() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length) {
        this.#outbox.push(this.#inbox.pop());
      }
    }
    if (this.#outbox.length === 0) throw new Error("Queue is empty");
    return this.#outbox.at(-1);
  }

  get size() {
    return this.#inbox.length + this.#outbox.length;
  }

  isEmpty() {
    return this.size === 0;
  }
}

const q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
console.log(q.dequeue()); // 1
console.log(q.dequeue()); // 2
q.enqueue(4);
console.log(q.dequeue()); // 3

Linked-List Queue (True O(1))

A singly-linked list with head and tail pointers gives true O(1) for both operations — no amortization required. The tail pointer lets you append without traversal.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedQueue {
  #head = null;
  #tail = null;
  #size = 0;

  enqueue(value) {
    const node = new Node(value);
    if (this.#tail) this.#tail.next = node;
    this.#tail = node;
    if (!this.#head) this.#head = node;
    this.#size++;
  }

  dequeue() {
    if (!this.#head) throw new Error("Queue is empty");
    const value = this.#head.value;
    this.#head = this.#head.next;
    if (!this.#head) this.#tail = null; // queue became empty
    this.#size--;
    return value;
  }

  peek() {
    if (!this.#head) throw new Error("Queue is empty");
    return this.#head.value;
  }

  get size() { return this.#size; }
  isEmpty() { return this.#size === 0; }
}

Comparison

Implementation	enqueue	dequeue	Space
Array (shift)	O(1)	O(n)	O(n)
Two stacks	O(1)	O(1) amortized	O(n)
Linked list	O(1)	O(1) true	O(n)

The two-stack approach works well when memory layout matters (arrays have better cache locality). The linked list is preferable when worst-case latency must be bounded.

Up Next

A deque (double-ended queue) generalises the queue to allow push and pop at both ends — enabling the sliding-window maximum trick.

Deques →