Chapter 4 · Stacks, queues, and windows¶

Choose a linear structure by asking which pending item must leave next.

Required removal order	Structure	Typical signals
newest first	stack	nesting, undo, next greater, DFS
oldest first	queue	levels, arrival order, BFS
best priority first	heap	repeated min/max, top-k, Dijkstra
either end	deque	window extrema, 0–1 BFS

Thinking flow · Which item must leave next?¶

flowchart TD
  accTitle: Choosing a stack, queue, deque, heap, or sliding window
  accDescr: For pending work, choose a stack when the newest item resolves first, a queue when the oldest or shallowest resolves first, a heap when priority decides, and a deque when either end is needed. For a contiguous active range, use a sliding window for monotone validity and a monotonic deque for repeated window extrema.
  A{"Are these pending items<br/>or a contiguous range?"}
  A -->|"pending items"| B{"What determines<br/>the next removal?"}
  B -->|"newest / most nested"| C["Stack"]
  B -->|"oldest / shallowest layer"| D["Queue"]
  B -->|"best numeric priority"| E["Heap"]
  B -->|"front or back"| F["Deque"]
  A -->|"contiguous range"| G{"What query drives<br/>boundary movement?"}
  G -->|"validity becomes monotone"| H["Sliding window"]
  G -->|"extreme in every<br/>fixed window"| I["Monotonic deque"]
  G -->|"arbitrary range queries"| J["Prefix or indexed tree;<br/>not a plain window"]

The structure is chosen by the removal contract. DFS and BFS, for example, may visit the same states; stack versus queue changes which pending state is expanded next.

Monotonic deque¶

For the maximum of every fixed-size window, the deque stores indices, not values. Indices are needed to expire old entries.

Invariant: indices are live, ordered by position, and their values decrease from front to back.

flowchart TD
  accTitle: Updating a monotonic deque
  accDescr: For each new index, remove expired indices from the front, remove dominated values from the back, append the new index, and emit the front when the window is complete.
  A["Receive new index i"] --> B{"Front is outside<br/>the window?"}
  B -->|yes| C["Pop front"]
  C --> B
  B -->|no| D{"Back value ≤<br/>values[i]?"}
  D -->|yes| E["Pop back"]
  E --> D
  D -->|no| F["Append i"]
  F --> G{"Window complete?"}
  G -->|yes| H["Emit value at front"]
  G -->|no| I["Advance"]
  H --> I

PythonC++17C++11

def max_sliding_window(values: Sequence[int], window: int) -> list[int]:
    """Return the maximum in every complete fixed-size window."""
    if window <= 0 or window > len(values):
        raise ValueError("window must be between 1 and len(values)")

    candidates: deque[int] = deque()
    answer: list[int] = []
    for right, value in enumerate(values):
        # Remove indices that have left the current window.
        while candidates and candidates[0] <= right - window:
            candidates.popleft()
        # Remove smaller values that can never become a future maximum.
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(right)
        if right + 1 >= window:
            # The front is the largest live candidate.
            answer.append(values[candidates[0]])
    return answer

inline std::vector<int> max_sliding_window(
    const std::vector<int>& values, int window) {
  if (window <= 0 || window > static_cast<int>(values.size())) {
    throw std::invalid_argument("window must be between 1 and values.size()");
  }
  std::deque<int> candidates;
  std::vector<int> answer;
  for (int right = 0; right < static_cast<int>(values.size()); ++right) {
    // Expire indices that have left the current window.
    while (!candidates.empty() && candidates.front() <= right - window) {
      candidates.pop_front();
    }
    // Remove dominated values that can never become a future maximum.
    while (!candidates.empty() &&
           values[candidates.back()] <= values[right]) {
      candidates.pop_back();
    }
    candidates.push_back(right);
    if (right + 1 >= window) {
      // The front is the largest live candidate.
      answer.push_back(values[candidates.front()]);
    }
  }
  return answer;
}

inline std::vector<int> max_sliding_window(
    const std::vector<int>& values, int window) {
  if (window <= 0 || window > static_cast<int>(values.size())) {
    throw std::invalid_argument("window must be between 1 and values.size()");
  }
  std::deque<int> candidates;
  std::vector<int> answer;
  for (int right = 0; right < static_cast<int>(values.size()); ++right) {
    // Expire indices that have left the current window.
    while (!candidates.empty() && candidates.front() <= right - window) {
      candidates.pop_front();
    }
    // Remove dominated values that can never become a future maximum.
    while (!candidates.empty() &&
           values[candidates.back()] <= values[right]) {
      candidates.pop_back();
    }
    candidates.push_back(right);
    if (right + 1 >= window) {
      // The front is the largest live candidate.
      answer.push_back(values[candidates.front()]);
    }
  }
  return answer;
}

Every index enters and leaves at most once, so the total time is O(n).

Stack as unresolved work¶

A monotonic stack stores candidates whose answer has not yet appeared. When a new value dominates the top, resolve and pop until the invariant returns.

For “next greater element,” the stack usually stores indices so the result can record positions or distances. Decide whether equal values should pop by reading the exact comparison rule.

Heap as a bounded frontier¶

To keep the k largest values, maintain a min-heap of size at most k. The root is the weakest survivor. Each new value enters, and an excess root is removed.

Invariant: after processing any prefix, the heap contains its k largest values (or the entire prefix if it contains fewer than k values).

Boundary questions¶

Is the window fixed or variable?
Does validity change monotonically as the left edge moves?
Do equal values dominate one another?
Must stale heap entries be removed lazily?
Can k be zero or larger than the input?

Practice ladder · identify the expiration rule¶

Rung	Problem	Thinking prompt
1	Valid Parentheses	What unmatched obligation belongs on the stack?
2	Daily Temperatures	Which earlier indices does the new value resolve?
3	Longest Substring Without Repeating Characters	What forces the left boundary forward?
4	Sliding Window Maximum	Which candidates expire, and which are dominated?

Write the container's order, membership, and removal condition before the loop.