Buổi 03 — Stack & Queue

Navigation

← 02-Linked-List-Dummy-Node | → 04-Recursion-and-Backtracking Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Mental Model — Stack

Stack = chồng đĩa ở buffet. Bạn chỉ có thể lấy đĩa trên cùng (pop) và đặt đĩa lên trên cùng (push). Đĩa đầu tiên được đặt vào sẽ là đĩa cuối cùng được lấy ra — LIFO: Last In, First Out.

Mental Model — Queue

Queue = hàng chờ ở quán cà phê. Người đến trước được phục vụ trước — FIFO: First In, First Out. Người mới đến xếp ở cuối hàng (enqueue), người được phục vụ rời từ đầu hàng (dequeue).

Mental Model — Deque

Deque (Double-Ended Queue) = toa tàu cho phép hành khách lên xuống từ cả hai đầu. Có thể push/pop từ cả front lẫn back — flexible nhất trong 3 loại.

Tại sao Stack và Queue quan trọng?

Stack = externalized call stack của recursion. Khi convert đệ quy → iterative, bạn quản lý stack thủ công.
Queue = backbone của BFS (Breadth-First Search). Mọi bài shortest path, level-order traversal đều cần queue.
Monotonic Stack (chủ đề nâng cao) = built directly on top of stack — giải quyết “next greater element” trong $O (N)$ .

2. The FAANG Standard

Tại sao Stack & Queue xuất hiện liên tục ở FAANG?

25% số bài Medium dùng stack ngầm — nhiều người không nhận ra vì đề không nói rõ.

Stack là “hidden structure” trong DFS, expression evaluation, undo/redo systems.

Queue là backbone của BFS — level-order tree traversal, shortest path in unweighted graph.

Monotonic Stack là pattern FAANG yêu thích: “Next Greater Element”, “Largest Rectangle”.

Những gì interviewer đánh giá:

Biết khi nào dùng stack vs queue (LIFO vs FIFO reasoning).
Hiểu Two-Stack Queue trick và amortized analysis.
Không dùng array.shift() cho queue — $O (N)$ là performance bug.
Biết convert recursive solution → iterative stack solution.

Common Mistake ở FAANG

Dùng array.shift() để dequeue trong JavaScript/TypeScript là O(N) — phải re-index toàn bộ array. Kỹ sư biết dùng index pointer trick hoặc linked list để đạt O(1).

3. Visual Thinking

Stack: Push & Pop

graph TD
    subgraph Before["Stack trước push(40)"]
        S1["TOP: 30<br/>────────<br/>20<br/>────────<br/>10<br/>BOTTOM"]
    end

    subgraph After["Stack sau push(40)"]
        S2["TOP: 40<br/>────────<br/>30<br/>────────<br/>20<br/>────────<br/>10<br/>BOTTOM"]
    end

    Before -->|"push(40)"| After
    After -->|"pop() → 40"| Before

    style Before fill:#4A90D9,color:#fff
    style After fill:#27AE60,color:#fff

Queue: Enqueue & Dequeue

graph LR
    subgraph Queue["Queue — FIFO"]
        direction LR
        QF["FRONT: 10"] --> Q2["20"] --> QB["30: BACK"]
    end

    E["enqueue(40)"] -.->|"add to back"| QB
    D["dequeue()"] -.->|"remove from front, returns 10"| QF

    style QF fill:#E74C3C,color:#fff
    style QB fill:#27AE60,color:#fff

Function Call Stack — Stack trong thực tế

graph TD
    subgraph CallStack["Call Stack khi gọi factorial(3)"]
        F3["factorial(3) — waiting for factorial(2)"]
        F2["factorial(2) — waiting for factorial(1)"]
        F1["factorial(1) — returns 1 (base case)"]
    end

    F3 -->|"calls"| F2
    F2 -->|"calls"| F1
    F1 -->|"returns 1"| F2
    F2 -->|"returns 2"| F3
    F3 -->|"returns 6"| DONE["Result: 6"]

    style F1 fill:#27AE60,color:#fff
    style DONE fill:#FFD700,color:#000

Two-Stack Queue — Amortized O(1)

graph LR
    subgraph TSQ["Two-Stack Queue"]
        IN["inStack<br/>(nhận enqueue)<br/>[3,2,1] top=3"]
        OUT["outStack<br/>(phục vụ dequeue)<br/>[] rỗng"]
    end

    E["enqueue(1,2,3)"] -->|"push lần lượt"| IN
    IN -->|"khi outStack rỗng:<br/>pour all → order reverses"| OUT
    OUT -->|"pop() = dequeue FIFO"| R["1 (first in, first out)"]

    style IN fill:#4A90D9,color:#fff
    style OUT fill:#E74C3C,color:#fff
    style R fill:#27AE60,color:#fff

4. TypeScript Template

4.1 — Generic Stack

/**
 * Generic Stack implementation với TypeScript.
 * Built on array — push/pop đều O(1) amortized.
 *
 * @template T - Kiểu dữ liệu của elements
 */
class Stack<T> {
  private items: T[] = [];
 
  /** Push element lên top — O(1) amortized */
  push(item: T): void {
    this.items.push(item);
  }
 
  /** Pop element từ top — O(1) | throws nếu empty */
  pop(): T {
    if (this.isEmpty()) throw new Error("Stack underflow — cannot pop from empty stack");
    return this.items.pop()!;
  }
 
  /** Peek top element mà không xóa — O(1) */
  peek(): T {
    if (this.isEmpty()) throw new Error("Stack is empty — cannot peek");
    return this.items[this.items.length - 1];
  }
 
  /** Kiểm tra stack rỗng — O(1) */
  isEmpty(): boolean {
    return this.items.length === 0;
  }
 
  /** Số lượng elements — O(1) */
  size(): number {
    return this.items.length;
  }
}

4.2 — Generic Queue using Two Stacks (Amortized O(1))

/**
 * LeetCode #232 — Implement Queue using Stacks
 *
 * KEY INSIGHT (Amortized Analysis):
 * - Mỗi element được push vào inStack đúng 1 lần → O(1) per enqueue.
 * - Khi outStack rỗng, "rót" toàn bộ inStack → O(1) amortized per element.
 * - Mỗi element được pop từ outStack đúng 1 lần → O(1) per dequeue.
 * - Tổng: O(3N) cho N operations = O(1) amortized mỗi operation.
 *
 * Worst case cho 1 dequeue: O(N) (khi phải pour toàn bộ inStack)
 * Nhưng amortized qua N dequeues: O(1) mỗi cái.
 *
 * @template T - Kiểu dữ liệu của elements
 */
class MyQueue<T> {
  private inStack: T[] = [];   // Nhận enqueue — top = phần tử vào sau cùng
  private outStack: T[] = [];  // Phục vụ dequeue/peek — top = phần tử vào đầu tiên
 
  /**
   * Thêm element vào cuối queue — O(1)
   */
  enqueue(item: T): void {
    this.inStack.push(item);
  }
 
  /**
   * Lấy và xóa element đầu queue — O(1) amortized
   * Nếu outStack rỗng: rót toàn bộ inStack vào outStack (đảo ngược thứ tự)
   */
  dequeue(): T {
    this.transferIfNeeded();
    if (this.outStack.length === 0) throw new Error("Queue is empty");
    return this.outStack.pop()!;
  }
 
  /**
   * Xem element đầu queue mà không xóa — O(1) amortized
   */
  peek(): T {
    this.transferIfNeeded();
    if (this.outStack.length === 0) throw new Error("Queue is empty");
    return this.outStack[this.outStack.length - 1];
  }
 
