Lesson 09 of 2415 min read

Stacks

Last in, first out. An array with discipline, and the key to matching brackets, evaluating expressions and the monotonic-stack trick.

By the end: Recognise when a problem is secretly asking for a stack.

A stack is a pile. You add to the top and you remove from the top, and you cannot reach anything underneath. Last in, first out.

In JavaScript you do not need a class: an array with only push and pop is a stack, and both are O(1).

An array is already a stack

1
2
3
4
5
6
7
8
9
10
11
12const stack = [];

stack.push('a');
stack.push('b');
stack.push('c');
console.log('after three pushes:', stack);

console.log('peek (do not remove):', stack[stack.length - 1]);
console.log('pop:', stack.pop(), '→', stack);
console.log('pop:', stack.pop(), '→', stack);
console.log('empty?', stack.length === 0);
console.log('pop on empty gives:', [].pop());

Output

Matching brackets

The classic. Push every opening bracket. On a closing bracket, the top of the stack must be its partner. At the end the stack must be empty.

Valid parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function isValid(s) {
  const partner = { ')': '(', ']': '[', '}': '{' };
  const stack = [];

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (ch in partner) {
      // Nothing to match, or the wrong thing on top.
      if (stack.pop() !== partner[ch]) return false;
    }
  }
  return stack.length === 0;    // leftover openers means unbalanced
}

for (const s of ['()', '()[]{}', '(]', '([)]', '{[]}', '(', '', ']']) {
  console.log(JSON.stringify(s).padEnd(10), isValid(s));
}

Output

A stack as a running record

Simplify a path, and undo-style processing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// Unix path simplification: '..' pops, '.' and '' are ignored.
function simplifyPath(path) {
  const stack = [];
  for (const part of path.split('/')) {
    if (part === '' || part === '.') continue;
    if (part === '..') stack.pop();
    else stack.push(part);
  }
  return '/' + stack.join('/');
}

console.log(simplifyPath('/home/'));                 // /home
console.log(simplifyPath('/../'));                   // /
console.log(simplifyPath('/home//foo/'));            // /home/foo
console.log(simplifyPath('/a/./b/../../c/'));        // /c

// Backspace-aware string comparison: '#' deletes the previous character.
function applyBackspaces(s) {
  const out = [];
  for (const ch of s) {
    if (ch === '#') out.pop();
    else out.push(ch);
  }
  return out.join('');
}
console.log(applyBackspaces('ab#c'), '===', applyBackspaces('ad#c'));

Output

Evaluating expressions

Reverse Polish notation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function evalRPN(tokens) {
  const stack = [];
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),   // truncate toward zero, not floor
  };

  for (const t of tokens) {
    if (t in ops) {
      const b = stack.pop();            // NOTE the order: b comes off first
      const a = stack.pop();
      stack.push(ops[t](a, b));
    } else {
      stack.push(Number(t));
    }
  }
  return stack.pop();
}

console.log(evalRPN(['2', '1', '+', '3', '*']));                    // 9
console.log(evalRPN(['4', '13', '5', '/', '+']));                   // 6
console.log(evalRPN(['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+']));  // 22
console.log('truncation matters:', evalRPN(['7', '-3', '/']), '(not -3)');

Output

The monotonic stack

This is the technique worth real study. A monotonic stack keeps its contents in sorted order by discarding anything that breaks the order. It answers "for each element, what is the next one greater than it?" in a single pass.

The insight: when you find a bigger element, it is the answer for everything currently waiting on the stack that is smaller than it. So you pop them all and resolve them at once. Each element is pushed once and popped at most once, so the whole thing is O(n) even though there is an inner loop.

Next greater element, with a trace

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function nextGreater(nums) {
  const answer = new Array(nums.length).fill(-1);
  const stack = [];    // holds INDICES whose answer is still unknown

  for (let i = 0; i < nums.length; i++) {
    // nums[i] is the answer for every smaller value still waiting.
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      answer[idx] = nums[i];
      console.log(`  ${nums[i]} at index ${i} resolves index ${idx} (value ${nums[idx]})`);
    }
    stack.push(i);
  }
  // Anything left never found a greater element; it stays -1.
  return answer;
}

console.log('input: [2, 1, 2, 4, 3]');
console.log('result:', nextGreater([2, 1, 2, 4, 3]));
console.log('');
console.log('input: [5, 4, 3, 2, 1]  (decreasing: nothing resolves)');
console.log('result:', nextGreater([5, 4, 3, 2, 1]));

Output

Daily temperatures: how many days until it gets warmer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function daysUntilWarmer(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];

  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop();
      answer[j] = i - j;          // the distance, which is why we stored indices
    }
    stack.push(i);
  }
  return answer;
}

console.log(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]));   // [1,1,4,2,1,1,0,0]
console.log(daysUntilWarmer([30, 40, 50, 60]));                    // [1,1,1,0]
console.log(daysUntilWarmer([30, 60, 90]));                        // [1,1,0]

Output

Largest rectangle in a histogram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// For each bar, the widest rectangle of that height extends until a shorter bar
// on each side. A monotonic increasing stack finds both boundaries in one pass.
function largestRectangle(heights) {
  const stack = [];          // indices, heights increasing
  let best = 0;
  // The trailing 0 forces every remaining bar to resolve at the end.
  const h = [...heights, 0];

  for (let i = 0; i < h.length; i++) {
    while (stack.length > 0 && h[stack[stack.length - 1]] >= h[i]) {
      const height = h[stack.pop()];
      // Left boundary is whatever is now on top; if empty, the whole prefix.
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }
    stack.push(i);
  }
  return best;
}

