Stack Discipline

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