  isEmpty(): boolean {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
 
  /**
   * Rót inStack vào outStack chỉ khi outStack rỗng.
   * Thao tác đảo ngược thứ tự → FIFO được đảm bảo.
   *
   * Ví dụ: enqueue(1,2,3) → inStack = [1,2,3] (top=3)
   *        Pour → outStack = [3,2,1] (top=1)
   *        Pop outStack → trả về 1 (first in, first out) ✓
   */
  private transferIfNeeded(): void {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop()!);
      }
    }
  }
}

4.3 — Valid Parentheses

/**
 * LeetCode #20 — Valid Parentheses
 *
 * PATTERN: Stack-based matching
 * Mở ngoặc → push lên stack.
 * Đóng ngoặc → kiểm tra stack top có phải ngoặc mở tương ứng không.
 * Cuối cùng: stack phải rỗng (tất cả đã khớp).
 *
 * Time: O(N) | Space: O(N)
 *
 * @param s - Chuỗi chứa '(', ')', '{', '}', '[', ']'
 * @returns true nếu ngoặc hợp lệ
 *
 * @example
 * isValid("()[]{}") → true
 * isValid("([)]")  → false  (sai thứ tự)
 * isValid("{[]}")  → true   (lồng nhau đúng)
 */
function isValid(s: string): boolean {
  const stack: string[] = [];
  const matchMap: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  };
 
  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      // Ngoặc mở: push vào stack để chờ khớp sau
      stack.push(char);
    } else {
      // Ngoặc đóng: top của stack PHẢI là ngoặc mở tương ứng
      if (stack.length === 0 || stack[stack.length - 1] !== matchMap[char]) {
        return false;
      }
      stack.pop(); // Khớp thành công → pop ngoặc mở ra
    }
  }
 
  // Stack rỗng = tất cả ngoặc đã được khớp
  return stack.length === 0;
}

4.4 — Min Stack với O(1) getMin

/**
 * LeetCode #155 — Min Stack
 *
 * CHALLENGE: getMin() phải là O(1), không phải O(N) scan.
 *
 * APPROACH: Dùng 2 stacks song song.
 * - `stack`: chứa tất cả values bình thường.
 * - `minStack`: top luôn là minimum của toàn bộ stack tại thời điểm đó.
 *   Chỉ push khi val <= current min.
 *   Chỉ pop khi val === current min.
 *
 * Time: O(1) cho mọi thao tác | Space: O(N)
 */
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = []; // top = giá trị nhỏ nhất hiện tại
 
  /**
   * Push val — O(1)
   * Cập nhật minStack nếu val <= current min.
   */
  push(val: number): void {
    this.stack.push(val);
    // Push vào minStack nếu: minStack rỗng, hoặc val nhỏ hơn/bằng min hiện tại
    if (
      this.minStack.length === 0 ||
      val <= this.minStack[this.minStack.length - 1]
    ) {
      this.minStack.push(val);
    }
  }
 
  /**
   * Pop — O(1)
   * Nếu pop ra chính là minimum hiện tại → minStack cũng phải pop.
   */
  pop(): void {
    const popped = this.stack.pop()!;
    if (popped === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }
 
  /** Top của stack — O(1) */
  top(): number {
    return this.stack[this.stack.length - 1];
  }
 
  /** Minimum của toàn bộ stack hiện tại — O(1) */
  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}
 
/*
 * TRACE THROUGH:
 * push(5): stack=[5],     minStack=[5]
 * push(3): stack=[5,3],   minStack=[5,3]
 * push(7): stack=[5,3,7], minStack=[5,3]   ← 7 > 3, không push minStack
 * getMin() → 3 ✓
 * pop():    stack=[5,3],   minStack=[5,3]   ← 7 != 3, minStack không đổi
 * getMin() → 3 ✓
 * pop():    stack=[5],     minStack=[5]     ← 3 == 3, pop minStack cũng
 * getMin() → 5 ✓
 */

4.5 — Largest Rectangle in Histogram (Monotonic Stack)

