A stack is a last-in-first-out (LIFO) collection. The three core operations — push, pop, peek — all run in . Implementations: a dynamic array (append/pop from the end) or a singly linked list (push/pop at the head).
The call stack
Every programming language uses a stack to manage function calls. When you call a function, a new frame is pushed; when it returns, the frame is popped. This is why recursion works — and why deep recursion overflows. Understanding the call stack also clarifies how iterative algorithms can simulate recursion explicitly when needed.
Balanced parentheses
The classic intro problem. Scan the string; push opening brackets onto a stack; when you see a closing bracket, pop and verify it matches. If the stack is empty or mismatches at any point, the string is unbalanced. time.
Reverse Polish notation
To evaluate : scan left to right, push numbers onto the stack; when you see an operator, pop two values, apply, push the result. Final stack has one value — the answer. This is also how some compilers and calculators work internally.
Histograms and rectangles
"Largest rectangle in histogram" uses a monotonic stack to find, for each bar, the nearest taller bar on each side — in total. We'll cover monotonic stacks in the next lesson.
Undo / redo
Two stacks: undo and redo. Each action pushes its inverse onto undo. Pressing undo pops, applies, and pushes onto redo. Pressing redo reverses. Almost every text editor and design tool uses this pattern.