← Learn DSA · Lesson 3 of 9
Stacks & Queues
When the order you process things in is the whole problem.
The idea
A stack is last-in-first-out; a queue is first-in-first-out. Both are trivial to implement. What is worth learning is recognising the problems whose structure is one of them.
Stack appears whenever the most recent unresolved thing must be resolved first — matching brackets, undo history, evaluating nested expressions, and depth-first traversal. If you find yourself saying "the last one I saw", it is a stack.
The subtler use is the monotonic stack: keep the stack sorted by holding only elements that are still candidates, popping any that the current element makes irrelevant. That is how "next greater element" problems collapse from O(n²) to O(n) — each index is pushed once and popped once, however nested the loops look.
Queue appears when things must be handled in arrival order — breadth-first traversal, scheduling, rate limiting, buffering between a fast producer and a slow consumer.
Walkthrough
A stack is just an array with a top. +1 pushes, -1 pops — watch the depth rise and fall.
What it costs
- time
- O(1) per push, pop, or peek
- space
- O(n) for n held elements
A monotonic stack processes each element exactly twice — once pushed, once popped — so the total is linear even though the code contains a loop inside a loop.
When to reach for it
- The most recently seen item is the first one you need to resolve — that is a stack.
- Items must be handled in arrival order, or you are exploring level by level — that is a queue.
- You are matching pairs or tracking nesting.
- You need the next greater or next smaller element, which is a monotonic stack.
Rather than the obvious alternative
Recursion
A stack is what recursion uses underneath. Making it explicit is how you avoid stack overflow on deep inputs, and how you pause and resume a traversal.
An array with shift()
Removing from the front of an array is O(n) because everything shifts. A real queue or deque makes it O(1), which matters inside a BFS loop.
Sorting
For next-greater-element problems a monotonic stack is O(n) where sorting is O(n log n) and loses the positions you needed.
How to spot it
- The most recently seen item is the first one you need to resolve.
- You are matching pairs, or tracking nesting.
- The problem asks for the next greater, next smaller, or nearest element.
- You are traversing level by level, which is a queue rather than a stack.
Where it goes wrong
Popping an empty stack
A closing bracket with nothing open is a valid input, not an impossible one. Check before popping.
Forgetting the leftovers
Finishing the input with a non-empty stack usually means unmatched openers. The loop ending is not the same as the answer being valid.
Using an array as a queue in JavaScript
`shift()` is O(n) because it re-indexes everything. Fine for small inputs, quietly quadratic for large ones.
Practise it
- Valid Parentheseseasy
- Daily Temperaturesmedium
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.