Stack Fundamentals

What is this?

Think of a stack as a pile of plates: you only ever add to the top or take from the top. There are just three things you can do — put a plate on (push), take the top one off (pop), and peek at the top one — and each is instant. Once you have those three moves, the classic first puzzle is checking that brackets like ( ), [ ], and { } open and close in the right order.

flowchart TD A["See an opener"] --> B["Push it on the stack"] C["See a closer"] --> D["Check the top matches"] D --> E["Pop the top off"] F["Reached the end"] --> G["Stack should be empty"]

💡 Fun fact: Text editors track every change on a stack so that Undo always reverses your most recent edit first — pop the last action and the document steps back in time.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: A stack is a pile you touch only at the top — last in, first out (LIFO). Master the three O(1) moves (push, pop, peek) and the one pattern that defines this chapter: push things as you meet them, and resolve the most recent one when its match arrives.

The three operations, and nothing else

Chalkboard diagram of a stack with cells a, b, c and the three O(1) operations push, pop, peek with a top pointer

All three are O(1) — no shifting, no searching, you only ever touch the top. In Python a list already is a stack: stack.append(x) to push, stack.pop() to pop, stack[-1] to peek, if not stack to test empty.

The defining property: a stack hands items back in reverse order of arrival. So whenever "the next thing to deal with" is "the most recent thing I haven't finished," the stack already has it waiting on top.

When a problem is secretly a stack

Nesting / matching — brackets, tags, BEGIN/COMMIT — the innermost (most recent) must close first.
Undo / backtracking — the last action is the first undone.
Deferred work — pause the current task, handle a nested one, resume — exactly what the call stack does.

If you can phrase the task as "the latest unresolved item gets resolved first," reach for a stack.

The problem in this chapter

Valid Parentheses — the LIFO pattern in its purest form

Given a string of ()[]{}, decide if every bracket closes in the right order. Push each opener; on a closer, the top of the stack must be its matching opener (pop it) — otherwise it's invalid. A valid string ends with an empty stack.

Chalkboard trace of Valid Parentheses pushing and popping while scanning ( [ ] ) ending with an empty stack

Two ways to fail, and both matter: a mismatch (closer doesn't match the top) and leftover openers (stack not empty at the end). → O(n) time, O(n) space.

The cross-cutting skill: think in pushes and pops

Situation	Stack move
See an opener / a new unresolved item	push it
See a closer / a resolver	check the top, then pop
Reach the end	the stack should be empty (or its remainder is the answer)
Stack empty when you need to pop	the input is malformed → handle it

A stack turns "is the most recent unresolved thing the right one?" into a single peek + pop. Get comfortable here — every later chapter (expression eval, paths, monotonic stacks) is a variation on this move.

📓 Draw it yourself

Push/pop trace. Draw a vertical box and walk push a, push b, pop, push c, pop, pop, redrawing the pile each step. Always touch the top.
Brackets as a stack. Take ([{}]) and draw the stack growing on each opener and shrinking on each closer; circle the moment the top must match the incoming closer.

Snap photos and embed them with the /host-diagrams skill.

Complexity at a glance

Operation / problem	Time	Space
push / pop / peek	O(1)	—
Valid Parentheses	O(n)	O(n)

Key takeaways

LIFO, three O(1) moves. Push, pop, peek — you only ever touch the top.
In Python, a list is a stack (append, pop, [-1], not stack).
The fundamental pattern: push the unresolved, pop to resolve, and check the stack is empty at the end.
Guard your pops — popping an empty stack is the classic bug.
Why this chapter matters: every advanced stack problem — expression evaluation, path simplification, monotonic stacks — is built from exactly these moves.

Next: Valid Parentheses, then carry the push/pop instinct into Expression Evaluation.

Foundations