console.log(largestRectangle([2, 1, 5, 6, 2, 3]));   // 10, the 5 and 6 together
console.log(largestRectangle([2, 4]));               // 4
console.log(largestRectangle([1, 1, 1, 1]));         // 4
console.log(largestRectangle([5]));                  // 5

Output

Two stacks

A stack that also reports its minimum in O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class MinStack {
  #main = [];
  #mins = [];      // the minimum of everything at or below each position

  push(x) {
    this.#main.push(x);
    const currentMin = this.#mins.length === 0 ? x : Math.min(x, this.#mins[this.#mins.length - 1]);
    this.#mins.push(currentMin);
    return this;
  }

  pop() { this.#mins.pop(); return this.#main.pop(); }
  top() { return this.#main[this.#main.length - 1]; }
  getMin() { return this.#mins[this.#mins.length - 1]; }
}

const ms = new MinStack();
ms.push(-2).push(0).push(-3);
console.log('min:', ms.getMin());        // -3
ms.pop();
console.log('after pop, top:', ms.top(), '| min:', ms.getMin());   // 0, -2

Output

The trick is that you never need to search for the minimum, because you recorded it at the moment each element was pushed. Popping restores the previous minimum for free. This "keep a parallel stack of running answers" idea generalises.

A queue built from two stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class QueueFromStacks {
  #inbox = [];
  #outbox = [];

  enqueue(x) { this.#inbox.push(x); return this; }

  dequeue() {
    if (this.#outbox.length === 0) {
      // Pouring reverses the order, turning LIFO into FIFO.
      while (this.#inbox.length > 0) this.#outbox.push(this.#inbox.pop());
    }
    return this.#outbox.pop();
  }

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

const q = new QueueFromStacks();
q.enqueue(1).enqueue(2).enqueue(3);
console.log(q.dequeue(), q.dequeue());   // 1 2, in arrival order
q.enqueue(4);
console.log(q.dequeue(), q.dequeue());   // 3 4

Output

Recursion is a stack

Every recursive function is using the call stack. Which means any recursion can be rewritten with an explicit stack, and that is how you avoid a stack overflow on deep inputs.

The same traversal, recursive and iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24const tree = { val: 1, left: { val: 2, left: { val: 4 }, right: { val: 5 } }, right: { val: 3 } };

function recursive(node, out = []) {
  if (!node) return out;
  out.push(node.val);
  recursive(node.left, out);
  recursive(node.right, out);
  return out;
}

function iterative(root) {
  const out = [], stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    out.push(node.val);
    stack.push(node.right);   // push right FIRST so left is processed first
    stack.push(node.left);
  }
  return out;
}

console.log('recursive:', recursive(tree));
console.log('iterative:', iterative(tree));

Output

Your turn: four stack problems

removeAdjacentDuplicates(s) — repeatedly delete two identical neighbouring characters. 'abbaca' becomes 'ca'. One pass with a stack.
decodeString(s) — expand '3[a2[c]]' into 'accaccacc'. Two stacks: one for counts, one for partial strings.
asteroidCollide(asteroids) — positive numbers move right, negative move left, larger survives, equal destroys both. Return the survivors.
nextGreaterCircular(nums) — next greater element, but the array wraps around. Hint: loop twice over the indices using i % n, and only push during the first pass.

Editable. Fill them in, then run.

function removeAdjacentDuplicates(s) {
  // push, and pop instead when it matches the top
}

function decodeString(s) {
  // countStack and stringStack; on ']' pop both and repeat
}

function asteroidCollide(asteroids) {
  // a right-mover on the stack meets a left-mover coming in
}

function nextGreaterCircular(nums) {
  // for (let i = 0; i < 2 * n; i++) use nums[i % n]
}

console.log(removeAdjacentDuplicates('abbaca'));       // 'ca'
console.log(removeAdjacentDuplicates('azxxzy'));       // 'ay'
console.log(decodeString('3[a]2[bc]'));                // 'aaabcbc'
console.log(decodeString('3[a2[c]]'));                 // 'accaccacc'
console.log(asteroidCollide([5, 10, -5]));             // [5,10]
console.log(asteroidCollide([8, -8]));                 // []
console.log(asteroidCollide([10, 2, -5]));             // [10]
console.log(nextGreaterCircular([1, 2, 1]));           // [2,-1,2]
console.log(nextGreaterCircular([5, 4, 3, 2, 1]));     // [-1,5,5,5,5]

Output

Recap

An array with only push and pop is a stack, and both are O(1).
Use one when the most recent unfinished item is the next one you need: brackets, paths, undo, expressions.
A monotonic stack answers "next greater" style questions in O(n), because each index is pushed and popped at most once.
Store indices rather than values, and add a sentinel to force the final cleanup inside the main loop.
A parallel stack of running answers gives O(1) minimum; two stacks give an amortized O(1) queue; and any recursion can be rewritten with an explicit stack.

Matching brackets

A stack as a running record

Evaluating expressions

The monotonic stack

Two stacks

Recursion is a stack

Your turn: four stack problems

Recap

New writing, when it lands.