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.

💡 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

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.

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

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

1. 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.
2. 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

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.