/**
 * LeetCode #84 — Largest Rectangle in Histogram
 *
 * BRUTE FORCE: O(N²) — với mỗi cặp (i,j), tính min(heights[i..j]) * (j-i+1).
 *
 * DỄ HIỂU NHẤT — 2 passes với Monotonic Increasing Stack: O(N)
 *
 * KEY INSIGHT:
 * Một rectangle bị giới hạn bởi bar THẤP NHẤT trong range của nó.
 * Với mỗi bar heights[i], rectangle lớn nhất dùng heights[i] làm chiều cao là:
 *   width = (next smaller element index) - (previous smaller element index) - 1
 *
 * THAY VÌ gộp mọi thứ vào 1 loop, tách thành 3 bước dễ hiểu:
 * 1. Tìm previous smaller cho từng i.
 * 2. Tìm next smaller cho từng i.
 * 3. Tính area = heights[i] * (right[i] - left[i] - 1).
 *
 * STACK LƯU GÌ: indices, duy trì heights tăng dần.
 * - left[i]  = index bar thấp hơn gần nhất bên trái i
 * - right[i] = index bar thấp hơn gần nhất bên phải i
 *
 * Time: O(N) — mỗi bar được push và pop đúng 1 lần.
 * Space: O(N) — stack + 2 arrays left/right.
 *
 * @param heights - Array chiều cao của các bars
 * @returns Diện tích hình chữ nhật lớn nhất
 *
 * @example
 * largestRectangleArea([2,1,5,6,2,3]) → 10
 * largestRectangleArea([2,4])         → 4
 */
function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const left = new Array<number>(n).fill(-1);
  const right = new Array<number>(n).fill(n);
  const stack: number[] = [];
  let maxArea = 0;
 
  // Pass 1: previous smaller element cho từng i
  for (let i = 0; i < n; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
      stack.pop();
    }
    left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(i);
  }
 
  stack.length = 0;
 
  // Pass 2: next smaller element cho từng i
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= heights[i]) {
      stack.pop();
    }
    right[i] = stack.length === 0 ? n : stack[stack.length - 1];
    stack.push(i);
  }
 
  // Pass 3: mỗi bar làm chiều cao một lần
  for (let i = 0; i < n; i++) {
    const width = right[i] - left[i] - 1;
    maxArea = Math.max(maxArea, heights[i] * width);
  }
 
  return maxArea;
}
 
/*
 * TRACE THROUGH với [2,1,5,6,2,3]:
 * Indices:                0 1 2 3 4 5
 * Heights:                2 1 5 6 2 3
 *
 * previous smaller (left):
 * left =  [-1,-1, 1, 2, 1, 4]
 *
 * next smaller (right):
 * right = [ 1, 6, 4, 4, 6, 6]
 *
 * Tính area cho từng bar:
 * i=0: h=2, width=1-(-1)-1=1 → area=2
 * i=1: h=1, width=6-(-1)-1=6 → area=6
 * i=2: h=5, width=4-1-1=2    → area=10  ← MAX!
 * i=3: h=6, width=4-2-1=1    → area=6
 * i=4: h=2, width=6-1-1=4    → area=8
 * i=5: h=3, width=6-4-1=1    → area=3
 *
 * maxArea = 10 ✓
 */

Advanced Version

Sau khi hiểu rõ previous smaller và next smaller, bạn có thể học bản 1 pass + sentinel height=0 để gộp 2 arrays vào một loop. Bản đó gọn hơn nhưng khó trace hơn cho người mới.

5. Complexity Deep-dive

Stack & Queue Operations

Thao tác	Stack (Array)	Queue (2 Stacks)	Queue (Linked List)
Push / Enqueue	$O (1)$ amortized	$O (1)$	$O (1)$
Pop / Dequeue	$O (1)$	$O (1)$ amortized	$O (1)$
Peek	$O (1)$	$O (1)$ amortized	$O (1)$
isEmpty	$O (1)$	$O (1)$	$O (1)$
Space	$O (N)$	$O (N)$	$O (N)$

Tại sao Two-Stack Queue là O(1) Amortized?

Amortized Analysis — Accounting Method

Gán “cost token” cho mỗi element được enqueue:

