Stacks

What it is

A stack supports push and pop from one end only — last in, first out. Implemented as an array (fastest) or linked list, both give O(1) push/pop.

Core patterns

• Matching / validity — parentheses matching, HTML tag balancing: push opening tokens, pop and compare on closing tokens.
• Monotonic stack — maintain the stack in increasing or decreasing order, popping elements that violate it; used for "next greater element" and largest-rectangle-style problems in O(n) instead of O(n²).
• Call stack simulation — anywhere you'd use recursion (tree traversal, backtracking) can be rewritten iteratively with an explicit stack.

Complexity

Push, pop, and peek are all O(1). The trade-off versus an array is that a stack only exposes one end — you give up random access in exchange for a strict ordering guarantee.

Where it shows up

Expression evaluation, undo/redo history, and — since recursive tree/graph traversal literally uses the call stack — it's the conceptual bridge into recursion-heavy topics like trees and backtracking.