Stacks

Think of it like this

Imagine a stack of plates in a cafeteria. You always place a new plate on top, and you always take a plate from top. You cannot grab a plate from the middle without removing everything above it first.

This is LIFO: Last In, First Out. The last thing you put in is the first thing you get out.

Cafeteria stack:         Stack operations:
 
   [plate 3] ← TOP           Push(plate) → adds to top
   [plate 2]                 Pop()       → removes from top
   [plate 1]                 Peek()      → reads top without removing
   ─────────

Every time your code calls a function, the runtime pushes a stack frame onto the call stack. When the function returns, it pops. This is why infinite recursion causes a "stack overflow".

Visualizing Push & Pop

Start:    Push 5:   Push 2:   Push 8:   Pop:      Pop:
          │  5  │   │  2  │   │  8  │   │  2  │   │  5  │
empty     │     │   │  5  │   │  2  │   │  5  │   │     │
          ─────     ─────     ─────     ─────     ─────
                    TOP=5     TOP=8     TOP=2  ← returned 8
                                                 returned 2 next

Time Complexity

Operation	Complexity	Why
Push (add to top)	O(1)	Just append to end of array
Pop (remove top)	O(1)	Just remove last element
Peek (read top)	O(1)	Access last element by index
Search	O(n)	Must scan the whole stack
isEmpty	O(1)	Check length

Space Complexity: O(n)

Implementation

class Stack {
  #data = []; // private field
 
