Stop 21 · Data Structures & AlgorithmsTopics · 4/17

Stack

In short

Your browser's back button, Ctrl+Z and the JS call stack all work the same way. Whenever a problem says 'matching' or 'nested', think stack first.

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

The jaadu places a steel plate on top of a tall pile in the hostel mess.

Think of it like this

Plates in the hostel mess

Washed plates go on top of the pile, and the next student takes the top one. The plate that went in last comes out first. Nobody pulls a plate from the bottom.

Watch it happen

Checking "{[()]}"

push({)

{

Top of the stack is coloured

1/6'{' is an opener, so push it on the stack.

The big ideas

What you need to know

Last in, first out

You only touch the top: push adds, pop removes, peek looks. All are O(1).

A JS array is enough

Use push and pop on a normal array. They work at the end, which is fast.

Great for matching pairs

Brackets, HTML tags, undo history. The most recent open thing must close first.

Monotonic stack

Keep the stack sorted to answer 'next greater element' style questions in O(n).

See it in code

Walk through the code

1function isValid(s) {2  const pairs = { ")": "(", "]": "[", "}": "{" };3  const stack = [];4 5  for (const ch of s) {6    if (ch in pairs) {7      if (stack.pop() !== pairs[ch]) return false;8    } else {9      stack.push(ch);10    }11  }12  return stack.length === 0;13}14 15isValid("{[()]}"); // true

1/4A lookup from each closer to its opener, plus an empty stack.

One pass over the string, so time is O(n). In the worst case, like "((((", every character sits on the stack, so space is O(n).

Save yourself the pain

Common mistakes

Oops

Returning true as soon as the loop ends.

Do this instead

Check the stack is empty. "(((" never fails a match but is still unbalanced.

Oops

Using shift and unshift to build a stack.

Do this instead

Work at the end with push and pop. The front of an array is the slow side.

Your mission

Stack it up

~35 min

Quick check

You push 1, 2, 3 onto a stack, pop once, then push 4. What does the next pop return?

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'.