Stacks, queues & the monotonic stack

A stack is last-in-first-out (LIFO); a queue is first-in-first-out (FIFO). Both give O(1) push/pop. Stacks model nesting and 'most recent'; queues model order of arrival (and drive BFS).

• Stack: matching brackets, undo, DFS, expression evaluation, 'nearest previous' problems.
• Queue: BFS, task scheduling, streaming/first-come order. A deque adds both ends in O(1) (sliding-window maximum).

Balanced parentheses

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif not stack or stack.pop() != pairs[c]:
            return False
    return not stack

The monotonic stack

A monotonic stack keeps its elements in sorted order (increasing or decreasing) by popping anything that violates the order before pushing. It answers 'next greater / previous smaller element' for every position in O(n) total, because each element is pushed and popped at most once.

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []                       # holds indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x     # x is the next greater for that index
        stack.append(i)
    return res