Chuyển tới nội dung chính

Ứng dụng stack & queue

Bạn sẽ học được gì

Stack và queue đơn giản nhưng giải được vô số bài. Bạn sẽ thấy bức tranh ứng dụng của cả hai, và học kỹ một bài kinh điển: kiểm tra cặp ngoặc cân bằng bằng stack.

1. Stack giải gì? Queue giải gì?​

Stack (LIFO)Queue (FIFO)
Kiểm tra cặp ngoặc cân bằngBFS (duyệt đồ thị theo lớp)
Undo / RedoHàng đợi tác vụ, hàng in
Ngăn xếp lời gọi hàm, đệ quyXử lý yêu cầu máy chủ theo thứ tự
DFS (duyệt theo chiều sâu)Lập lịch round-robin của CPU
Tính biểu thức (hậu tố)Bộ đệm luồng dữ liệu

Mẹo nhớ: cần xử lý cái mới nhất / quay lui → stack. Cần xử lý theo thứ tự đến / theo lớp → queue.

2. Bài kinh điển: cặp ngoặc cân bằng​

Cho chuỗi ngoặc như "([]{})", kiểm tra mọi ngoặc có đóng đúng cặp, đúng thứ tự không. Ý tưởng với stack: gặp ngoặc mở thì push; gặp ngoặc đóng thì nó phải khớp với ngoặc mở gần nhất (chính là đỉnh stack).

🐞 Kiểm tra "([])" cân bằngBước 1/6
1def can_bang(s):
2  stack = []
3  khop = {')':'(', ']':'[', '}':'{'}
4  for c in s:
5      if c in "([{":
6          stack.append(c)
7      else:
8          if not stack or stack.pop() != khop[c]:
9              return False
10  return not stack
Biến tại bước này
stack[]
👉 Chuỗi: ( [ ] )

Nếu cuối cùng stack không rỗng → có ngoặc mở chưa đóng → không cân bằng. Nếu pop ra không khớp → sai cặp.

3. Code mẫu (chạy thật)​

Đang tải trình chạy code…

"([)]" sai vì ngoặc lồng nhau không đúng — stack phát hiện ngay khi ) không khớp đỉnh [.

4. Vì sao stack hợp với "khớp cặp gần nhất"?​

Ngoặc đóng luôn phải khớp ngoặc mở gần nhất chưa đóng — đúng là phần tử đỉnh stack (vào sau cùng). Bất kỳ bài nào có dạng "cái đóng phải khớp cái mở gần nhất" (thẻ HTML, biểu thức, lồng nhau) đều là dấu hiệu dùng stack.

5. Mẫu nhận diện​

  • "Cặp ngoặc/thẻ", "lồng nhau", "khớp cái gần nhất", "undo" → stack.
  • "Theo lớp", "lan toả từng vòng", "thứ tự đến trước" → queue (BFS sẽ học ở Trụ 3).
  • Biểu thức, quay lui, DFS → stack (hoặc đệ quy).

6. 🎮 Trò chơi: Stack hay queue?​

🎮 Stack hay queue?Câu 1/5· Điểm 0· 🔥 0

Mới nhất/quay lui/khớp gần nhất → stack. Theo thứ tự đến/theo lớp → queue.

Kiểm tra cặp ngoặc cân bằng.

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Cấu trúc nào hợp để kiểm tra cặp ngoặc cân bằng?
2. Sau khi duyệt hết chuỗi, stack KHÔNG rỗng nghĩa là?
3. BFS (duyệt theo lớp) dùng cấu trúc nào?

8. Hoàn thành — XONG Chương 2.3! 🎉​

…

☑️ Hết Chương 2.3 (Ngăn xếp & Hàng đợi). Tiếp theo: 2.4.1 — Bảng băm (Hash table).