Stack Discipline

Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.

stack = []
stack.append(x)
stack.pop()

Bracket matching is the classic stack application. Must be instant for interview warm-ups.

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

Maintaining a parallel min stack gives O(1) getMin. Classic design problem.

self.stack.append(val)
self.min_stack.append(
    min(val, self.min_stack[-1] if self.min_stack else val)
)

Stack-based expression evaluation is the foundation for calculator and RPN problems.

for tok in tokens:
    if tok.lstrip('-').isdigit():
        stack.append(int(tok))
    else:
        b, a = stack.pop(), stack.pop()
        if tok == '+': stack.append(a + b)
        elif tok == '-': stack.append(a - b)
        elif tok == '*': stack.append(a * b)
        elif tok == '/': stack.append(int(a / b))

Monotonic stacks find next-greater/smaller elements in O(n). Key for histogram and temperature problems.

stack = []
for x in a:
    while stack and stack[-1] >= x:
        stack.pop()
    stack.append(x)

Next-greater-element uses a decreasing stack. Shows up in stock span and temperature problems.

result = [-1] * len(a)
stack = []
for i in range(len(a) - 1, -1, -1):
    while stack and stack[-1] <= a[i]:
        stack.pop()
    if stack:
        result[i] = stack[-1]
    stack.append(a[i])

Using a stack to reverse order is the intuition behind reversing linked lists and strings.

stack = []
for x in a:
    stack.append(x)
reversed_a = []
while stack:
    reversed_a.append(stack.pop())

Stack-based evaluation pops two operands per operator. Handles all four arithmetic ops.

st = []
for t in tokens:
    if t in '+-*/':
        b, a = st.pop(), st.pop()
        st.append(int(eval(f'{a}{t}{b}')))
    else:
        st.append(int(t))

Decreasing stack resolves waiting days when a warmer temperature arrives.

res = [0] * len(t)
st = []
for i, v in enumerate(t):
    while st and t[st[-1]] < v:
        j = st.pop()
        res[j] = i - j
    st.append(i)

Stack = most recent first (nesting, matching). Queue = oldest first (BFS, scheduling). Deque = both ends.

STACK (LIFO) vs QUEUE (FIFO)
────────────────────────────
STACK — Last In, First Out:
  "most recent" / "nested" / "matching"
  □ Parentheses matching
  □ Undo/redo
  □ DFS traversal (explicit stack)
  □ Monotonic stack (next greater element)
  □ Expression evaluation
  □ Call stack simulation

QUEUE — First In, First Out:
  "earliest" / "level-by-level" / "waiting line"
  □ BFS traversal (shortest path)
  □ Level-order tree traversal
  □ Task scheduling (FIFO order)
  □ Sliding window max (deque)
  □ Rate limiting (timestamp queue)

DEQUE — both ends:
  □ Sliding window maximum
  □ BFS optimizations
  □ Palindrome check

PRIORITY QUEUE (heap):
  □ "Next best" / "top K" / "median"
  □ Dijkstra, merge K sorted lists

Monotonic stack finds nearest greater/smaller in O(n). The key insight: popping means we found the answer for that element.

WHEN TO USE MONOTONIC STACK
───────────────────────────
SIGNAL PHRASES:
  "next greater/smaller element"
  "previous greater/smaller element"
  "span" / "days until warmer"
  "largest rectangle in histogram"
  "stock span problem"

PATTERN:
  stack = []  # stores indices, monotonic order
  for i in range(n):
      while stack and a[stack[-1]] < a[i]:  # or >
          j = stack.pop()
          # a[j]'s next greater is a[i]
          # a[j]'s previous greater is stack[-1] (if exists)
      stack.append(i)

MONOTONIC INCREASING STACK: finds next smaller
MONOTONIC DECREASING STACK: finds next greater

WHEN NOT monotonic stack:
  × Sliding window max → use deque (not just stack)
  × Need both prev AND next → two passes or one pass
  × No "nearest" relationship → wrong tool

COMPLEXITY: O(n) — each element pushed and popped once

RPN evaluation: numbers push, operators pop two and push result. Note: pop order is b, a (right operand first).

stack = []
for tok in tokens:
    if tok in '+-*/':
        b, a = stack.pop(), 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))
    else:
        stack.append(int(tok))