1.6 Stacks & Queues

Deep Dive: The Monotonic Stack Pattern

Beginner tip: A stack is like a stack of plates -- you add and remove from the top only (Last In, First Out). A queue is like a line at a store -- first person in line is first to be served (First In, First Out). Stacks handle undo/redo and matching brackets. Queues handle scheduling and BFS.

Daily Temperatures -- "Next Greater Element"

temps = [73, 74, 75, 71, 69, 72, 76, 73]

Step  Temp  Stack(indices)  Action                    Result
  0    73   [0]             push                      [_,_,_,_,_,_,_,_]
  1    74   [1]             73<74: pop 0, ans[0]=1-0  [1,_,_,_,_,_,_,_]
  2    75   [2]             74<75: pop 1, ans[1]=2-1  [1,1,_,_,_,_,_,_]
  3    71   [2,3]           71<75: just push           ...
  4    69   [2,3,4]         69<71: just push           ...
  5    72   [2,5]           69<72: pop 4, ans[4]=1    [1,1,_,_,1,_,_,_]
                            71<72: pop 3, ans[3]=2    [1,1,_,2,1,_,_,_]
  6    76   [6]             72<76: pop 5, ans[5]=1    [1,1,4,2,1,1,_,_]
                            75<76: pop 2, ans[2]=4    [1,1,4,2,1,1,_,_]
  7    73   [6,7]           73<76: just push          [1,1,4,2,1,1,0,0]

Why the stack works: It holds indices of unresolved temperatures (waiting for a warmer day). When a warmer day arrives, it resolves all waiting entries that are cooler. Each index is pushed and popped at most once -> O(n).

Valid Parentheses -- Stack as Memory

Input: "({[]})"

Process '(' -> stack: ['(' ]
Process '{' -> stack: ['(', '{']
Process '[' -> stack: ['(', '{', '[']
Process ']' -> top='[' matches ']'. Pop. stack: ['(', '{']
Process '}' -> top='{' matches '}'. Pop. stack: ['(']
Process ')' -> top='(' matches ')'. Pop. stack: []
Stack empty -> VALID

The stack remembers the ORDER of opening brackets. The most recent opener must close first -- that is exactly LIFO.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Stacks & Queues

Why They Exist

• Stack (LIFO): Last thing in = first thing out. Like a stack of plates.
• Queue (FIFO): First thing in = first thing out. Like a line at a counter.

The Stack Mindset

Whenever you see nesting or matching or most recent first, think Stack.

Signal words: "matching parentheses", "next greater", "evaluate expression",
              "undo", "backtrack", "nested structure"

Monotonic Stack -- The Power Pattern

A monotonic stack maintains elements in sorted order (increasing or decreasing). It's the key to "next greater/smaller element" problems.

Idea: As you traverse, pop elements that violate the monotonic property.
      The element that causes the pop IS the answer for the popped element.

For "Next Greater Element":
  - Maintain a decreasing stack
  - For each new element: pop all smaller elements (you're their next greater)
  - Push current element

Monotonic Queue (Deque)

Same idea but for sliding window min/max. Maintains a window of candidates.

For "Sliding Window Maximum":
  - Maintain a decreasing deque of INDICES
  - Front of deque = current window max
  - Remove from back if new element is larger (they'll never be the max)
  - Remove from front if index is outside window

When You See a Stack/Queue Problem, Ask Yourself

1. Is there MATCHING / NESTING? (parentheses, tags) -> Stack
2. "Next greater/smaller element"? -> Monotonic Stack
3. "Evaluate expression"? -> Stack (operands) + maybe Stack (operators)
4. "Sliding window max/min"? -> Monotonic Deque
5. Need FIFO processing / level-order? -> Queue (BFS)

Common Mistakes

• Forgetting to check stack is not empty before stack.pop() or stack[-1]
• Monotonic stack: confusing increasing vs decreasing -- depends on whether you want next greater or next smaller
• Sliding Window Maximum: storing values instead of indices in the deque (need indices to check window bounds)

Problems

#	Problem	Difficulty	Pattern	Status
1	Valid Parentheses	Easy	Stack matching	[ ]
2	Min Stack	Medium	Stack + min tracking	[ ]
3	Daily Temperatures	Medium	Monotonic Stack	[ ]
4	Largest Rectangle in Histogram	Hard	Monotonic Stack	[ ]
5	Sliding Window Maximum	Hard	Monotonic Deque	[ ]
6	Evaluate Reverse Polish Notation	Medium	Stack evaluation	[ ]
7	Implement Queue using Stacks	Easy	Two stacks	[ ]
8	Basic Calculator	Hard	Recursive stack	[ ]

Notes