Stack
A stack is a "last in, first out" (LIFO) structure: the element added most recently is the first one removed. Push, pop, and peek all touch only the top, so they are O(1).
A stack fits when a problem needs to remember the order of "opens" to match them with "closes" (checking balanced brackets), to keep a history for undo, or to compare the current element with the nearest unprocessed one (monotonic stack). Recursion itself runs on an implicit system stack.
Like a stack of plates in a kitchen — the last plate put on is the first one taken off (LIFO).
- To get the plate at the bottom you have to lift off all the plates above it.
- Every push/pop only touches the top of the stack.
How to spot it
When you see these cues in the problem, reach for Stack
| Keyword in the problem | Why it points to this topic |
|---|---|
| match open / close pairs | Brackets, HTML tags — push on open, pop on close |
| next greater / smaller | Monotonic stack keeps increasing/decreasing order |
| undo history | Most recent handled first (LIFO) |
When to use
4 typical situations where this topic applies
You need to remember the order of "opens" to match "closes" (brackets, HTML tags)
You need undo / to go back to the most recent state
You need to compare the current element with the nearest unprocessed one (monotonic stack)
Simulating recursion with a loop + an explicit stack
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
You need FIFO (first in, first out): use a Queue, not a Stack
You need to access an element at any position (random access): a Stack only operates on the top
You need to keep the original order of appearance while processing: consider a Queue or iterating the array directly
Illustration
A diagram of how this topic works.
Last in, first out (LIFO): you only add or remove at the top. push puts an element on top, pop takes the top one — both O(1).
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function stackPattern(items: T[]): R {
const stack: T[] = []
for (const item of items) {
// Match / merge with the top while the condition holds
while (stack.length && shouldPop(stack[stack.length - 1], item)) {
stack.pop()
}
stack.push(item) // or push a value derived from item
}
return assembleResult(stack)
}Recap
A quick summary — reread it before your interview
Key points
push() and pop() are both O(1) — they operate only at the top
In JS use an array: push() to add, pop() to take the top
A monotonic stack keeps elements increasing/decreasing; each element enters/leaves at most once → O(n)
Common mistakes
Forgetting to check for an empty stack before pop → undefined
Matching brackets wrongly by comparing with the element at the bottom instead of the top
Forgetting to handle elements left in the stack after the loop
Complexity
push/pop/peek O(1), duyệt 1 lần O(n)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence