Stack &
Queue

4.1 Stack là gì?

Stack là cấu trúc dữ liệu kiểu LIFO (Last In, First Out) — phần tử được thêm vào sau cùng sẽ là phần tử lấy ra đầu tiên. Như chồng đĩa: bạn úp đĩa lên trên, khi cần lấy đĩa, bạn lấy đĩa trên cùng.

Ba thao tác chính

• push(x) — thêm phần tử lên đầu — O(1)
• pop() — lấy và xoá phần tử trên cùng — O(1)
• peek() / top() — xem phần tử trên cùng (không xoá) — O(1)

     ┌─────┐
     │  5  │ ← top
     ├─────┤
     │  3  │
     ├─────┤
     │  1  │ ← bottom
     └─────┘

push(7) → top = 7
pop()   → trả về 7, top = 5

4.2 Cài đặt Stack

Cách 1 — Dùng Array (đơn giản nhất, hiệu quả)

// Stack bằng JS Array
class Stack {
  constructor() { this.data = []; }
  push(x)       { this.data.push(x); }
  pop()         { return this.data.pop(); }
  peek()        { return this.data[this.data.length - 1]; }
  isEmpty()     { return this.data.length === 0; }
  size()        { return this.data.length; }
}

const s = new Stack();
s.push(1); s.push(2); s.push(3);
console.log(s.pop());   // 3
console.log(s.peek());  // 2
console.log(s.size());  // 2

Trong JS, Array.push/pop đều O(1) amortized → đủ tốt cho mọi trường hợp. Không nên dùng shift vì nó O(n).

Cách 2 — Dùng Linked List

// Stack bằng Singly Linked List, push/pop ở head
class StackLL {
  constructor() { this.head = null; this.size = 0; }

  push(val) {
    this.head = { val, next: this.head };
    this.size++;
  }

  pop() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    this.size--;
    return val;
  }

  peek() { return this.head?.val; }
}

Bài kinh điển — Min Stack

Cài stack hỗ trợ thêm getMin() trong O(1). Đây là bài LeetCode 155, cực hay hỏi.

// Cách: dùng 2 stack — một stack thường, một stack min
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];  // luôn lưu min hiện tại ở top
  }
  push(x) {
    this.stack.push(x);
    if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(x);
    }
  }
  pop() {
    const x = this.stack.pop();
    if (x === this.minStack[this.minStack.length - 1]) this.minStack.pop();
    return x;
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

4.3 Ứng dụng Stack — bài toán kinh điển

4.3.1 Valid Parentheses

Kiểm tra chuỗi dấu ngoặc ()[]{} có hợp lệ không.

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isValid("()[]{}"));     // true
console.log(isValid("([)]"));       // false
console.log(isValid("{[]}"));       // true

4.3.2 Reverse string

function reverse(s) {
  const stack = [...s];
  let result = '';
  while (stack.length) result += stack.pop();
  return result;
}

4.3.3 DFS (sẽ học sâu ở Chương 11)

// DFS iterative dùng stack
function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
}

4.4 Queue là gì?

Queue là FIFO (First In, First Out) — phần tử thêm vào trước được lấy ra trước. Như xếp hàng mua vé: ai đến trước thì đi trước.

Hai thao tác chính

• enqueue(x) — thêm vào cuối (rear/tail) — O(1)
• dequeue() — lấy và xoá phần tử đầu (front/head) — O(1)
• peek() — xem phần tử đầu — O(1)

front                          rear
  ↓                              ↓
[ A ] [ B ] [ C ] [ D ] [ E ]
  →                              ←
dequeue                       enqueue

4.5 Cài đặt Queue trong JS

// ❌ shift() là O(n) → tổng O(n²)
const queue = [];
queue.push(1); queue.push(2);
queue.shift();  // O(n)!

Cách 1 — Index thủ công (đơn giản, đúng)

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
  }
  enqueue(x) {
    this.data.push(x);
  }
  dequeue() {
    if (this.head >= this.data.length) return undefined;
    const x = this.data[this.head];
    this.data[this.head] = undefined;  // giúp GC
    this.head++;

    // Compact array thỉnh thoảng để tiết kiệm bộ nhớ
    if (this.head > 50 && this.head * 2 > this.data.length) {
      this.data = this.data.slice(this.head);
      this.head = 0;
    }
    return x;
  }
  peek() {
    return this.data[this.head];
  }
  get size() {
    return this.data.length - this.head;
  }
}

Cách 2 — Linked List (clean nhất)

class QueueLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  enqueue(val) {
    const node = { val, next: null };
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
  dequeue() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.size--;
    return val;
  }
  peek() { return this.head?.val; }
}

