Stacks —

You're parsing a string of brackets: ({[]}). You encounter }. Is the string valid at this point? How do you know which opening bracket this } should match?

It has to match the most recent unmatched opening bracket. Not the first one. The most recent. Last in, first out.

That access pattern — where the most recently added item is the first one you need — is a stack. And it shows up far more often than you'd expect.

The Operations

Operation	Time	What It Does
push(x)	O(1)	Add to top
pop()	O(1)	Remove and return top
peek()	O(1)	Read top without removing
isEmpty()	O(1)	Check if empty

In JavaScript, arrays are stacks out of the box:

const stack: number[] = [];
stack.push(1);           // [1]
stack.push(2);           // [1, 2]
const top = stack.pop(); // top = 2, stack = [1]

push and pop operate on the end — O(1). Don't use unshift/shift — those operate on the front and shift every element. Why is that O(n)? If you read the arrays article, you already know.

The Matching Problem

Now solve it yourself before reading the solution: given a string containing (){}[], determine if every bracket is properly matched and nested. What data structure do you reach for, and what's your algorithm?

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ')': '(', '}': '{', ']': '[' };
  for (const c of s) {
    if ('([{'.includes(c)) stack.push(c);
    else if (stack.pop() !== pairs[c]) return false;
  }
  return stack.length === 0;
}

Opening bracket → push. Closing bracket → pop and check. Empty stack at the end → valid. This pattern — matching nested structure with a stack — solves bracket validation, HTML tag matching, calculator expressions, and directory path simplification.

But here's the deeper question: why does nesting require a stack specifically? Why wouldn't a counter work? Think about ([)] — two of each bracket type, counts balance perfectly, but the string is invalid. The order matters, and a stack preserves order while a counter doesn't.

The Call Stack Connection

Here's something worth sitting with: every time you call a function, your operating system pushes a frame onto a stack. Every return pops one. Recursion is just repeated pushing onto the same stack.

This means two things:

1. Deep recursion = deep stack. O(n) recursive depth on large input risks stack overflow. That's not a metaphor — it's literally the stack overflowing.

1. Any recursion can become an explicit stack. And sometimes it must.

Iterative DFS is the canonical example:

function dfs(root: TreeNode | null): void {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop()!;
    // process node
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

Question: why push right before left? Think about what pop returns and what order you want to process nodes in.

Right is pushed first so left is on top and gets popped first — preserving the expected left-to-right DFS traversal. The order of pushes is the reverse of the order you want to process. This trips people up in interviews when they get the traversal order backward.

Monotonic Stacks

This is the advanced pattern. Before I explain it, try this problem: for each element in an array, find the next element that's greater than it. Brute force is O(n²). Can you do it in O(n)?

The insight: maintain a stack of indices, where the corresponding values are in decreasing order. When you encounter a value greater than the stack's top, that value is the "next greater" for every smaller element on the stack.

function nextGreater(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Each element is pushed once and popped at most once. O(n) total. The nested while loop isn't O(n²) — same amortized argument as sliding window.

What makes this a "monotonic" stack? The stack always maintains decreasing order. Any element that would violate that order triggers pops until the invariant is restored. That invariant is what lets you answer "nearest greater element" queries in constant amortized time.

This pattern appears in stock span, histogram max area, daily temperatures, and trapping rain water. If a problem asks "find the nearest X that's greater/smaller," think monotonic stack.

Reflection

Two checks. First: why does bracket matching require a stack and not just a counter? Give a specific counterexample. Second: explain why the monotonic stack's next-greater algorithm is O(n) despite the nested loop. If both answers are clear in your head, you've internalized the core — not just memorized the code.

Original article: [jamesperalta.com](https://jamesperalta.com/learn/dsa/stacks)