Queues and circular buffers

A queue adds at the back and removes from the front: enqueue, dequeue, peek. It is the structure behind job processing, request handling, breadth-first search, and every printer that has ever kept you waiting.

The trap

const queue = [];
queue.push(job);        // O(1) — fine
queue.shift();          // O(n) — every remaining element moves left

Draining a million-job array with shift() is O(n²). It works in a demo and dies in production.

Two ends, two pointers

Keep a head index instead of moving the data:

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

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

  dequeue() {
    if (this.#head >= this.#items.length) return undefined;

    const value = this.#items[this.#head++];

    // Reclaim space once the dead prefix outweighs the live part.
    if (this.#head > 32 && this.#head * 2 >= this.#items.length) {
      this.#items = this.#items.slice(this.#head);
      this.#head = 0;
    }

    return value;
  }

  get size() { return this.#items.length - this.#head; }
}

O(1) amortised at both ends. A linked list with head and tail pointers gives the same guarantee without the compaction, at the cost of a node per item.

Circular buffers

When capacity is fixed, wrap around a preallocated array with modular arithmetic. No allocation, no garbage, constant memory:

class RingBuffer {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.head = 0;
    this.size = 0;
  }

  push(value) {
    const at = (this.head + this.size) % this.capacity;
    this.items[at] = value;

    if (this.size === this.capacity) this.head = (this.head + 1) % this.capacity;  // overwrite oldest
    else this.size++;
  }

  toArray() {
    return Array.from({ length: this.size }, (_, i) => this.items[(this.head + i) % this.capacity]);
  }
}

This is how audio buffers, log tailers, metric windows and network stacks hold "the last n things" without ever allocating.

Queues you will meet by name

• Priority queue — served by importance, not arrival. That is a heap, three chapters on.
• Deque — both ends open, the basis of the sliding window maximum.
• Blocking queue — the producer–consumer backbone of concurrent systems.
• Message queue — the same contract across a network, with durability added.