See through
the disguise.

Stack and queue in one pass

Both structures are discipline wrappers around an ordered collection. The discipline is what makes them powerful, not the data structure itself.

Start from the brute force

Canonical problem: given an array, find the next greater element (NGE) to the right of each position — the first element to the right that is strictly larger. Return -1 if none exists.

The O(n²) solution is obvious: for each element, scan right until you find a larger one or exhaust the array.

for i in 0..n:
    result[i] = -1
    for j in i+1..n:
        if arr[j] > arr[i]:
            result[i] = arr[j]
            break     # found NGE, stop inner scan

Now ask the diagnostic question: what is the brute force throwing away? Suppose you're scanning forward from index i and you reach index j where arr[j] > arr[i]. You just found i's NGE. But your scan also walked through every element between i+1 and j-1 — and for some of those elements, arr[j] is also their NGE. The brute force discards that realization and re-derives it from scratch in a later outer-loop iteration.

The question that derives the whole algorithm

Here it is, stated precisely: "When scanning right from i we find arr[j] > arr[i] — for every element between i and j that hasn't yet found its NGE, what does arr[j] tell us?"

Answer: if arr[j] is greater than any of those elements, it is their NGE too — because we're scanning left-to-right, so arr[j] is the first element to their right that beats them. We can settle all of their answers in that same moment, not separately.

This is the entire derivation. Keep a stack of indices whose NGE we haven't found yet. As we scan left to right, whenever we encounter a new element, it might be the NGE for several pending elements. Pop everything from the stack that it beats — those elements just found their answer. Then push the new element onto the stack as a new pending candidate.

The key identity: the stack contains exactly the elements that are still candidates — elements that have not yet encountered a greater element to their right. The moment a new element arrives that beats some of them, those candidates are no longer needed. They've found their answer and can be discarded permanently — no element to the right of j could have been their NGE, because j arrived first.

Widget A — monotonic stack in motion

The array below runs through eight elements. Each press of Step processes one element: first all pops (red cells found their answer), then the push of the current element. Toggle between next-greater and next-smaller to see that only the pop condition changes — the structural discipline is identical.

Notice the structural symmetry when you toggle modes. Next-greater pops when top < current; next-smaller pops when top > current. The stack's invariant flips its direction, but the algorithm skeleton — pop-while-condition, push, record answers for popped elements — does not change at all.

Increasing vs decreasing: which to reach for

The terminology is sometimes used inconsistently across sources. Use this framing and you won't get confused:

A subtler variant: previous greater / previous smaller element (looking left, not right). For those, process the array right-to-left with the same pop conditions, or process left-to-right and answer the question "what was already in the stack when this element was pushed" rather than "what gets popped when this element arrives." The stack discipline is unchanged.

For problems like Largest Rectangle in Histogram, the answer involves both the previous smaller and next smaller element for each bar. You can compute both in one left-to-right pass by reading answers from the stack at pop time (the element being popped gets next-smaller = current element) and at push time (the element being pushed gets previous-smaller = new stack top after the push).

Widget B — brute force vs monotonic, racing

Array [6, 5, 4, 3, 2, 1, 7] is a near-worst case for the brute force: every element except the last must scan all the way to index 6 to find its answer. Watch the comparison counters diverge — the stack's counter barely moves until the last step, then settles everything at once. That final burst is the amortized argument made visual.

The contrast at step 1 (outer element 6): BF does 6 comparisons scanning to the end. The stack does 0 — it just pushes. The stack's "debt" is paid at step 7, but it pays 6 comparisons total across all steps while BF pays 21. Each element in the stack is touched exactly twice: once pushed, once popped.

Nested structure validation

The classic nested-brackets problem — determine if a string of brackets is valid — is usually taught correctly, but the crucial motivating argument is often skipped: why a counter fails.

For a single bracket type, a counter works fine: increment on (, decrement on ), valid iff counter reaches 0 and never goes negative. But consider two bracket types and the string "([)]":

input:  (  [  )  ]
round:  +1  0   0  -1   → final = 0, opens = closes — counter says VALID
square: 0  +1  0  -1   → final = 0, opens = closes — counter says VALID

