What is a Stack?
A Stack is a data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first one removed.
Think of a stack of plates — you add new plates on top and take plates from the top. That's exactly how a stack works in programming.
Why Does It Matter?
The stack is one of the most fundamental data structures, used in surprisingly many places.
- •Call stack: Function calls and returns in programs are managed via a stack
- •DFS implementation: Iterative DFS uses an explicit stack
- •Interview essential: Parentheses matching, largest rectangle in histogram, stock prices
Core Operations
| Operation | Description | Time |
|---|---|---|
| push(item) | Add element to the top | O(1) |
| pop() | Remove and return top element | O(1) |
| peek() / top() | View top element without removing | O(1) |
| isEmpty() | Check if stack is empty | O(1) |
All operations are O(1) — they only interact with the top of the stack.
Real-World Applications
1. Parentheses Matching
The most classic stack problem. Push opening brackets, pop on closing brackets, and check if they match.
- •
(),[],{}— Valid - •
([)]— Invalid
2. Browser Back/Forward
Two stacks: a back stack and a forward stack. Visiting a new page pushes the current page onto the back stack. Going back pushes onto the forward stack.
3. Undo (Ctrl+Z)
Text editors use a stack for undo. Every action is pushed onto the stack, and undo pops the most recent action.
4. DFS (Depth-First Search)
Instead of recursion, use an explicit stack: pop a node, push its neighbors. Same traversal, no recursion overhead.
Stack vs Queue
| Comparison | Stack | Queue |
|---|---|---|
| Principle | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Analogy | Stack of plates | Standing in line |
| Add | push (top) | enqueue (back) |
| Remove | pop (top) | dequeue (front) |
| Use Cases | DFS, parentheses, undo | BFS, print queue, cache |
Common Stack Interview Patterns
Monotonic Stack — Maintain elements in strictly increasing/decreasing order to find "next greater element" or "previous smaller element" in O(n).
- •Stock prices: Count days the price didn't drop
- •Histogram: Find the largest rectangle area
- •Next greater element: Find the first larger element to the right
Common Mistakes
- •Calling pop or peek on an empty stack causes errors → Always check isEmpty first
- •In parentheses problems, forgetting to check if unmatched opening brackets remain
- •Setting push/pop conditions backwards in monotonic stack problems
See It in Action on AlgoNote
Watch how push and pop operations change the stack step by step on AlgoNote. Enter your own sequence of operations and experiment to build intuition.