Stack
A stack is a LIFO (Last In, First Out) data structure. Elements are added and removed from the same end — the top. Think of a stack of plates: you always add or take from the top.
Interactive Visualization
stack.peek() → 5. Reads stack[top] without modifying the stack. O(1) — no removalHow it Works
- LIFO discipline: The last element pushed is always the first to be popped. Only the top element is ever directly accessible.
- Top pointer: A single integer
toptracks where the next push writes and where pop reads from. Empty stack → top = −1. - All core operations O(1): Push, pop, and peek never iterate — they all work solely through the top pointer and a single array access.
- Fixed vs dynamic: Fixed stacks raise StackOverflowError when full. Dynamic stacks (backed by a resizable array) reallocate — same amortised O(1) cost as dynamic arrays.
Memory Layout
Operations — Full Summary
| Operation | Condition | Complexity | Notes |
|---|---|---|---|
| push(x) | Has free space | O(1) | Increment top, write x — two ops total |
| push(x) | Full (fixed-size) | O(1) then error | Top at bound → StackOverflowError; no write |
| push(x) | Full (dynamic) | O(n) once, O(1) amortised | Realloc: copy n elements then write |
| pop() | Non-empty | O(1) | Read top value, decrement top, return value |
| pop() | Empty stack | O(1) then error | top === −1 → StackUnderflowError; no change |
| peek() / top() | Non-empty | O(1) | Read stack[top], no pointer change |
| peek() / top() | Empty stack | O(1) then error | Returns error — nothing to read |
| isEmpty() | Always | O(1) | Returns top === −1 |
| size() | Always | O(1) | Returns top + 1 |
| search(x) | Any | O(n) | Not a core op — scan from top to bottom |
Common Use Cases
Function Call Stack
Every function call pushes a frame; return pops it. Stack overflow = too many nested calls (e.g. infinite recursion).
Undo / Redo
Each action is pushed onto an undo stack. Ctrl+Z pops and reverses it; redo pushes onto a separate redo stack.
Expression Parsing
Compilers use stacks to evaluate expressions, match parentheses, and convert between infix, prefix, and postfix.
DFS / Backtracking
Depth-first search and recursive backtracking algorithms use an explicit stack (or the call stack) to track the path.
Browser History
Back button pops the current page off the history stack, revealing the previous one.
Syntax Checking
Validate that brackets, braces, and tags are properly nested by pushing opens and popping on closes.
When NOT to Use a Stack
- You need to access elements by index — use an Array; stacks only expose the top.
- FIFO ordering (queue behaviour) — use a Queue or Deque; stacks are LIFO only.
- Searching by value — stack search is O(n) with no structural advantage. Use a Hash Set for O(1) average lookup.
- Priority-based removal — use a Priority Queue / Heap; stacks have no concept of element priority.
- Very deep recursion / huge datasets — fixed-size stacks overflow. Use iterative approaches with an explicit dynamic stack or increase the stack limit.