Foundation 05
Stack
A last-in, first-out collection: only the most recently added item is exposed.
01
Mental model
What the structure guarantees
The restricted access is the useful part. The top always represents the most recent unresolved item, call, edit, opening bracket, or candidate answer.
02
Implementation
How that model appears in code
Java code should normally use ArrayDeque rather than the legacy Stack class. C++ has std::stack; Python lists support append and pop at the end.
Stack basics
Deque<Integer> stack = new ArrayDeque<>();
stack.push(7);
int top = stack.peek();
int removed = stack.pop();stack = []
stack.append(7)
top = stack[-1]
removed = stack.pop()stack<int> st;
st.push(7);
int top = st.top();
st.pop();03
Operation costs
What gets more expensive as the input grows
OperationCostWhy
Push, peek, or pop the top
O(1)Only one end changes.Search for an arbitrary item
O(n)The stack offers no direct middle access.04
Tradeoffs
Choose it for the operations it makes cheap
Good fit
- Nested delimiters
- Undo and backtracking
- Unresolved candidates in monotonic-stack problems
Poor fit
- Oldest-first processing
- Random access
- Removing from the middle
Used by
Monotonic Stack
05
Common mistakes
Errors that survive a first glance
Check for empty before peek or pop
Put the emptiness test first in a short-circuit condition.
Store indices when distance matters
An index can recover both the value and the distance. A value alone cannot recover its position.
Use one end consistently
Mixing front and back operations quietly changes the data structure.