Stacks & queues

The only thing that actually differs between them

Stacks in JS — just use an array

const stack = [];
stack.push(1);
stack.push(2);
stack.pop();      // 2 — removes from the END, O(1)
stack[stack.length - 1]; // peek without removing

// an O(1)-amortized queue using two stacks
class Queue {
  #inStack = [];
  #outStack = [];

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

  dequeue() {
    if (this.#outStack.length === 0) {
      while (this.#inStack.length) {
        this.#outStack.push(this.#inStack.pop());
      }
    }
    return this.#outStack.pop();
  }
}

Each element gets moved from inStack to outStack at most once ever — so across n operations the total work is O(n), even though a single dequeue can occasionally cost O(n). That's the "amortized O(1)" argument, same shape as array.push()'s resizing.

The pattern stacks solve: matching and undoing

// valid parentheses — the canonical stack interview question
function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if (c === "(" || c === "[" || c === "{") {
      stack.push(c);
    } else {
      if (stack.pop() !== pairs[c]) return false;
    }
  }
  return stack.length === 0;
}

Watch the stack fill and drain, step by step

s = "{[()]}":

Stack empty at the end → valid. If any close bracket ever popped the wrong open bracket, or the stack ran out of elements to pop, or the stack still had leftover opens at the end — any of those means invalid. All three failure modes are just as common in interview test cases as the happy path, so trace through them mentally too.

The tell: whenever a problem needs "the most recent unmatched thing" — an open bracket, an undo history, the calling function to return to — a stack is the structure that naturally tracks it, because LIFO is "most recent first."

Min-stack — the classic "track extra state per level" question

A regular stack can't answer "what's the minimum value currently in me" in better than O(n) — you'd have to scan everything. The fix: keep a second stack that tracks the running minimum at each level, so it shrinks in lockstep with the main stack.

class MinStack {
  #stack = [];
  #minStack = []; // minStack[i] = the min among stack[0..i]

  push(x) {
    this.#stack.push(x);
    const currentMin = this.#minStack.length
      ? Math.min(x, this.#minStack[this.#minStack.length - 1])
      : x;
    this.#minStack.push(currentMin);
  }

  pop() {
    this.#minStack.pop();
    return this.#stack.pop();
  }

  getMin() {
    return this.#minStack[this.#minStack.length - 1]; // O(1)
  }
}

minStack pops in lockstep with stack, so it never has stale data — the minimum "at this depth" is always exactly minStack's top. This "shadow stack that mirrors the main one, tracking one extra fact" idea generalizes to max, running sum, and similar per-level queries.

Evaluating expressions — the other classic stack application

Postfix (Reverse Polish) notation — "3 4 +" instead of "3 + 4" — needs no parentheses and no operator precedence rules, because a stack evaluates it directly: push numbers, and when you hit an operator, pop two operands, apply it, push the result back.

function evalRPN(tokens) {
  const stack = [];
  const ops = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "*": (a, b) => a * b,
    "/": (a, b) => Math.trunc(a / b),
  };
  for (const token of tokens) {
    if (token in ops) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(ops[token](a, b)); // order matters for - and /
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}
// evalRPN(["3","4","+","2","*"]) → (3+4)*2 → 14

Deques — a queue that can push/pop from both ends

A deque (double-ended queue) supports O(1) add/remove at both the front and back. It's the structure behind the advanced "sliding window maximum" pattern (kept as a monotonic deque of candidate maximums) and behind efficient BFS variants that need to push to the front sometimes (0-1 BFS). In JS there's no built-in deque — people either accept an array's O(n) front operations at small scale, or reach for a small class backed by two stacks (same two-stack trick as the queue above, extended to push at both ends) or a circular buffer.

Circular queue — a fixed-size ring buffer

class CircularQueue {
  #data; #front = 0; #size = 0;
  constructor(capacity) { this.#data = new Array(capacity); }

  enqueue(x) {
    if (this.#size === this.#data.length) throw new Error("full");
    const rear = (this.#front + this.#size) % this.#data.length;
    this.#data[rear] = x;
    this.#size++;
  }

  dequeue() {
    if (this.#size === 0) throw new Error("empty");
    const x = this.#data[this.#front];
    this.#front = (this.#front + 1) % this.#data.length;
    this.#size--;
    return x;
  }
}

This is what a production task queue or a ring buffer for streaming data actually looks like — fixed memory, no allocation churn, and the modulo (%) is what makes "wrap back to the start" free.

The pattern queues solve: process in the order things arrived

Queues are the backbone of breadth-first search (its own chapter later): visit the closest things first, which requires processing in the exact order they were discovered — FIFO, not LIFO.

// level-order traversal shape — the queue IS the "current frontier"
function bfsShape(start, getNeighbors) {
  const queue = [start];
  const visited = new Set([start]);
  while (queue.length) {
    const node = queue.shift(); // front — fine at small scale; use a real
                                    queue/deque for large inputs, per the warning above
    for (const next of getNeighbors(node)) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
}

Recognizing which one you need

• Stack: matching pairs, undo/redo, "closest unmatched," depth-first exploration, evaluating expressions
• Queue: breadth-first exploration, "process in arrival order," task scheduling
• Deque: need to add/remove at both ends — sliding-window maximum, 0-1 BFS
• Circular queue: fixed-capacity buffering — rate limiters, streaming windows, producer/consumer queues
• Min-stack (or max-stack): "track the running min/max as things get pushed/popped"
• If a problem says "next greater/smaller element," that's usually a monotonic stack — covered in the advanced tier