enqueue: trả 2 tokens (1 cho push vào inStack, 1 dự phòng cho lần transfer sau).

Khi transfer xảy ra: mỗi element dùng token dự phòng của mình → không tốn thêm.

dequeue: 1 token cho pop từ outStack.

Tổng tokens dùng = $O (3 N)$ cho $N$ operations = $O (1)$ amortized mỗi cái.

Worst case cho 1 dequeue: $O (N)$ (khi transfer toàn bộ inStack). Nhưng sau đó $N$ lần dequeue tiếp theo đều $O (1)$ → amortized $O (1)$ .

Histogram: Stack vs Brute Force

Approach	Time	Space	Ghi chú
Brute Force	$O (N^{2})$	$O (1)$	2 vòng lặp lồng nhau
Monotonic Stack	$O (N)$	$O (N)$	Mỗi element push/pop đúng 1 lần

6. Edge Cases & Pitfalls

Pitfall 1: Pop/Peek trên Empty Stack

// SAI — không guard empty check, có thể return undefined và gây bug ở dưới
const top = stack.pop();
processValue(top); // top có thể là undefined!
 
// ĐÚNG — luôn kiểm tra trước
if (stack.length > 0) {
  const top = stack.pop()!;
  processValue(top);
}
// Hoặc ném lỗi sớm (fail fast):
pop(): T {
  if (this.isEmpty()) throw new Error("Stack underflow");
  return this.items.pop()!;
}

Pitfall 2: Dùng array.shift() cho Queue — O(N)!

// SAI — shift() là O(N) vì JavaScript phải re-index toàn bộ array
const queue: number[] = [];
queue.push(1);           // enqueue — O(1) amortized, ổn
const front = queue.shift(); // dequeue — O(N) PERFORMANCE BUG!
 
// ĐÚNG Option A — index pointer trick, O(1) dequeue
class EfficientQueue<T> {
  private items: T[] = [];
  private headIndex = 0;
 
  enqueue(item: T): void {
    this.items.push(item);
  }
 
  dequeue(): T | undefined {
    if (this.headIndex >= this.items.length) return undefined;
    return this.items[this.headIndex++]; // O(1) — chỉ tăng pointer
  }
}
 
// ĐÚNG Option B — dùng Two-Stack Queue (xem code block 4.2 ở trên)

Pitfall 3: Quên Pop Sau Khi Match

// Valid Parentheses — lỗi phổ biến: check nhưng quên pop
for (const char of s) {
  if (char === ')') {
    if (stack[stack.length - 1] === '(') {
      // SAI: kiểm tra xong nhưng không xóa khỏi stack!
      // '(' vẫn còn trong stack → kết quả sai
    }
  }
}
 
// ĐÚNG: phải pop sau khi match
if (stack[stack.length - 1] === '(') {
  stack.pop(); // Bắt buộc!
}

Pitfall 4: Stack Overflow với Deep Recursion

// Recursion sâu → JavaScript call stack overflow (~10,000 frames)
function sumDeep(n: number): number {
  return n === 0 ? 0 : n + sumDeep(n - 1); // Crash với n = 100,000
}
 
// ĐÚNG — convert sang iterative với explicit stack
function sumIterative(n: number): number {
  let result = 0;
  for (let i = 1; i <= n; i++) result += i;
  return result;
  // Hoặc: n * (n + 1) / 2
}

7. Pattern Recognition

Nhận Diện Stack & Queue Problems

Từ khóa	Pattern	LeetCode
”valid parentheses/brackets”	Stack: push open, pop on close	#20
”min/max at each step”	Min Stack / Monotonic Stack	#155
”next greater/smaller element”	Monotonic Stack (nâng cao)	#496, #739
”evaluate expression”	Stack: operand push, operator pop-evaluate	#150, #224
”implement queue with stack”	Two-Stack Queue	#232
”decode string / nested”	Stack: lưu (count, string) pairs	#394
”simplify path”	Stack: split by ’/’, handle ”..”	#71
”BFS / level order traversal”	Queue	#102, #127
”daily temperatures”	Monotonic Stack: next greater index	#739
”largest rectangle / container”	Monotonic Stack: prev/next smaller	#84, #42

