Foundation · Module 11 · Lesson 1
Stack
LIFO operations, call stacks, parsing, and undo.
Lesson 58 of 123
1d streakInteractive Visualization
See how stack works
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive data structure
Change the structure and watch the operation
Try an operation and connect the visible movement to its runtime cost.
The LIFO Principle & Hardware Call Stack Execution
A Stack is a linear data structure that enforces the Last-In, First-Out (LIFO) access discipline: elements can only be inserted (push) and removed (pop) from one designated end, termed the top. Think of a stack of plates in a cafeteria: you can only place a new plate on top, and you can only remove the topmost plate.
Visual Mental Model:
Push(30) Pop() -> returns 30
| ^
v |
+----------+ +----------+
TOP | 30 | | 20 | <-- NEW TOP
+----------+ +----------+
| 20 | | 10 |
+----------+ +----------+
BASE | 10 | BASE | 10 |
+----------+ +----------+
Hardware Activation Records (Microprocessor Call Stack):
+-------------------------------------------------------------+
| Stack Frame: main() |
| - Local Variables: args, config |
| - Return Address: OS process exit |
+-------------------------------------------------------------+
| Stack Frame: processOrder(orderId = 42) |
| - Local Variables: order, totalAmount |
| - Return Address: back to main() line 18 |
+-------------------------------------------------------------+
| Stack Frame: calculateTax(amount = 100.0) <-- Top (RSP) |
| - Local Variables: rate = 0.08, tax = 8.0 |
| - Return Address: back to processOrder() line 35 |
+-------------------------------------------------------------+
When calculateTax() completes:
1. CPU executes 'RET' instruction.
2. Pops calculateTax frame off the top.
3. Resumes processOrder() at line 35 with return value 8.0!| Operation | Method | Time Complexity | Physical Mechanism |
|---|---|---|---|
| Push | push(x) | O(1) | Writes element at top pointer; increments top cursor |
| Pop | pop() | O(1) | Reads element at top pointer; decrements top cursor |
| Peek / Top | peek() | O(1) | Reads element at top without moving cursor |
| Is Empty | isEmpty() | O(1) | Checks if top cursor == -1 (or size == 0) |
| Search | search(x) | O(n) | Requires popping or scanning through items sequentially |
What Causes a StackOverflowError?
StackOverflowError. Converting recursion to an iterative loop with an explicit heap-allocated Deque<T> eliminates this limit.The Min Stack Pattern: O(1) Minimum Tracking
A classic FAANG interview question asks: "Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time." Scanning the stack on getMin() would take $O(n)$. We can achieve $O(1)$ by maintaining a synchronized secondary stack of prefix minimums.
Operations: push(5), push(3), push(7), push(2), pop()
Main Stack: Min Stack:
Push 5 -> [ 5 ] Push min(5, 5) -> [ 5 ]
Push 3 -> [ 5, 3 ] Push min(3, 5) -> [ 5, 3 ]
Push 7 -> [ 5, 3, 7 ] Push min(7, 3) -> [ 5, 3, 3 ]
Push 2 -> [ 5, 3, 7, 2 ] Push min(2, 3) -> [ 5, 3, 3, 2 ]
Current getMin() = minStack.peek() = 2
Pop() executes:
Main Stack pops 2 -> [ 5, 3, 7 ]
Min Stack pops 2 -> [ 5, 3, 3 ]
Next getMin() = minStack.peek() = 3 (Instant O(1) with zero searching!)class MinStack {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();
public void push(int val) {
stack.push(val);
// Min stack stores current minimum up to this depth
int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
minStack.push(currentMin);
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek(); // Strictly O(1)
}
}Balanced Parentheses & Parsing State Machines
Stacks are the universal tool for validating nested structures (HTML tags, JSON objects, arithmetic expressions). An opening delimiter creates an "obligation" that must be resolved in reverse order of arrival.
// Classic Balanced Parentheses Validation - O(n) time, O(n) space
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (ch == '(') stack.push(')');
else if (ch == '{') stack.push('}');
else if (ch == '[') stack.push(']');
else {
// Closing bracket: must match the most recent opening bracket
if (stack.isEmpty() || stack.pop() != ch) {
return false;
}
}
}
// All opened brackets must be matched and closed
return stack.isEmpty();
}Architectural Boundary · Do Not Confuse
Counter Variable: int balance = 0
Stack: Deque<Character>
A single counter works for 1 bracket type ("(())" -> balance++ on "(", balance-- on ")"). But for multiple bracket types ("([)]"), a counter fails to verify that the innermost bracket closes first. A stack preserves the exact type ordering.
Cost Model
Complexity & Trade-offs
Hands-On Practice
Implement: Valid Parentheses (Stack)
Write and test your solution in the browser against automated verification test cases.
Valid Parentheses (Stack)
Given a string s containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.
When to use it
- Nested parsing, undo, arrival order, buffering, and nearest-greater queries.
- BFS frontiers and producer/consumer scheduling.
- Maintaining range extremes or constrained access.
Common mistakes
- Reading from an empty structure.
- Confusing the logical front with an array index in a circular buffer.
- Missing the amortized argument for transfers or monotonic pops.
Practice prompts
- Reproduce the worked Stack example without looking at the trace.
- Change one input condition and explain whether the Stack invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check