Stack Overview
Master the LIFO (Last-In, First-Out) data structure.
What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. Imagine a stack of plates: you can only add a new plate to the top (Push) and can only remove the top plate (Pop). The last element added is the first one to be removed.
The Motivation: Valid Parentheses
Consider the problem of checking if a string of brackets is valid: {[()]}.
To solve this, you need to remember the most recent opening bracket to match it with the correct closing one. A Stack is perfect for this "remembering the most recent" state.
Attempt 1: Brute Force (Why it fails)
Without a stack, you might try to count open and close brackets. However, ([)] has balanced counts but is invalid. You need to track the order. Repeatedly finding and deleting matching pairs () in the string is an O(N²) operation due to string manipulation.
Visualizing the Issue
If you just count, you lose the nested structure information. You need a way to say "Wait, I'm currently inside a {, so I expect a } next, unless I start a new ( group."
When should I use a Stack?
- Matching/Pairing: Parentheses, HTML tags.
- Reverse Order: Reversing a string, Undo feature.
- Next Greater/Smaller Element: Monotonic Stack pattern.
- Simulating Recursion: Iterative DFS.
The Intuition: Matching Neighbors
By using a stack, we can process elements one by one. If we see a 'start' signal (like (), we push it. If we see an 'end' signal (like )), we pop the top of the stack and check if it matches. This resolves dependencies locally in O(N).
Interactive Walkthrough
LAST IN · FIRST OUT
EMPTY STACK
operations
stack
empty
Size
0
Top
—
isEmpty
—
Create an empty stack
Next
push 3: it goes on top. Size 1
Ops
Legend & Complexity
The value an operation just pushed, read or popped
The operation running now, in the list
A peek or pop on an empty stack
The floor: the closed end of the stack
Push / pop / peek
O(1)
Space
O(n)
Run a list of stack operations: each push, peek, pop and isEmpty lights its line of code, and the column shows the stack after it — top drawn highest. Try Pop from empty to see why code checks isEmpty before popping.
Dry Run Table
Input: ()[{}]
| Char | Action | Stack State | Check |
|---|---|---|---|
( |
Push | ( |
- |
) |
Pop | Empty |
Match (? Yes |
[ |
Push | [ |
- |
{ |
Push | [ { |
- |
} |
Pop | [ |
Match {? Yes |
] |
Pop | Empty |
Match [? Yes |
The Solution Template
The five stack operations, one line each, in every language.
Stack Overview Code
1const stack = [];2stack.push(x); // push3const top = stack[stack.length - 1]; // peek4stack.pop(); // pop5const isEmpty = stack.length === 0;
Edge Cases & Common Mistakes
- Empty Stack Pop: Trying to pop from an empty stack causes error/crash.
- Leftover Elements: Stack must be empty at the end for validity (e.g.,
((is invalid).
Summary
- Use Stack for LIFO problems.
- Perfect for parsing, nested structures, and tracking 'previous' distinct state.