Data structures · foundation
Stack
A stack is a collection whose push and pop operations add and remove at the same end, so the most recently added element is removed first.
Why it matters
Stacks model nested work such as function calls, parsing, undo history, and depth-first traversal, where the newest unfinished task must resume first.
Mental model
How to reason about stack
Only the top is active. Pushing suspends what was below it; popping completes the current layer and exposes the previous one.
Analogy
In a stack of trays, a new tray goes on top and the top tray comes off first. Reaching a lower tray requires removing those above it.
Examples
See the boundary, not just the happy path
Worked example · Balanced delimiters
push '(' when opened; pop when ')' closesThe newest unmatched opening delimiter must close first, exactly matching LIFO order.
Worked example · Iterative depth-first search
stack.push(start); node = stack.pop()Newly discovered neighbors sit above older alternatives, so one path is pursued before the algorithm backtracks.
Useful contrast · Not a queue
push A, push B, then pop returns BA queue would remove A, the oldest item; a stack removes B, the newest.
Common mistakes
Misconceptions to remove early
Reading or popping an empty stack
Underflow behavior varies by API: it may throw, return a sentinel, or be undefined. Check emptiness or use the documented safe operation.
Equating the abstract stack with call-stack memory
A stack is an interface and can be implemented with an array or linked list. A runtime call stack is one particular use with platform limits.
Quick check
Can you predict the result?
1. After pushing A, B, and C, which value does one pop return?
- • C
- • A
- • B
2. Why is a stack suitable for matching nested parentheses?
Keep building