Ngăn xếp & hàng đợi

Bài trước ta có hai viên gạch lưu dữ liệu: mảng & danh sách liên kết. Giờ ta cố tình giới hạn cách thêm/bớt, và bất ngờ thu được hai công cụ cực kỳ hữu dụng.

Hình dung một chồng đĩa: bỏ đĩa mới lên trên, và khi lấy cũng lấy từ trên xuống. Cái đặt sau cùng lại được lấy đầu tiên - đó là ngăn xếp. Ngược lại, một hàng mua vé: ai đến trước được phục vụ trước, ai đến sau xếp xuống cuối - đó là hàng đợi.

• ▸Ngăn xếp (stack): vào sau ra trước - LIFO (Last In, First Out).
• ▸Hàng đợi (queue): vào trước ra trước - FIFO (First In, First Out).
• ▸Cả hai chỉ là mảng / danh sách bị giới hạn cách thêm-bớt, nên thao tác rất nhanh.

Ngăn xếp có ba thao tác, tất cả ở đỉnh (top): push (đẩy một phần tử lên đỉnh), pop (lấy phần tử ở đỉnh ra), và peek (nhìn đỉnh mà không lấy). Vì chỉ đụng tới một đầu, cả ba đều là O(1). Một mảng là quá đủ để làm ngăn xếp:

const undo: number[] = [];
undo.push(1); undo.push(2); undo.push(3); // lam 3 viec

console.log(undo.pop()); // hoan tac viec MOI nhat -> 3
console.log(undo.pop()); // -> 2
console.log(undo);       // con lai -> [ 1 ]

3
2
[ 1 ]

• ▸Thao tác: push (thêm đỉnh), pop (lấy đỉnh), peek (xem đỉnh) - đều O(1).
• ▸Ứng dụng: nút Undo, nút Back trình duyệt, và call stack của chương trình.
• ▸Lỗi “stack overflow” = đệ quy quá sâu, đẩy quá sức chứa của call stack.

Hàng đợi thêm vào cuối (enqueue) và lấy ra từ đầu (dequeue). Đúng như xếp hàng: người mới đứng xuống cuối, người đầu hàng được phục vụ rồi rời đi.

• ▸Thao tác: enqueue (thêm cuối), dequeue (lấy đầu), peek (xem đầu).
• ▸Cài đúng (danh sách có tail, hoặc mảng vòng) thì mọi thao tác là O(1).
• ▸Ứng dụng: hàng chờ in, lập lịch tác vụ, và duyệt theo chiều rộng (BFS) trên đồ thị.

Bấm Thêm để đẩy cùng một số vào cả ngăn xếp lẫn hàng đợi, rồi Lấy ra và để ý: hai cấu trúc trả về hai số khác nhau dù nhận đúng cùng một dãy đầu vào.

• ▸Cùng một chuỗi “thêm”, ngăn xếp và hàng đợi cho thứ tự lấy ra NGƯỢC nhau.
• ▸Ngăn xếp trả về số mới nhất; hàng đợi trả về số cũ nhất.
• ▸Chọn cấu trúc nào là chọn THỨ TỰ xử lý bạn muốn.

Ngoặc trong code lồng theo kiểu “mở sau phải đóng trước” - đúng tinh thần LIFO, nên ngăn xếp là công cụ hoàn hảo. Quét chuỗi: gặp ngoặc mở thì push; gặp ngoặc đóng thì pop ra cái mở gần nhất để so khớp. Hết chuỗi mà ngăn xếp rỗng nghĩa là mọi ngoặc đã khớp:

function ngoacCan(s: string): boolean {
  const stack: string[] = [];
  const cap: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (ch in cap) {
      if (stack.pop() !== cap[ch]) return false; // dong khong khop mo gan nhat
    }
  }
  return stack.length === 0; // con ngoac mo chua dong -> chua can
}

console.log(ngoacCan('([]{})')); // can
console.log(ngoacCan('([)]'));   // long sai thu tu
console.log(ngoacCan('(('));     // con ngoac mo

true
false
false

Ngăn xếp và hàng đợi không lưu thêm gì mới so với mảng/danh sách - chúng chỉ áp một kỷ luật về thứ tự (LIFO hay FIFO), và chính kỷ luật đó làm chúng hữu dụng. Hai cấu trúc này sẽ trở lại khi ta duyệt cây và đồ thị: ngăn xếp cho duyệt theo chiều sâu (DFS), hàng đợi cho duyệt theo chiều rộng (BFS).