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 (pairs[c] === undefined || stack.pop() !== pairs[c]) return false; // any other character is not a bracket
    }
  }
  return stack.length === 0;
}

Dry run: isValid("{[()]}")

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));
    }
  }
  const result = stack.pop();
  return result === 0 ? 0 : result; // -0 === 0, so a -0 result comes back as 0 (Math.trunc(-1 / 2) is -0)
}
// evalRPN(["3","4","+","2","*"]) → (3+4)*2 → 14

Infix expressions: Basic Calculator II with one stack

Real expressions are written infix, "2-3*4+5", and then precedence matters: multiplication binds tighter than addition, so you cannot just fold left to right. Reverse Polish notation avoided the problem by moving the precedence into the notation. For infix, the trick is to see the expression as a sum of terms. A term is numbers joined by * and /, and the terms are joined by + and -. Keep a stack of finished, signed terms. When a number is complete, look at the operator that came before it: after + or - the number starts a new term (push it, negated for -); after * or / it belongs to the term on top of the stack, so combine it with that term immediately. At the end, the answer is the sum of the stack.

function calculate(s) {                         // digits, + - * /, spaces; "/" truncates toward zero
  const stack = [];
  let num = 0;
  let op = "+";                                 // the operator BEFORE the number being read
  for (let i = 0; i <= s.length; i++) {
    const c = i < s.length ? s[i] : "+";        // a sentinel "+" at the end flushes the last number
    if (c >= "0" && c <= "9") { num = num * 10 + (c.charCodeAt(0) - 48); continue; }
    if (c === " ") continue;                    // a space never ends a number
    if (op === "+") stack.push(num);
    else if (op === "-") stack.push(-num);
    else if (op === "*") stack.push(stack.pop() * num);
    else stack.push(Math.trunc(stack.pop() / num));
    op = c;
    num = 0;
  }
  return stack.reduce((sum, term) => sum + term, 0);
}

Dry run: calculate("2-3*4+5")

The sum of the stack is 2 − 12 + 5 = −5. Each character is read once, so time is O(n), and the stack holds at most one entry per term, O(n) space (O(1) if you keep only the sum so far and the last term). The function was checked on 5,000 random expressions against a reference that applies the precedence rules by hand. The details people lose points on: a multi-digit number is built digit by digit (num * 10 + digit); a space must be skipped before the operator test, or it would end a number early; the last number has no operator after it, hence the sentinel; and division must use Math.trunc, because -7 / 2 is -3.5 and the problem wants -3, while Math.floor would give -4.

Parentheses: save the outer state, then combine

