Mental model
Values enter and leave from one end called the top. Push adds to the top; pop removes from the top.
Everyday analogy
A stack of plates: you add and remove the plate at the top.
Learn by doing
Interactive visualization
Try multiple operations. Read the trace after every action and connect the visible movement to the operation's complexity.
Interactive data structure
Change the structure and watch the operation
Try an operation and connect the visible movement to its runtime cost.
Reasoning checkpoint
Pause and explain the trace
Try to answer each prompt before revealing the explanation.
01RepresentationHow does the physical representation explain the operations you saw?
Values enter and leave from one end called the top. Push adds to the top; pop removes from the top.
02CostWhy can “Push” become O(1)*?
A dynamic-array implementation may occasionally resize.
03CorrectnessWhich implementation mistake should you test explicitly?
Popping an empty stack
Cost model
Operation complexity
| Operation | Average | Worst | Why |
|---|---|---|---|
| Push | O(1) | O(1)* | A dynamic-array implementation may occasionally resize. |
| Pop | O(1) | O(1) | Only the top item is removed. |
| Peek | O(1) | O(1) | Reads the top without removing it. |
| Search | O(n) | O(n) | A stack is not designed for arbitrary lookup. |
* Amortized: occasional expensive work is spread across many cheap operations.
From picture to program
Java implementation
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.peek(); // 20
int removed = stack.pop(); // 20Where it appears
- Function calls and recursion
- Undo operations and browser navigation
- Expression parsing, DFS, and backtracking
Common mistakes
- Popping an empty stack
- Using Stack in modern Java instead of the Deque interface
- Trying to access elements in the middle