But "([)]" is INVALID — the round ) closes before the square [ closes,
violating nesting order. A counter only knows counts, not order.

A stack knows order because it remembers what was most recently opened. When you see a closing bracket, check the stack top: if it matches, pop and continue. If it doesn't match or the stack is empty, the string is invalid immediately — no need to look further. At the end, if the stack is empty, every opener was closed in the right order.

The rule also handles edge cases cleanly: stack empty when closing (extra closer), stack non-empty at end (unclosed opener). Both fall out of the same check without special cases.

This pattern extends to more complex nested structures: HTML/XML tag matching, matching function calls to returns in a call trace, validating that BEGIN/END blocks in a DSL are properly nested, or confirming that IF/ELSE/ENDIF in a bytecode instruction stream are well-formed.

Widget C — the stack as a tiny processor

A stack evaluating a postfix expression is a minimal computer: read a token stream left to right, push operands, and when you hit an operator pop two operands, compute, push the result. The same visual object — a stack — also validates bracket nesting. Toggle between modes to see both use cases side-by-side.

Notice that the bracket validation mode uses the same stack object for a fundamentally different purpose: instead of accumulating numeric values, it accumulates "pending unmatched openers." The instruction "pop and verify on each closer" is structurally identical to "pop two operands on each operator." This is not a coincidence — both are consuming a token stream with the stack acting as working memory for the most recent context.

Monotonic stack vs monotonic deque

Candidates consistently conflate these two because the mechanics look similar: in both cases you maintain a data structure in sorted order by evicting useless elements before pushing a new one. The difference is in the question being answered and the data structure required.

Practically, this means: if you see "maximum/minimum in a fixed-size sliding window," you need a deque. If you see "next/previous greater/smaller over the whole array," you need a stack. The Sliding Window topic covers the deque version in full; this topic owns the stack version. Do not conflate them under pressure — they are different algorithms serving different queries, and the interviewer will notice if you reach for a deque when a stack suffices or vice versa.

Recognition triggers — the checklist

Before spending 30 seconds trying to "figure out" a problem, run this list in 10 seconds. One hit is enough to start sketching.

The same object in real systems

A small stack-based virtual machine used to validate spending conditions in a ledger system is, mechanically, the exact same object as the postfix-expression-evaluator interview pattern: an instruction stream is processed left to right, values are pushed, operators pop their operands and push a result, and the final state of the stack determines the outcome — here, transaction validity instead of a numeric answer. The interview pattern is not a toy abstraction; it is the production architecture.

Implementing conditional control flow (IF/ELSE/ENDIF) inside such a VM requires the same "use a stack to remember where you are and to validate nesting is well-formed" discipline as bracket-matching validation — control flow blocks must close in the same order they opened, which is precisely the LIFO matching constraint that makes a counter insufficient and a stack necessary. The bracket-validation pattern you see in Section 6 of this topic is not a contrived problem; it is a real correctness concern in any bytecode interpreter.

More broadly: call stacks in real program execution are the literal origin of the word "stack" in computer science. When a function calls another, its local state is pushed onto the call stack; when it returns, its frame is popped. Stack overflow is a real error caused by pushing too many frames. The stack that saves and restores caller state is the exact same LIFO structure you're using in these problems — same invariant, same failure mode, different scale.

Problem set — 10

Ordered by difficulty. The first two are anchors that establish the baseline. Problems 4–8 are where Tier-1 custom banks live. Problem 10 is a deliberate contrast case, not new content — its purpose is to sharpen the stack-vs-deque boundary one final time.

Pseudocode

Runnable-logic-correct. The four patterns you'll reach for most often — copy the shape, not the syntax.

1. Balanced bracket validation (multi-type)

function is_valid(s):
    stack = []
    match = {']': '[', ')': '(', '}': '{'}
    for ch in s:
        if ch in {'(', '[', '{'}:
            stack.push(ch)          # opening bracket: remember it
        else:                       # closing bracket
            if stack.empty() or stack.top() != match[ch]:
                return False        # no matching opener, or wrong type
            stack.pop()             # matched — consume the opener
    return stack.empty()            # true iff every opener was closed

2. Monotonic stack — next greater element

function next_greater(arr):
    n = length(arr)
    result = [-1] * n               # default: no NGE found
    stack = []                      # stack of indices (not values)
    for i in 0..n-1:
        # Pop all indices whose NGE is arr[i]
        while stack not empty and arr[stack.top()] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.push(i)
    # Elements remaining in stack have no NGE → result stays -1
    return result

# To find next SMALLER element: flip the comparison to arr[stack.top()] > arr[i]

3. Postfix (RPN) expression evaluation

function eval_postfix(tokens):
    stack = []
    for tok in tokens:
        if tok is number:
            stack.push(to_int(tok))
        else:                       # tok is an operator (+, -, *, /)
            b = stack.pop()         # second operand (pushed later)
            a = stack.pop()         # first operand (pushed earlier)
            if   tok == '+': stack.push(a + b)
            elif tok == '-': stack.push(a - b)
            elif tok == '*': stack.push(a * b)
            elif tok == '/': stack.push(int(a / b))  # truncate toward zero
    return stack.pop()              # single remaining value is the answer

4. Queue using two stacks

class MyQueue:
    inbox  = []    # push stack: receives all enqueues
    outbox = []    # pop stack: serves all dequeues

    function enqueue(val):
        inbox.push(val)              # O(1) always

    function dequeue():
        if outbox.empty():           # outbox empty: transfer all from inbox
            while inbox not empty:
                outbox.push(inbox.pop())
        return outbox.pop()          # O(1) amortized: each element moves once

    function peek():
        if outbox.empty():
            while inbox not empty:
                outbox.push(inbox.pop())
        return outbox.top()

# Key insight: reversing a stack by popping into another stack reverses insertion order,
# converting LIFO (stack) into FIFO (queue). Each element crosses inbox→outbox exactly once.

Further reading