Pattern — Stack & Queue

Stack signal phrases

Khi nào nghĩ ngay đến Stack

• “Match parentheses / brackets”
• “Next greater / smaller / nearest”
• “Histogram / largest rectangle / trapping water”
• “Reverse a sequence”
• “Evaluate expression / RPN / calculator”
• “Iterative DFS”

Queue / Deque signal phrases

• “Level order / BFS”
• “Sliding window max/min”
• “Shortest path unweighted”
• “Round-robin / scheduling”

Templates

Monotonic stack — Next greater (decreasing stack)

const stack: number[] = [];   // indices
const res = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
  while (stack.length && nums[stack[stack.length-1]] < nums[i]) {
    res[stack.pop()!] = nums[i];
  }
  stack.push(i);
}

BFS với index pointer (O(1) dequeue)

const queue: T[] = [start];
let head = 0;                    // KHÔNG dùng .shift() (O(N))
while (head < queue.length) {
  const node = queue[head++];
  // process; queue.push(...) for neighbors
}

Monotonic deque — Sliding window max

const dq: number[] = [];        // indices, values decrease front→back
let head = 0;
for (let i = 0; i < n; i++) {
  if (head < dq.length && dq[head] < i - k + 1) head++;
  while (head < dq.length && nums[dq[dq.length-1]] <= nums[i]) dq.pop();
  dq.push(i);
  if (i >= k - 1) result.push(nums[dq[head]]);
}

Top problems

Bài	LC	Pattern
Valid Parentheses	LC #20	Stack
Daily Temperatures	LC #739	Monotonic stack
Largest Rectangle Histogram	LC #84	Monotonic stack + sentinel
Trapping Rain Water	LC #42	Monotonic stack hoặc 2-pointer
Sliding Window Max	LC #239	Monotonic deque
Implement Queue using Stacks	LC #232	2 stacks, amortized O(1)
Min Stack	LC #155	Stack + auxiliary min
Basic Calculator	LC #224	Stack-based parser
Decode String	LC #394	Stack-based parser
Online Stock Span	LC #901	Monotonic stack

Pitfalls (rất hay sai)

1. array.shift() O(N) trong queue — luôn dùng head index pointer hoặc proper Queue class. Xem 03-Stack-and-Queue § Pitfall 2.
2. Increasing vs decreasing stack — ngược nhau cho Next Greater vs Next Smaller. Quy tắc: “đuổi top khi gặp đối thủ mạnh hơn”.
3. Strict < vs <= — ảnh hưởng cách handle equal values (vd histogram).
4. Lưu indices không lưu values — để tính khoảng cách / chiều rộng.
5. Sentinel — push 0 vào cuối histogram để flush stack remaining.

→ Nguồn: 03-Stack-and-Queue, 03-Monotonic-Stack-Queue (FAANG Mastery)