Stack
Last in, first out — like a stack of plates. Only the top is accessible: push, pop, peek, all O(1). The call stack running this page is one.
A stack exposes exactly three operations: push (add on top), pop (remove the top), peek (read the top). That restriction is the feature — it enforces perfectly nested, most-recent-first ordering.
Function calls are the canonical example: each call pushes a frame (locals + return address); returning pops it. Recursion depth is stack depth, and a runaway recursion "overflows the stack". Every recursive algorithm can be rewritten with an explicit stack — that is literally what the CPU does.
Stacks also drive undo histories (push each action, pop to undo), expression evaluation and syntax parsing (matching brackets), backtracking searches (DFS keeps its frontier on a stack), and browser back-buttons.
Operations
| Operation | Complexity |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
| search | O(n) — not its job |
Where it's used
Call stacks, undo/redo, DFS, parsing and bracket matching, expression evaluation (postfix/infix).