Stacks and last-in, first-out work
A stack removes the most recently added item first: last in, first out (LIFO).
Learning objectives
- Define push, pop, and top.
- Identify a LIFO problem.
Operation trace
push A: [A] push B: [A, B] ← top pop: returns B, leaves [A]
A stack exposes only its top as the normal removal point. With an array-backed or linked implementation that supports its end efficiently, push and pop are usually O(1).
Applications and mistakes
Undo histories, matching parentheses, depth-first traversal, and the call stack all use a LIFO idea. Do not pop from an empty stack; decide whether the API reports an error, returns an optional value, or checks emptiness first.