A stack fits whenever the thing that most recently opened is the first thing that must close: a bracket, a function call, a transaction inside another transaction. Push when something opens; when something closes, it must match the item on top.
In JavaScript an array is a stack: push adds to the top, pop removes from it, and stack[stack.length - 1] looks without removing. Both ends of the work are one step each.
A second use is the monotonic stack: items still waiting for an answer, kept in order. When a new item arrives, pop every waiting item it answers, then push it to wait in turn. Each item is pushed once and popped at most once, so a question like "how long until something larger" takes one pass instead of a scan per item.
Check what is left at the end. A stack that is not empty means something opened and never closed, or some items never got an answer.
Recognise it
- Things open and close, and must close in the reverse order they opened.
- For each item you need the next or previous item that is larger or smaller.
- A direct solution scans forward from every item.
The shape of the code
const stack = [];
for (let i = 0; i < items.length; i++) {
while (stack.length && resolves(items[i], items[stack[stack.length - 1]])) {
const waiting = stack.pop();
// record the answer for waiting
}
stack.push(i);
}
// whatever is left in stack has no answer