Cách 3 — Circular Buffer (cho queue kích thước cố định)

class CircularQueue {
  constructor(capacity) {
    this.data = new Array(capacity);
    this.capacity = capacity;
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }
  enqueue(x) {
    if (this.size === this.capacity) throw new Error('Full');
    this.data[this.tail] = x;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
  }
  dequeue() {
    if (this.size === 0) return undefined;
    const x = this.data[this.head];
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return x;
  }
}

Circular buffer là cấu trúc dùng trong embedded systems, audio processing, IPC.

4.6 Deque — Double-ended Queue

Deque (đọc là "deck") là queue cho phép thêm/xoá ở cả hai đầu trong O(1). Vừa stack vừa queue.

• pushFront(x) / pushBack(x)
• popFront() / popBack()
• peekFront() / peekBack()

JS không có Deque built-in. Có thể dùng:

// Doubly Linked List làm deque
class Deque {
  constructor() { this.head = null; this.tail = null; this.size = 0; }

  pushFront(val) {
    const node = { val, prev: null, next: this.head };
    if (this.head) this.head.prev = node;
    else this.tail = node;
    this.head = node;
    this.size++;
  }

  pushBack(val) {
    const node = { val, prev: this.tail, next: null };
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
    this.size++;
  }

  popFront() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    if (this.head) this.head.prev = null;
    else this.tail = null;
    this.size--;
    return val;
  }

  popBack() {
    if (!this.tail) return undefined;
    const val = this.tail.val;
    this.tail = this.tail.prev;
    if (this.tail) this.tail.next = null;
    else this.head = null;
    this.size--;
    return val;
  }
}

4.7 Monotonic Stack/Deque — Pattern vàng

Monotonic Stack = stack mà các phần tử trong nó luôn theo thứ tự (tăng hoặc giảm). Khi push phần tử mới vi phạm thứ tự, ta pop hết các phần tử vi phạm.

4.7.1 Bài kinh điển: Next Greater Element

Cho mảng nums. Với mỗi phần tử, tìm phần tử lớn hơn nó tiếp theo bên phải. Nếu không có, trả về -1.

// Brute force — O(n²)
function nextGreaterBrute(nums) {
  const result = new Array(nums.length).fill(-1);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) {
        result[i] = nums[j];
        break;
      }
    }
  }
  return result;
}

// Monotonic Stack — O(n)
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];  // chứa indices, value tương ứng giảm dần
  for (let i = 0; i < nums.length; i++) {
    // Khi gặp số lớn hơn top stack, đó chính là next greater của top
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

// Demo: nums = [2, 1, 2, 4, 3, 1]
// stack: [], i=0, push 0  → stack=[0]
// i=1, nums[0]=2 > nums[1]=1 → push 1 → stack=[0,1]
// i=2, nums[1]=1 < 2 → pop 1, result[1]=2; nums[0]=2 NOT < 2 → push 2 → stack=[0,2]
// i=3, nums[2]=2 < 4 → pop 2, result[2]=4; nums[0]=2 < 4 → pop 0, result[0]=4; push 3 → stack=[3]
// ...
// result = [4, 2, 4, -1, -1, -1]

Tại sao O(n)? Mỗi phần tử push và pop tối đa 1 lần → tổng thao tác = 2n = O(n).

4.7.2 Bài: Daily Temperatures

// Cho mảng temperatures, trả về answer[i] = số ngày phải đợi
// để có nhiệt độ ấm hơn temperatures[i]
function dailyTemperatures(t) {
  const result = new Array(t.length).fill(0);
  const stack = [];
  for (let i = 0; i < t.length; i++) {
    while (stack.length && t[stack[stack.length - 1]] < t[i]) {
      const idx = stack.pop();
      result[idx] = i - idx;
    }
    stack.push(i);
  }
  return result;
}

// Input:  [73,74,75,71,69,72,76,73]
// Output: [1, 1, 4, 2, 1, 1, 0, 0]

4.7.3 Largest Rectangle in Histogram

Bài cực khó nhưng đẹp. Cho mảng độ cao các cột, tìm hình chữ nhật lớn nhất chứa trong histogram.

function largestRectangleArea(heights) {
  const stack = [];  // monotonic increasing stack of indices
  let maxArea = 0;
  // Append 0 ở cuối để pop hết stack
  heights = [...heights, 0];
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
      const h = heights[stack.pop()];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}

4.7.4 Monotonic Deque — Sliding Window Maximum

Cho mảng và k. Tìm max của mỗi cửa sổ kích thước k.

// Brute force — O(n × k)
// Monotonic Deque — O(n)
function maxSlidingWindow(nums, k) {
  const dq = [];  // chứa indices, value giảm dần
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // Loại bỏ index ngoài cửa sổ (bên trái)
    while (dq.length && dq[0] <= i - k) dq.shift();
    // Loại bỏ phần tử nhỏ hơn ở cuối deque (vì max sẽ không cần đến chúng nữa)
    while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
    dq.push(i);
    // Sau khi cửa sổ đầy, ghi nhận max (đầu deque)
    if (i >= k - 1) result.push(nums[dq[0]]);
  }
  return result;
}

