Stacks, queues & monotonic stacks

Remember the recent past, in order. A stack is the right tool whenever the most-recent unresolved thing is the next to resolve; the monotonic-stack specialization answers "nearest greater/smaller element" for every position in a single O(n) sweep.

Why this pattern

A stack (LIFO) is the right tool whenever the MOST RECENT unresolved thing is the next to resolve: matching brackets, undo, nested structure, "the last open context." A queue (FIFO) is the right tool when order of arrival must be preserved: BFS frontiers, task pipelines. Python's list is a fine stack (append/pop are O(1)); use collections.deque for a queue (popleft is O(1), whereas list.pop(0) is O(n)).

The high-value specialization is the MONOTONIC STACK / DEQUE, which is what interviewers are usually probing for.

The monotonic-stack mental model

Trigger signal — phrased almost verbatim in the problem: "for each element, find the NEAREST greater/smaller element to its left/right" (next greater element, daily temperatures, stock span, largest rectangle, trapping rain).

Keep a stack of candidates that are still "waiting for their answer," kept in monotonic order (e.g. strictly decreasing). The INVARIANT: every element on the stack is still un-resolved, and they're ordered so that the newcomer resolves a contiguous run of them from the top.

When a new element arrives, POP WHILE THE NEW ELEMENT DOMINATES the stack top (e.g. new value > top for a decreasing stack). Each pop means "the newcomer is this popped element's answer (its next-greater)." Then push the newcomer.

Monotonic deque (sliding-window maximum). A deque variant supports a window that moves on BOTH ends: push new elements on the right (popping smaller ones, since they can never be the max while a bigger newer element exists), and pop from the LEFT when the front index slides out of the window. The front is always the current window maximum. O(n) total.

Plain stack uses

LeetCode 20 — Valid Parentheses

The most recent unmatched opener must be the first to close (LIFO). Push openers; on a closer, the stack top MUST be its match, else it's invalid. An empty stack at the end means everything matched.

def is_valid_parentheses(s: str) -> bool:
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in match:                       # a closer
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
        else:                                 # an opener
            stack.append(ch)
    return not stack

LeetCode 155 — Min Stack

push/pop/top/getMin all O(1). A second "mins" stack mirrors the main stack, where mins[i] is the minimum of everything at or below depth i. Each push records the running min (min of new value and previous min), so getMin is just mins[-1]. No scanning needed.

class MinStack:
    def __init__(self):
        self._data = []
        self._mins = []
    def push(self, x: int) -> None:
        self._data.append(x)
        self._mins.append(x if not self._mins else min(x, self._mins[-1]))
    def pop(self) -> None:
        self._data.pop()
        self._mins.pop()
    def top(self) -> int:
        return self._data[-1]
    def get_min(self) -> int:
        return self._mins[-1]

LeetCode 150 — Evaluate Reverse Polish Notation

In postfix, an operator applies to the two most recent operands — exactly LIFO. Push numbers; on an operator pop two, combine, push the result. Order matters for - and /: the deeper pop is the left operand.

def eval_rpn(tokens: List[str]) -> int:
    stack = []
    ops = {"+", "-", "*", "/"}
    for tok in tokens:
        if tok in ops:
            b = stack.pop()
            a = stack.pop()
            if tok == "+":
                stack.append(a + b)
            elif tok == "-":
                stack.append(a - b)
            elif tok == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))      # truncate toward zero
        else:
            stack.append(int(tok))
    return stack[-1]

LeetCode 71 — Simplify Path

Unix absolute path canonicalization. A path is a stack of directory names. "." is a no-op, ".." pops the last directory (if any), a real name pushes. Join the survivors.

def simplify_path(path: str) -> str:
    stack = []
    for part in path.split("/"):
        if part == "" or part == ".":
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

LeetCode 394 — Decode String

E.g. "3[a2[c]]" -> "accaccacc". Nesting ⇒ stack. On '[' push the (count, partial-string-so-far) context and reset; on ']' pop the context and append the just-built chunk repeated count times. The stack restores each enclosing context in LIFO order, which is exactly how nested brackets unwind.

