Stacks
A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. The last element inserted is the first one removed. Think of a stack of plates — you add to the top and remove from the top.
Core Operations
- Push(item): Add an item to the top of the stack — O(1)
- Pop(): Remove and return the top item — O(1)
- Peek(): Return the top item without removing it — O(1)
- isEmpty(): Check if the stack is empty — O(1)
Implementations
| Implementation | Pros | Cons |
|---|---|---|
| Array-based | Cache-friendly, O(1) amortized push | Fixed capacity (or resize overhead) |
| Linked-list-based | Dynamic size, no resizing | Extra memory per node, pointer chasing |
Common Applications
- Expression evaluation: Convert infix to postfix (Shunting-yard algorithm), evaluate postfix expressions.
- Undo/redo: Each action is pushed onto the undo stack; undo pops and pushes to the redo stack.
- Browser back button: Pages visited are pushed onto a stack; back button pops.
- Call stack: Function calls are pushed onto the call stack; returns pop them off.
- Balanced parentheses: Push opening brackets, pop on closing brackets; stack should be empty at end.
Two-Stack Algorithm
A classic expression evaluation algorithm (Dijkstra’s) uses two stacks:
- Operand stack: holds numbers
- Operator stack: holds operators and parentheses
Push operands onto the operand stack. Push operators onto the operator stack. When a closing parenthesis is encountered, pop operator and operands, evaluate, and push the result.