Stacks

A stack is a pile. Think of a stack of plates: you add a plate to the top and you take a plate off the top. The last plate you put down is the first one you pick up — Last In, First Out (LIFO). You never reach into the middle of the pile.

That one rule is the entire data structure. Two operations do all the work: push adds to the top, pop removes from the top (often with peek to look without removing). Because everything happens at one end, both are O(1). A stack is really just an array or linked list with a self-imposed restriction — and that restriction is what makes it useful.

The cost model

The call stack

You use a stack every time your code runs a function. When a function is called, the runtime pushes a stack frame — its local variables and return address — onto the call stack. When the function returns, that frame is popped. Deeply nested or runaway recursion pushes frames faster than they pop, and the stack overflows. That is literally what a "stack overflow" is.

Classic: balanced parentheses

Matching brackets is the textbook stack problem. Scan left to right: push every opening bracket, and on each closing bracket check that the top of the stack is its matching partner. If it isn’t — or the stack is empty — the string is unbalanced. A valid string leaves the stack empty at the end.

function isBalanced(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' }
  const stack = []
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch)
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false
    }
  }
  return stack.length === 0
}

The monotonic stack

A monotonic stack keeps its elements sorted (increasing or decreasing) by popping anything that would break the order before pushing. It turns "find the next greater element" style problems from O(n²) brute force into a single O(n) pass, because each element is pushed and popped at most once.

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1)
  const stack = [] // holds indices, values decreasing
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      res[stack.pop()] = nums[i]
    }
    stack.push(i)
  }
  return res
}

When to reach for a stack

• You need LIFO ordering — the most recent item is the one you want next.
• You’re processing nested or matched structures: brackets, tags, expressions.
• You want undo/redo, backtracking, or an explicit call stack for iterative DFS.
• You’re solving next-greater / span problems — a monotonic stack collapses them to O(n).