  push(val)  { this.#data.push(val); }
  pop()      { return this.#data.pop() ?? null; } // null if empty
  peek()     { return this.#data[this.#data.length - 1] ?? null; }
  isEmpty()  { return this.#data.length === 0; }
  size()     { return this.#data.length; }
  toArray()  { return [...this.#data]; } // copy for debugging
 
  // Useful for monotonic stack patterns
  top() { return this.#data[this.#data.length - 1]; }
}
 
// Usage
const s = new Stack();
s.push(3);
s.push(7);
s.push(2);
console.log(s.peek()); // 2 (top, not removed)
console.log(s.pop());  // 2 (removed)
console.log(s.peek()); // 7

Stack (Browser History)

1 / 3

/home

[0]

/about

[1]

↑ TOP

User navigates to Home, then About. The current page is always at the TOP of the stack.

Core Patterns

Pattern 1 — Bracket / Parenthesis Matching

For every opening bracket, push it. For every closing bracket, pop and check if it matches. If the stack is empty at the end, all brackets were balanced.

Input:  { [ ( ) ] }
 
Step 1: {  → push  →  stack: ['{']
Step 2: [  → push  →  stack: ['{', '[']
Step 3: (  → push  →  stack: ['{', '[', '(']
Step 4: )  → pop   →  popped '(' matches ')' ✓  stack: ['{', '[']
Step 5: ]  → pop   →  popped '[' matches ']' ✓  stack: ['{']
Step 6: }  → pop   →  popped '{' matches '}' ✓  stack: []
 
Stack empty at end → VALID ✓

function isValid(s) {
  const match = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else {
      if (stack.pop() !== match[ch]) return false;
    }
  }
  return stack.length === 0;
}

Pattern 2 — Monotonic Stack (Next Greater Element)

A stack where elements are always maintained in sorted order (increasing or decreasing). When you push a new element, pop everything that violates the order — those popped elements have found their "answer".

arr = [2, 1, 5, 3, 6, 4]
Find the Next Greater Element for each position.
 
Process right-to-left, maintain decreasing stack:
 
i=5: val=4  stack=[]      → NGE=-1   stack=[4]
i=4: val=6  stack=[4]     → pop 4(4<6), NGE=-1  stack=[6]
i=3: val=3  stack=[6]     → NGE=6    stack=[6,3]
i=2: val=5  stack=[6,3]   → pop 3(3<5), NGE=6   stack=[6,5]
i=1: val=1  stack=[6,5]   → NGE=5    stack=[6,5,1]
i=0: val=2  stack=[6,5,1] → pop 1(1<2), NGE=5   stack=[6,5,2]
 
Result: [5, 5, 6, 6, -1, -1]

function nextGreaterElement(arr) {
  const result = Array(arr.length).fill(-1);
  const stack = []; // stores indices, not values
 
  for (let i = arr.length - 1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length - 1]] <= arr[i]) {
      stack.pop();
    }
    result[i] = stack.length ? arr[stack[stack.length - 1]] : -1;
    stack.push(i);
  }
  return result;
}

Pattern 3 — Undo/Redo with Two Stacks

Two stacks: one for undo history, one for redo history.

class TextEditor {
  #undoStack = [];
  #redoStack = [];
  #content = '';
 
  type(text) {
    this.#undoStack.push(this.#content); // save current state
    this.#redoStack = [];                // new action clears redo
    this.#content += text;
  }
 
  undo() {
    if (!this.#undoStack.length) return;
    this.#redoStack.push(this.#content);
    this.#content = this.#undoStack.pop();
  }
 
  redo() {
    if (!this.#redoStack.length) return;
    this.#undoStack.push(this.#content);
    this.#content = this.#redoStack.pop();
  }
}

Pattern 4 — DFS Without Recursion

Replace the call stack with an explicit stack. Push the start node, then repeatedly pop-and-push-neighbors.

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
 
  while (stack.length) {
    const node = stack.pop(); // take from top
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

Real-World Frontend Application

Browser History API: window.history.pushState() and window.history.back() use a stack. Each page push goes on top; back pops it.
Call Stack: Every JavaScript function call pushes a frame. console.trace() shows you the current stack. Async code uses the event loop to defer frames.
React DevTools: The component tree is traversed using a stack during reconciliation in React Fiber
Figma / Editors Undo: Undo/redo is two stacks — each edit pushes to undo, undo pops and pushes to redo
Webpack/Vite module resolution: DFS over the module dependency graph, stack-based to detect circular imports

Common Mistakes

Mistake	Problem	Fix
Popping an empty stack	`undefined` or error	Always check `isEmpty()` first
Using stack when queue is needed	Gets DFS when you wanted BFS (level order)	BFS needs a queue, not a stack
Comparing values not references	`if (stack.top() === node)` may fail for objects	Compare `.val` or use indices
Forgetting to clear the stack between test cases	Stale state from previous test	Reinitialize stack at start

Key Problems to Solve

#	Problem	Pattern	Difficulty
1	Valid Parentheses	Bracket matching	Easy
2	Min Stack	Stack + parallel min-stack	Easy
3	Implement Queue Using Stacks	Two stacks (push-lazy vs pop-lazy)	Easy
4	Daily Temperatures	Monotonic stack	Medium
5	Evaluate Reverse Polish Notation	Stack-based evaluator	Medium
6	Asteroid Collision	Stack simulation	Medium
7	Decode String	Stack for nested structures	Medium
8	Largest Rectangle in Histogram	Monotonic stack + area calc	Hard
9	Trapping Rain Water	Two-pointer or stack	Hard
10	Basic Calculator	Operator-precedence stack	Hard

Cafeteria stack: Stack operations: [plate 3] ← TOP Push(plate) → adds to top [plate 2] Pop() → removes from top [plate 1] Peek() → reads top without removing ─────────

Start: Push 5: Push 2: Push 8: Pop: Pop: │ 5 │ │ 2 │ │ 8 │ │ 2 │ │ 5 │ empty │ │ │ 5 │ │ 2 │ │ 5 │ │ │ ───── ───── ───── ───── ───── TOP=5 TOP=8 TOP=2 ← returned 8 returned 2 next

Operation

Complexity

Why

Push (add to top)

O(1)

Just append to end of array

Pop (remove top)

O(1)

Just remove last element

Peek (read top)

O(1)

Access last element by index

O(n)

Must scan the whole stack

isEmpty

O(1)

Check length

class Stack { #data = []; // private field push(val) { this.#data.push(val); } pop() { return this.#data.pop() ?? null; } // null if empty peek() { return this.#data[this.#data.length - 1] ?? null; } isEmpty() { return this.#data.length === 0; } size() { return this.#data.length; } toArray() { return [...this.#data]; } // copy for debugging // Useful for monotonic stack patterns top() { return this.#data[this.#data.length - 1]; } } // Usage const s = new Stack(); s.push(3); s.push(7); s.push(2); console.log(s.peek()); // 2 (top, not removed) console.log(s.pop()); // 2 (removed) console.log(s.peek()); // 7

Input: { [ ( ) ] } Step 1: { → push → stack: ['{'] Step 2: [ → push → stack: ['{', '['] Step 3: ( → push → stack: ['{', '[', '('] Step 4: ) → pop → popped '(' matches ')' ✓ stack: ['{', '['] Step 5: ] → pop → popped '[' matches ']' ✓ stack: ['{'] Step 6: } → pop → popped '{' matches '}' ✓ stack: [] Stack empty at end → VALID ✓

function isValid(s) { const match = { ')': '(', ']': '[', '}': '{' }; const stack = []; for (const ch of s) { if ('([{'.includes(ch)) { stack.push(ch); } else { if (stack.pop() !== match[ch]) return false; } } return stack.length === 0; }

arr = [2, 1, 5, 3, 6, 4] Find the Next Greater Element for each position. Process right-to-left, maintain decreasing stack: i=5: val=4 stack=[] → NGE=-1 stack=[4] i=4: val=6 stack=[4] → pop 4(4<6), NGE=-1 stack=[6] i=3: val=3 stack=[6] → NGE=6 stack=[6,3] i=2: val=5 stack=[6,3] → pop 3(3<5), NGE=6 stack=[6,5] i=1: val=1 stack=[6,5] → NGE=5 stack=[6,5,1] i=0: val=2 stack=[6,5,1] → pop 1(1<2), NGE=5 stack=[6,5,2] Result: [5, 5, 6, 6, -1, -1]

function nextGreaterElement(arr) { const result = Array(arr.length).fill(-1); const stack = []; // stores indices, not values for (let i = arr.length - 1; i >= 0; i--) { while (stack.length && arr[stack[stack.length - 1]] <= arr[i]) { stack.pop(); } result[i] = stack.length ? arr[stack[stack.length - 1]] : -1; stack.push(i); } return result; }

class TextEditor { #undoStack = []; #redoStack = []; #content = ''; type(text) { this.#undoStack.push(this.#content); // save current state this.#redoStack = []; // new action clears redo this.#content += text; } undo() { if (!this.#undoStack.length) return; this.#redoStack.push(this.#content); this.#content = this.#undoStack.pop(); } redo() { if (!this.#redoStack.length) return; this.#undoStack.push(this.#content); this.#content = this.#redoStack.pop(); } }

function dfsIterative(graph, start) { const visited = new Set(); const stack = [start]; const order = []; while (stack.length) { const node = stack.pop(); // take from top if (visited.has(node)) continue; visited.add(node); order.push(node); for (const neighbor of graph[node]) { if (!visited.has(neighbor)) stack.push(neighbor); } } return order; }

Mistake

Problem

Fix

Popping an empty stack

undefined or error

Always check isEmpty() first

Using stack when queue is needed

Gets DFS when you wanted BFS (level order)

BFS needs a queue, not a stack

Comparing values not references

if (stack.top() === node) may fail for objects

Compare .val or use indices

Forgetting to clear the stack between test cases

Stale state from previous test

Reinitialize stack at start

Problem

Pattern

Difficulty

Valid Parentheses

Bracket matching

Easy

Min Stack

Stack + parallel min-stack

Easy

Implement Queue Using Stacks

Two stacks (push-lazy vs pop-lazy)

Easy

Daily Temperatures

Monotonic stack

Medium

Evaluate Reverse Polish Notation

Stack-based evaluator

Medium

Asteroid Collision

Stack simulation

Medium

Decode String

Stack for nested structures

Medium

Largest Rectangle in Histogram

Monotonic stack + area calc

Hard

Trapping Rain Water

Two-pointer or stack

Hard

Basic Calculator

Operator-precedence stack

Hard

Stacks

Stacks#

Think of it like this

Visualizing Push & Pop

Time Complexity

Space Complexity: O(n)

Implementation

Stack (Browser History)

Core Patterns

Real-World Frontend Application

Common Mistakes

Key Problems to Solve

Stacks

Stacks#

Think of it like this

Visualizing Push & Pop

Time Complexity

Space Complexity: O(n)

Implementation

Stack (Browser History)

Core Patterns

Real-World Frontend Application

Common Mistakes

Key Problems to Solve

Stacks

Stacks