Stacks and last-in-first-out order
A stack allows insertion and removal at one end only, which makes it the natural fit for anything that must unwind in reverse order: balanced brackets, undo history, expression evaluation, and the call stack itself.
The monotonic stack is the interview-grade variant. By keeping the stack sorted as you push, you answer "next greater element" style questions in a single O(n) pass instead of the obvious O(n²) scan.
Time and space complexity
| Operation | Time | Space |
|---|---|---|
| push | O(1) | O(1) |
| pop | O(1) | O(1) |
| peek / top | O(1) | O(1) |
| search | O(n) | O(1) |
| Total storage | — | O(n) |
How to use this visualizer
Choose a stack track such as balanced parentheses or a monotonic stack.
Step through and watch elements enter and leave from the same end.
For the monotonic track, note which elements get popped before a push and why.
Compare the running stack height against the input length.
Frequently asked questions
A monotonic stack keeps its elements in strictly increasing or decreasing order by popping any element that would violate that order before pushing. It solves next-greater-element, daily-temperatures, largest-rectangle-in-histogram, and trapping-rain-water in O(n), because every element is pushed and popped at most once.
Scan the string once. Push every opening bracket. On a closing bracket, pop and check that the popped bracket is the matching opener — if the stack is empty or the types disagree, the string is invalid. After the scan, the string is balanced only if the stack is empty. O(n) time and O(n) space.
A stack is last-in-first-out: the most recently added element leaves first, and both ends of the operation are the same. A queue is first-in-first-out: elements leave in arrival order, entering at the tail and leaving at the head. Stacks suit backtracking and depth-first traversal; queues suit scheduling and breadth-first traversal.