Add parentheses (and only + and -, with a minus allowed at the start or right after () and the expression nests. A parenthesised group is a sub-expression whose value gets added with the sign that stood in front of it: 2-(5-6) is 2 + (−1) × (5 − 6). So when you meet (, the outer expression is on hold. Push what it needs to resume, its running result and the sign in front of the bracket, and start the inner expression from scratch. At ), finish the inner value and fold it back:

function calculateWithParens(s) {
  const stack = [];                              // holds [result, sign] pairs of the outer expressions on hold
  let result = 0, sign = 1, num = 0;
  for (const c of s) {
    if (c >= "0" && c <= "9") {
      num = num * 10 + (c.charCodeAt(0) - 48);
    } else if (c === "+" || c === "-") {
      result += sign * num;                      // the number before this operator is complete
      num = 0;
      sign = c === "+" ? 1 : -1;
    } else if (c === "(") {
      stack.push(result, sign);                  // put the outer expression on hold ...
      result = 0;                                // ... and start the inner one from scratch
      sign = 1;
    } else if (c === ")") {
      result += sign * num;                      // finish the inner expression
      num = 0;
      const outerSign = stack.pop();             // pushed last, so popped first
      const outerResult = stack.pop();
      result = outerResult + outerSign * result;
    }
  }
  return result + sign * num;                    // the final number has no operator after it
}

Dry run: calculateWithParens("2-(5-6)")

The end adds sign * num = −1 × 0 and the answer is 3. A leading minus works without special handling: for "-(2+3)" the first - sets sign = −1 after adding 0, the bracket saves [0, −1], and the close gives 0 + (−1) × 5 = −5. The function matched eval on 5,000 random well-formed expressions with nested brackets, spaces and leading minus signs. Mistakes to avoid: popping the pair in the wrong order, not resetting sign to 1 and result to 0 after (, and forgetting the last sign * num at the end. With * and / as well as brackets (Basic Calculator III) the same idea of saving state at ( combines with the term stack of the previous section.

A stack of states for nesting: decode string

"3[a2[c]]" means "three copies of (a followed by two copies of c)", which expands to accaccacc. The nesting is the same put-on-hold structure as the parentheses above. When you meet [, what you were building and how many times the bracket will repeat must wait: push the pair [textSoFar, repeatCount] and start a fresh current string. At ], pop the pair and append the finished inner text, repeated, to the saved text.

function decodeString(s) {
  const stack = [];                              // pairs: [text before the bracket, repeat count]
  let current = "";
  let count = 0;
  for (const c of s) {
    if (c >= "0" && c <= "9") count = count * 10 + (c.charCodeAt(0) - 48);   // counts can have several digits
    else if (c === "[") { stack.push([current, count]); current = ""; count = 0; }
    else if (c === "]") { const [before, times] = stack.pop(); current = before + current.repeat(times); }
    else current += c;
  }
  return current;
}

Dry run: decodeString("3[a2[c]]")

Checked against a recursive parser on 2,000 random nested inputs. The cost is proportional to the length L of the decoded string, since every character of the output is produced by repeat or a concatenation. Strictly, each closing bracket rebuilds the string for its level, so a chain of many brackets around a long string can do up to O(L × nesting depth) copying, though it is normally quoted as O(L). Traps: a count like 10 is two digits; the count must be reset at [ (and is naturally zero after ]); letters may sit before, between and after brackets ("2[abc]3[cd]ef"), which is why the text before a bracket is part of what you save.

Collision simulation: asteroid collision

Asteroids sit in a row. Each number is its size, positive means moving right and negative means moving left, all at the same speed. When two meet the smaller explodes, and if they are equal both do. What is left? Collisions can only involve a right-mover with a left-mover coming after it, and the pair that collides is always the most recent right-mover still alive against the newcomer, which is the top of a stack. A newcomer that moves left may destroy several right-movers in a row, so the collision step is a loop:

function asteroidCollision(asteroids) {
  const stack = [];                                       // survivors so far, in order
  for (const a of asteroids) {
    let alive = true;
    while (alive && a < 0 && stack.length && stack[stack.length - 1] > 0) {
      const top = stack[stack.length - 1];                // a right-mover meets a left-mover
      if (top < -a) stack.pop();                         // top explodes, a keeps going: check the next one
      else if (top === -a) { stack.pop(); alive = false; }  // both explode
      else alive = false;                                  // a explodes
    }
    if (alive) stack.push(a);                              // only survivors are pushed
  }
  return stack;
}

Dry run: [5, 10, −12, −3, 4]

Every asteroid is pushed at most once and popped at most once, so the loop is O(n) amortized. Checked against a brute-force simulation (repeatedly resolve the leftmost right-mover/left-mover neighbour pair) on 8,000 random arrays. Pitfalls: a collision needs top > 0 and a < 0 (a left-mover followed by a right-mover are moving apart); a while, not an if; both explode on a tie; and push the newcomer only if it survived.

A stack as a text editor: backspaces and adjacent duplicates

A stack of characters is exactly the model of a text field where you can only edit the end: typing pushes, backspace pops. That is the whole of "Backspace String Compare", where # means backspace:

function backspaceCompare(s, t) {
  return build(s) === build(t);
}

function build(text) {
  const stack = [];
  for (const c of text) {
    if (c === "#") stack.pop();                 // backspace on an empty field does nothing
    else stack.push(c);
  }
  return stack.join("");
}
// build("ab#c") → "ac"     build("a##c") → "c"     backspaceCompare("ab#c", "ad#c") → true

O(n) time and space. The O(1)-space version scans both strings from the back with a skip counter (the two-pointers chapter). Mind that in JavaScript [].pop() returns undefined and is harmless; in languages where popping an empty stack throws, guard it.

The same shape solves "remove adjacent duplicates": delete any two equal neighbours, and keep deleting, since a removal can create a new pair ("abba" becomes "aa" becomes nothing). Rescanning the string after each removal costs O(n²) in the worst case. With a stack, the character on top after a pop is the new neighbour, so one pass is enough. For the variant that removes k equal neighbours, store a run length with each entry:

function removeDuplicates(s) {                       // remove pairs of equal neighbours
  const stack = [];
  for (const c of s) {
    if (stack.length && stack[stack.length - 1] === c) stack.pop();
    else stack.push(c);
  }
  return stack.join("");
}

function removeDuplicatesK(s, k) {                   // remove runs of k equal neighbours
  const stack = [];                                  // entries: [character, length of its current run]
  for (const c of s) {
    if (stack.length && stack[stack.length - 1][0] === c) {
      if (++stack[stack.length - 1][1] === k) stack.pop();
    } else {
      stack.push([c, 1]);
    }
  }
  return stack.map(([c, n]) => c.repeat(n)).join("");
}

Dry run: removeDuplicates("abbaca") and removeDuplicatesK("deeedbbcccbdaa", 3)

The results are "ca" and "aa". Both functions matched a repeated-regex-replacement reference on 5,000 random strings (for k = 2, 3 and 4). Time and space are O(n); the stack never holds more characters than have been read. Note how removing eee in the k = 3 trace made the two ds adjacent: after the pop, the top of the stack was already the right neighbour, with no rescanning.

Simplify path: a stack of directory names

Turn a Unix absolute path such as "/a/./b/../../c/" into its canonical form. Walking a path is moving up and down a directory stack: a name goes in, .. comes out, . and empty segments (from // or a trailing slash) do nothing. Split on / and process the segments:

function simplifyPath(path) {
  const stack = [];
  for (const part of path.split("/")) {
    if (part === "" || part === ".") continue;   // empty segment or "stay here"
    if (part === "..") stack.pop();              // go up; at the root there is nothing to pop
    else stack.push(part);                       // a real name, including "..." or "x.y"
  }
  return "/" + stack.join("/");                  // an empty stack gives "/"
}

The result is "/c". This matched path.posix.normalize (with its trailing slash removed) on 5,000 random paths made of a, b, ., .., ..., x.y, empty segments and doubled slashes. The traps: .. at the root must stay at the root (popping an empty array is safe in JavaScript, so it already does), "..." is an ordinary directory name, and the empty result is "/", not "". O(n) time and space.

Remove K digits: the stack that keeps itself sorted

Given a number as a string, remove exactly k digits to make the result as small as possible: "1432219" with k = 3 gives "1219". The greedy fact: a more significant digit decides the size, so scanning left to right, the first digit that is larger than the one after it is the best one to delete. Doing that repeatedly is a stack: while the digit on top is bigger than the new digit and deletions remain, pop it. While deletions remain, the stack stays non-decreasing from bottom to top.

function removeKdigits(num, k) {
  const stack = [];
  for (const d of num) {
    while (k > 0 && stack.length && stack[stack.length - 1] > d) {
      stack.pop();                                // a bigger digit before a smaller one: delete the bigger
      k--;
    }
    stack.push(d);
  }
  while (k > 0) { stack.pop(); k--; }             // still owed deletions: drop from the end (largest digits)
  const result = stack.join("").replace(/^0+/, "");   // no leading zeros
  return result === "" ? "0" : result;
}

The function matched an exhaustive search over every way of keeping n − k digits on 3,000 random inputs. The edge cases are the whole difficulty: removeKdigits("10200", 1) is "200" (leading zeros stripped), removeKdigits("10", 2) is "0" (nothing left means zero), and removeKdigits("112", 1) is "11": with no descent the leftover deletion comes off the end. This is a monotonic stack, the idea the next tier generalises (next greater element, histogram areas, lexicographically smallest subsequences); here it is enough to see that "pop while the top is worse than the newcomer" is a stack pattern in its own right.

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; for large inputs use a real queue/deque (see the warning above)
    for (const next of getNeighbors(node)) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
}

A stack built from queues

The earlier two-stack queue has a mirror image that interviewers also ask for: build a stack using only queue operations (add to the back, remove from the front, size, empty check). A queue hands back the oldest element first, a stack the newest. The trick is to make the newest element the oldest. After adding x to the back, rotate the queue by moving the size − 1 elements that were already there from the front to the back, one by one. Now x is at the front and the older elements follow it in reverse arrival order, so the front of the queue is always the top of the stack.

class MyStack {
  constructor() { this.q = []; }                 // used ONLY as a queue: push = enqueue, shift = dequeue

  push(x) {
    this.q.push(x);                              // x is at the back
    for (let i = this.q.length - 1; i > 0; i--) {
      this.q.push(this.q.shift());               // rotate every older element behind x
    }
  }

  pop() { return this.q.shift(); }               // the front is the newest
  top() { return this.q[0]; }
  empty() { return this.q.length === 0; }
}

push costs O(n), pop, top and empty cost O(1). The alternative is to push in O(1) and do the rotation inside pop (O(n) for that), which is the better choice when pushes outnumber pops. Unlike the two-stack queue, no amortised trick makes both operations cheap here, so say which one you chose to make slow. The code matched a plain array used as a stack over 500 random sequences of pushes and pops. In this problem shift stands for the queue's O(1) dequeue that the problem statement gives you; in real JavaScript, remember the warning above that shift on a big array is O(n).

Iterative DFS: an explicit stack instead of the call stack

Depth-first search is recursion on a graph, and recursion is a stack the language manages for you. A graph or tree that is deep (a path of 200,000 nodes) overflows it, and "do it iteratively" is a standard follow-up (the recursion chapter showed the same conversion). Put the nodes to visit on your own stack. Three details decide whether the order matches the recursive version:

• Mark a node visited when you pop it (when you actually visit it), not when you push it. A node can be pushed by two different neighbours before it is ever visited, so on a pop, skip it if it is already visited.
• Push the neighbours in reverse, so that the first neighbour ends up on top and is popped first, as it would be in the recursive loop.
• Only push neighbours that are not yet visited; it keeps the stack smaller.

function dfsIterative(graph, start) {             // graph: node → array of neighbours
  const order = [];
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;               // stale entry: already reached another way
    visited.add(node);
    order.push(node);
    for (let i = graph[node].length - 1; i >= 0; i--) {   // reverse, so the first neighbour pops first
      if (!visited.has(graph[node][i])) stack.push(graph[node][i]);
    }
  }
  return order;
}

Dry run: graph A → [B, C], B → [C], C → []

The order is A, B, C, the same as the recursive DFS. This matched the recursive version on 3,000 random undirected graphs, and a 200,000-node path that makes the recursive version throw RangeError is handled in a loop. Time is O(V + E). The stack can hold stale duplicates, so its size is bounded by the number of edges rather than the number of nodes. The tempting alternative, marking on push, still visits every reachable node exactly once, which is all that is needed for reachability or counting components, but it is not DFS order: it can differ from the recursive order even when the neighbours are pushed in reverse: for A → [B, C, D] and B → [D] the recursive order is A, B, D, C, but marking on push gives A, B, C, D (and with the neighbours pushed in their listed order, the small graph above would give A, C, B).

The same idea turns a recursive tree traversal into a loop. For inorder (left, node, right), go as far left as possible while stacking the nodes you pass; the node on top is the next one to visit; then continue with its right subtree.

function inorder(root) {
  const out = [];
  const stack = [];
  let node = root;
  while (node !== null || stack.length) {
    while (node !== null) { stack.push(node); node = node.left; }   // dive left, remembering the way back
    node = stack.pop();
    out.push(node.val);                                              // everything to its left is done
    node = node.right;
  }
  return out;
}

For the tree 1 → (right) 2 → (left) 3, the loop stacks 1, visits 1, moves to 2, stacks 2 and 3, visits 3, finds no right child, pops 2 and visits it: the result is [1, 3, 2]. It matched the recursive definition on 1,000 random trees and ran on a 200,000-node left chain that overflows the recursive one. The loop condition needs both halves: node !== null keeps it going while there is a subtree to enter, stack.length while there are nodes still waiting to be visited.

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"
• Stack of saved states: nesting with ( ) or [ ] where the outer context must wait (calculator with brackets, decode string)
• Stack as a text editor: deletions that can expose new neighbours (backspaces, adjacent duplicates, remove K digits, simplify path)
• Stack of survivors: items that interact with only the most recent one (asteroid collision)
• Explicit stack: "do it iteratively", or a depth that would overflow the call stack (DFS, tree traversals)
• If a problem says "next greater/smaller element," that's usually a monotonic stack — covered in the advanced tier