Stack

A stack is the simplest possible container — push, pop, peek at the top, nothing else — and yet it's the exact right tool the moment a problem has a "most recent unresolved thing" shape: the most recently opened bracket, the most recent nested group, the most recent right-moving asteroid still in flight. Recognizing that shape is the actual skill; the container itself is trivial.

Why LIFO order is the whole point

A stack is Last-In-First-Out for a reason: in every problem below, whatever you need to resolve next is whatever was most recently left unresolved. Bracket matching is the clearest case — "([)]" is invalid precisely because the ) needs to match the most recent unmatched (, not just any earlier one. A queue (FIFO) would get this wrong; a stack gets it right for free, just by existing.

The monotonic stack: the pattern hiding inside "next greater/smaller"

Daily Temperatures, Next Greater Element, and Largest Rectangle in Histogram all look like they need an O(n²) "scan forward/backward from every position" approach — and a monotonic stack is what turns that into O(n). The idea: keep a stack whose values are always in sorted order (increasing or decreasing, depending on the problem) from bottom to top. When a new element would break that order, pop everything that it invalidates — and the reason this is fast is that each element only ever gets pushed once and popped once across the entire run, no matter how many times the while loop looks like it's doing extra work.

// This LOOKS like it could be O(n^2) -- a while loop nested inside a for
// loop. It isn't, because of one fact: every index gets pushed exactly
// once and popped at most once across the WHOLE run, not once per
// outer iteration.
for (int i = 0; i < n; ++i) {
    while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
        // this index is popped HERE and never pushed again -- it's
        // permanently resolved, not re-examined on a future i
        result[st.top()] = i - st.top();
        st.pop();
    }
    st.push(i);   // pushed exactly once, ever
}
// Total pushes: n. Total pops: at most n. Total work: O(n), not O(n^2).

Stack-as-scratchpad: building output incrementally

A second recurring shape: some problems use a stack not to track "what's still pending" but as a scratchpad for building a result where later input can retroactively undo earlier output — Backspace String Compare (a # undoes the last character), Remove All Adjacent Duplicates (a matching character cancels the one before it), and Decode String (a closing bracket finishes and folds in everything built since the matching open). In all three, a plain string-append-only approach can't handle the "undo," but a stack's pop handles it directly.

Common mistakes

• Popping without checking empty() first — an unclosed bracket, an extra backspace, or a malformed input will call .top()/.pop() on an empty stack, which is undefined behavior, not a clean crash you can rely on.
• Getting the monotonic stack's direction backwards — "next greater" needs a decreasing stack (pop when the new value is bigger); "next smaller" needs the opposite. Copy-pasting the wrong comparison silently solves a different problem.
• Off-by-one on width calculations after a pop (Largest Rectangle in Histogram) — the popped bar's width depends on what's now on top of the stack (its left boundary) and the current index (its right boundary), and getting the boundary exclusive/inclusive wrong is the single most common bug in this problem.
• Re-scanning from the start after a stack-driven "cascade" (Remove All Adjacent Duplicates) instead of trusting the stack — the whole point of using a stack here is that popping already exposes the next comparison for free; a fresh re-scan turns an O(n) solution back into O(n²).
• Forgetting the circular wraparound needs a bounded second pass (Next Greater Element II) — iterating 2n times but still pushing new indices on the second lap causes indices to be considered twice, corrupting the monotonic order.