Problems
A stack is a data structure that follows the Last-In, First-Out (LIFO) principle. The last item you put in is the first item you take out.
Think of a stack of plates. You add plates on top and remove from the top. You can't pull a plate from the middle or bottom without removing everything above it first.
Stacks are everywhere in programming. Every time you call a function, it goes on the call stack. When you hit undo in a text editor, it pops the last action from a stack. Browser back button? Stack.
A stack supports only a few operations, and that's what makes it powerful. You don't need random access. You only care about the top.
- push(item): Add an item on top of the stack
- pop(): Remove and return the top item
- peek() / top(): Look at the top item without removing it
- isEmpty(): Check if the stack has no items
- size(): How many items are in the stack
| Operation | What it does | Time Complexity |
|---|---|---|
| push(item) | Add item on top | O(1) |
| pop() | Remove and return top item | O(1) |
| peek() / top() | Look at top item | O(1) |
| isEmpty() | Check if stack is empty | O(1) |
| size() | Number of items | O(1) |
Notice that every operation is O(1). That's the beauty of a stack. You never search, you never iterate. You only touch the top.
In most languages, you don't need to build a stack from scratch. Arrays and built-in collections work perfectly.
- Python: Use a regular list.
append()is push,pop()is pop,[-1]is peek. - Java: Use
Deque<Integer> stack = new ArrayDeque<>(). Avoid the oldStackclass. - JavaScript: Use an array.
push()andpop()are built in. - C++: Use
std::stack<int>from the standard library. - Go: Use a slice. Append to push, slice to pop.
You can build a stack using an array or a linked list. In practice, arrays are almost always better.
- Array-based: Items are stored in contiguous memory. push/pop just move a pointer. Very cache-friendly and fast.
- Linked list-based: Each node points to the one below it. Push adds a new head, pop removes the head. Uses more memory because of the pointers.
Use an array-based stack unless you have a specific reason not to.
| Array-based | Linked list-based | |
|---|---|---|
| push() | O(1) amortized | O(1) |
| pop() | O(1) | O(1) |
| Memory | Compact, cache-friendly | Extra pointer per node |
| Best for | Almost everything | When max size is unknown and memory is tight |
Stacks show up more than you think:
- Function call stack: Every function call pushes a frame. When it returns, the frame is popped. This is how recursion works under the hood.
- Undo/Redo: Text editors push each action onto a stack. Undo pops the last action. Redo uses a second stack.
- Browser history: Back button pops the current page and pushes it onto a forward stack.
- Expression evaluation: Calculators use stacks to handle operator precedence and parentheses.
- Syntax parsing: Compilers use stacks to match brackets, parse HTML tags, and validate nested structures.
Look for these clues in a problem:
- Matching pairs: Anything that opens and closes (brackets, tags, quotes). Push the opener, pop when you see the closer.
- "Next greater" or "next smaller": A monotonic stack solves this in one pass. Keep the stack sorted, pop elements that violate the order.
- Undo operations: Anything where you need to reverse the most recent action.
- Nested structures: Parsing expressions, handling nested groups, function calls.
- Converting recursion to iteration: Any recursive algorithm can be rewritten with an explicit stack. This is exactly what DFS does.
1. Popping from an empty stack.
Always check isEmpty() before calling pop() or peek(). Forgetting this causes runtime errors.
2. Using Java's Stack class.
The java.util.Stack class is legacy and synchronized (slow). Use ArrayDeque instead.
3. Forgetting items left in the stack. In monotonic stack problems, items remaining after the loop have no "next greater" element. Don't forget to handle them (usually set to -1).
4. Confusing stack with queue. Stack is LIFO (last in, first out). Queue is FIFO (first in, first out). If you need level-order processing, you need a queue, not a stack.
| Stack (LIFO) | Queue (FIFO) | |
|---|---|---|
| Order | Last in, first out | First in, first out |
| Add | push (top) | enqueue (back) |
| Remove | pop (top) | dequeue (front) |
| Use when | Need to reverse, match pairs, backtrack | Need ordering, level-by-level, BFS |
| Real life | Stack of plates, undo button | Waiting in line, printer queue |