Queue and stack

A queue gives items back in the order they arrived (FIFO). A stack gives back the most recent first (LIFO).

How it works

Stack: a JS array with push and pop, both O(1). Queue: a JS array with shift() is O(n), because every element moves down one slot. Instead, keep a head index that moves forward, and occasionally slice off the used front. A deque (double-ended) supports both ends, usually as a ring buffer.

Reach for it when

• Queue: BFS, task processing in order, buffering
• Stack: matching brackets, undo, DFS without recursion, 'most recent'
• Monotonic stack: next greater element

Copyclass Queue {
  items = [];
  head = 0; // index of the front; avoids O(n) shift()
  enqueue(x) {
    this.items.push(x);
  }
  dequeue() {
    if (this.head === this.items.length) return undefined;
    const x = this.items[this.head++];
    if (this.head > 1024 && this.head * 2 > this.items.length) {
      // reclaim memory now and then
      this.items = this.items.slice(this.head);
      this.head = 0;
    }
    return x;
  }
  peek() {
    return this.items[this.head];
  }
  get size() {
    return this.items.length - this.head;
  }
}
// Stack needs no class: push() and pop() on an array are both O(1).

Traps

• shift() inside a BFS loop makes it O(n²) on big inputs.
• Recursion is a hidden stack. Deep recursion overflows; switch to an explicit stack.