// Demo: nums = [1,3,-1,-3,5,3,6,7], k = 3
// Output: [3, 3, 5, 5, 6, 7]

4.8 Expression Evaluation — Parse biểu thức bằng Stack

4.8.1 Postfix Evaluation (RPN)

RPN (Reverse Polish Notation) như "2 3 +" nghĩa là 2 + 3 = 5. Đánh giá bằng 1 stack:

function evalRPN(tokens) {
  const stack = [];
  for (const t of tokens) {
    if ('+-*/'.includes(t) && t.length === 1) {
      const b = stack.pop();
      const a = stack.pop();
      let r;
      switch (t) {
        case '+': r = a + b; break;
        case '-': r = a - b; break;
        case '*': r = a * b; break;
        case '/': r = Math.trunc(a / b); break;
      }
      stack.push(r);
    } else {
      stack.push(Number(t));
    }
  }
  return stack[0];
}

// evalRPN(["2","1","+","3","*"]) → ((2+1)*3) = 9
// evalRPN(["4","13","5","/","+"]) → (4 + 13/5) = 6

4.8.2 Infix to Postfix — Shunting Yard

Đây là thuật toán nổi tiếng của Dijkstra để chuyển "3 + 4 * 2" sang "3 4 2 * +".

function infixToPostfix(infix) {
  const prec = { '+': 1, '-': 1, '*': 2, '/': 2 };
  const ops = [];
  const output = [];
  for (const t of infix.split(' ')) {
    if (!isNaN(Number(t))) {
      output.push(t);
    } else if (t === '(') {
      ops.push(t);
    } else if (t === ')') {
      while (ops.length && ops[ops.length - 1] !== '(') {
        output.push(ops.pop());
      }
      ops.pop();  // bỏ '('
    } else {  // operator
      while (ops.length && ops[ops.length - 1] !== '(' && prec[ops[ops.length - 1]] >= prec[t]) {
        output.push(ops.pop());
      }
      ops.push(t);
    }
  }
  while (ops.length) output.push(ops.pop());
  return output.join(' ');
}

4.9 Stack từ Queue & ngược lại — bài phỏng vấn kinh điển

4.9.1 Implement Queue using two Stacks

class MyQueue {
  constructor() {
    this.in = [];   // dùng để enqueue
    this.out = [];  // dùng để dequeue
  }
  enqueue(x) { this.in.push(x); }

  dequeue() {
    if (this.out.length === 0) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out.pop();
  }

  peek() {
    if (this.out.length === 0) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out[this.out.length - 1];
  }
}
// Amortized O(1) cho mỗi op

4.9.2 Implement Stack using two Queues

// Cách 1: push O(n), pop O(1)
class MyStack {
  constructor() { this.q = []; }
  push(x) {
    this.q.push(x);
    // Đảo ngược queue: rotate n-1 lần
    for (let i = 0; i < this.q.length - 1; i++) {
      this.q.push(this.q.shift());
    }
  }
  pop()  { return this.q.shift(); }
  top()  { return this.q[0]; }
}

Bài tập

[5, 10, -5] → [5, 10] (-5 bị 10 nổ)
[8, -8]     → []      (cả hai nổ)
[10, 2, -5] → [10]    (-5 nổ 2 rồi nổ vào 10? Không — 10 sống)

Tổng kết chương 4

• ✅ Stack = LIFO; Queue = FIFO; Deque = cả hai
• ✅ Trong JS, Stack dùng arr.push/pop; Queue cần index hoặc linked list (KHÔNG shift)
• ✅ Monotonic Stack: O(n) cho Next Greater/Smaller
• ✅ Monotonic Deque: O(n) cho Sliding Window Max/Min
• ✅ Min Stack: dùng 2 stack để getMin O(1)
• ✅ Implement Queue using 2 Stacks: O(1) amortized — bài phỏng vấn kinh điển
• ✅ DFS = Stack, BFS = Queue (sẽ dùng nhiều ở Chương 11)