def decode_string(s: str) -> str:
    stack = []                       # holds (prev_string, repeat_count)
    cur = ""
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append((cur, num))
            cur, num = "", 0
        elif ch == "]":
            prev, count = stack.pop()
            cur = prev + cur * count
        else:
            cur += ch
    return cur

Queue / deque

LeetCode 232 — Implement Queue using Stacks

An in stack receives pushes; an out stack serves pops. When out is empty, pour in into out, reversing order so the oldest element surfaces (FIFO from two LIFOs). Each element is moved at most once ⇒ O(1) amortized per op.

class MyQueue:
    def __init__(self):
        self._in = []
        self._out = []
    def push(self, x: int) -> None:
        self._in.append(x)
    def _shift(self) -> None:
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())
    def pop(self) -> int:
        self._shift()
        return self._out.pop()
    def peek(self) -> int:
        self._shift()
        return self._out[-1]
    def empty(self) -> bool:
        return not self._in and not self._out

Monotonic stack

LeetCode 496-style — Next Greater Element

For each index, the next greater element to its RIGHT (or -1 if none). Keep a stack of indices whose answer is still pending, in DECREASING value order. The newcomer pops every pending index it exceeds — it is their next-greater. Survivors stay waiting. Each index pushed/popped once ⇒ O(n).

def next_greater_elements(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [-1] * n
    stack = []                         # indices, nums[stack] strictly decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x       # x dominates this pending index
        stack.append(i)
    return ans

LeetCode 739 — Daily Temperatures

ans[i] = days until a warmer temperature (0 if none). Identical monotonic-stack skeleton, but store INDICES and report the DISTANCE (i - popped_index) instead of the value — the question asks "how many days," not "which temperature."

def daily_temperatures(temps: List[int]) -> List[int]:
    n = len(temps)
    ans = [0] * n
    stack = []                         # indices with decreasing temperature
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j             # days waited until warmer
        stack.append(i)
    return ans

LeetCode 84 — Largest Rectangle in Histogram

A bar's maximal rectangle extends left/right until it meets a SHORTER bar. A monotonic INCREASING stack of indices lets us, when a shorter bar arrives, pop each taller bar and finalize its rectangle: the popped bar's height times the width between the new shorter bar and the new stack top (the first shorter bar on the left). A sentinel 0 at the end flushes everything still on the stack.

def largest_rectangle_area(heights: List[int]) -> int:
    stack = []                         # indices with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):    # trailing 0 forces a final flush
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            # left boundary is the new top; width spans (top, i) exclusive
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

LeetCode 42 — Trapping Rain Water (monotonic-stack formulation)

Water sits in "valleys" bounded by a taller bar on each side. Keep a DECREASING stack of indices. When a taller bar arrives, the popped bar is a valley floor; water above it is bounded by min(left wall, right wall) minus the floor height, times the width between the two walls. Each bar is pushed/popped once ⇒ O(n).

def trap(height: List[int]) -> int:
    stack = []                         # indices, decreasing heights
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            floor = height[stack.pop()]
            if not stack:              # no left wall -> water spills out
                break
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], h) - floor
            water += width * bounded
        stack.append(i)
    return water

Monotonic deque

LeetCode 239 — Sliding Window Maximum

Maintain a deque of indices whose values are DECREASING. Pushing a new value evicts smaller values from the back (they can never be the max while a larger, newer value is present). Evict the front when its index falls out of the window [i-k+1, i]. The front index is always the window's maximum. Each index enters and leaves once ⇒ O(n).

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    dq = deque()                       # indices, nums[dq] decreasing
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x:        # smaller-and-older values are useless
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                    # front slid out of the window
            dq.popleft()
        if i >= k - 1:                        # window is full -> record its max
            out.append(nums[dq[0]])
    return out

Spot-checks: next_greater_elements([2,1,2,4,3]) == [4,2,4,-1,-1], largest_rectangle_area([2,1,5,6,2,3]) == 10, trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6, and max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7].