Stack = Externalized Recursion Call Stack

Bất kỳ bài nào có thể giải bằng DFS (đệ quy) đều có thể giải bằng explicit stack (iterative). Hiểu nguyên tắc này giúp:

Tránh stack overflow với input lớn ( $N > 10, 000$ ).

Kiểm soát memory — biết rõ depth tối đa.

Debug dễ hơn — bạn thấy được state của stack tại mọi thời điểm.

8. Top LeetCode Problems

#	Tên	Độ khó	Pattern	Priority
20	Valid Parentheses	Easy	Stack matching	Must-do
232	Implement Queue using Stacks	Easy	Two-stack queue	Must-do
155	Min Stack	Medium	Auxiliary min stack	Must-do
394	Decode String	Medium	Stack: (count, str) pairs	High
739	Daily Temperatures	Medium	Monotonic stack	High
84	Largest Rectangle in Histogram	Hard	Monotonic stack	High
150	Evaluate Reverse Polish Notation	Medium	Stack: operand/operator	Medium
71	Simplify Path	Medium	Stack: split + handle ”..”	Medium
496	Next Greater Element I	Easy	Monotonic stack intro	Medium
42	Trapping Rain Water	Hard	Monotonic stack / two-pointer	Stretch

Học Monotonic Stack sau khi nắm vững Stack cơ bản

Monotonic Stack là một trong những patterns hay xuất hiện nhất ở FAANG level Medium/Hard. Sau buổi này, xem thêm buổi “Monotonic Stack” để deep dive vào #739, #496, #42, #85.

9. Self-Assessment Checklist

Checklist trước khi chuyển sang buổi tiếp theo

Kiến thức nền:

Giải thích LIFO vs FIFO — cho ví dụ thực tế ngoài buffet và coffee shop.
Giải thích tại sao array.shift() là O(N) và ít nhất 2 cách khắc phục.
Giải thích amortized O(1) của Two-Stack Queue bằng “accounting method”.
Giải thích tại sao Stack là “externalized recursion call stack”.

Code từ memory (không nhìn):

Viết được isValid (valid parentheses) trong < 5 phút.
Viết được MinStack với O(1) getMin trong < 8 phút.
Viết được MyQueue với two stacks trong < 8 phút.
Sketch được core logic của Monotonic Stack cho Histogram.

Hiểu sâu:

Trace through largestRectangleArea([2,1,5,6,2,3]) bằng tay — điền đúng left[], right[], rồi tính width.
Giải thích công thức width = right[i] - left[i] - 1 đến từ đâu.
Convert DFS tree traversal từ recursive sang iterative dùng explicit stack.

Stretch goal:

Solve được #42 Trapping Rain Water bằng Monotonic Stack approach.
Implement #739 Daily Temperatures — “next warmer day” bằng monotonic stack.
Solve #84 mà không nhìn solution sau khi nắm được key insight.

Xem tiếp: 04-Recursion-and-Backtracking — Recursion = matryoshka dolls, Backtracking = maze solving

lthieu's notes

Explorer

03-Stack-and-Queue

Buổi 03 — Stack & Queue

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking

Stack: Push & Pop

Queue: Enqueue & Dequeue

Function Call Stack — Stack trong thực tế

Two-Stack Queue — Amortized O(1)

4. TypeScript Template

4.1 — Generic Stack

4.2 — Generic Queue using Two Stacks (Amortized O(1))

4.3 — Valid Parentheses

4.4 — Min Stack với O(1) getMin

4.5 — Largest Rectangle in Histogram (Monotonic Stack)

5. Complexity Deep-dive

Stack & Queue Operations

Tại sao Two-Stack Queue là O(1) Amortized?

Histogram: Stack vs Brute Force

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks