Stop 21 · Data Structures & AlgorithmsTopics · 4/17

Stack

In short

Brackets matching, undo buttons, the call stack in your own Node.js process: all stacks. Once you spot the "last in, first out" pattern, these questions solve themselves.

A Last-In-First-Out (LIFO) data structure — used for problems involving nested or matching structures, undo functionality, and backtracking.

At a wedding buffet the purple blob adds a plate to the top of a tall stack.

Think of it like this

Plates at a wedding buffet

Waiters put clean plates on top of the pile, and guests take from the top. Nobody pulls a plate from the bottom. The last plate placed is the first one used. That's a stack.

Watch it happen

Checking "{[()]}"

push({)

{

Top of the stack is coloured

1/6An opening bracket. Push it and wait for its partner.

The big ideas

What you need to know

Push and pop from the top

Both are O(1). In JavaScript, a plain array with push() and pop() is a perfectly good stack.

Matching and nesting

Whenever something must close in the reverse order it opened, like brackets or HTML tags, think stack.

Undo and history

Editors push every action. Undo pops the latest one off. Browsers do the same with the back button.

Monotonic stack

Keep the stack always increasing or decreasing to answer "next greater element" style questions in O(n).

See it in code

Walk through the code

1function isValid(s: string): boolean {2  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };3  const stack: string[] = [];4 5  for (const ch of s) {6    if (ch === "(" || ch === "[" || ch === "{") {7      stack.push(ch);                          // opener: wait for its partner8    } else if (stack.pop() !== pairs[ch]) {9      return false;                            // wrong partner, or nothing to close10    }11  }12  return stack.length === 0;                   // leftovers mean unclosed brackets13}14 15console.log(isValid("{[()]}"), isValid("([)]")); // true false

1/4Map each closer to its opener, and start with an empty stack.

"([)]" fails because when ")" arrives, the top of the stack is "[", not "(".

Save yourself the pain

Common mistakes

Oops

Returning true as soon as the loop ends.

Do this instead

Check the stack is empty too. "((" never fails inside the loop but is still invalid.

Oops

Writing deep recursion on huge input in Node.js.

Do this instead

Recursion uses the call stack, which has a limit. Switch to an explicit array stack for very deep inputs.

Your mission

Stack it up

~30 min

Quick check

You push 1, 2, 3 and then pop twice. What's left in the stack?

Go deeper

1Solve the classic 'valid parentheses' problem using a stack.
2Implement a stack from scratch using an array.
3Recognize stack-shaped problems: anything about matching, nesting, or 'most recent unresolved item'.