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

Hàng đợi (Queue)

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

Hàng đợi (queue) là cấu trúc "vào trước ra trước" (FIFO) — như xếp hàng mua vé. Bạn sẽ học các thao tác của nó, một bẫy hiệu năng kinh điển trong Python, và cách cài đúng.

1. Trực quan: xếp hàng mua vé​

Queue giống hàng người xếp mua vé: ai đến trước được phục vụ trước. Thêm vào cuối hàng, lấy ra ở đầu hàng. Đó là FIFO — First In, First Out.

   dequeue ◀──┐                       ┌──◀ enqueue
              │                       │
        ┌─────┴─┬───────┬───────┬─────┴─┐
   ra ◀ │  10   │  20   │  30   │  40   │ ◀ vào
        └───────┴───────┴───────┴───────┘
         đầu (front)              cuối (rear)

So với stack (LIFO, lấy ở đỉnh), queue lấy ở đầu — ngược đầu với nơi thêm vào.

2. Hai thao tác chính​

Thao tácÝ nghĩa
enqueue(x)thêm x vào cuối hàng
dequeue()lấy & bỏ phần tử ở đầu hàng

Cả hai nên là O(1) — nhưng cài sai thì không (xem mục 4).

3. Chạy debug: enqueue rồi dequeue​

Bước qua để thấy FIFO: phần tử vào trước (1) ra trước.

🐞 enqueue 1, 2, 3 rồi dequeueBước 1/5
1from collections import deque
2q = deque()
3q.append(1)        # enqueue 1
4q.append(2)        # enqueue 2
5q.append(3)        # enqueue 3
6x = q.popleft()    # dequeue -> lay DAU
Biến tại bước này
q[]
👉 Hàng đợi rỗng.

4. Bẫy: đừng dùng list.pop(0) làm queue​

Trông có vẻ list làm queue được: append để enqueue, pop(0) để dequeue. NHƯNG pop(0) phải dịch toàn bộ mảng → O(n) mỗi lần! Cài đúng dùng collections.deque (O(1) hai đầu):

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

Quy tắc: queue trong Python → luôn dùng deque, không dùng list.pop(0).

5. Vì sao queue quan trọng?​

Queue mô hình hoá "xử lý theo thứ tự đến" — công bằng, đúng tuần tự. Ứng dụng: BFS (duyệt đồ thị theo lớp — sẽ học ở Trụ 3), hàng đợi tác vụ, hàng đợi in, xử lý yêu cầu máy chủ, bộ đệm. Nếu stack gắn với DFS/đệ quy, thì queue gắn với BFS.

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

  • "Xử lý theo thứ tự đến", "lần lượt", "theo lớp/tầng" → queue (FIFO).
  • Duyệt đồ thị/cây theo lớp → BFS → dùng queue.
  • Trong Python, cần queue → from collections import deque.

7. 🎮 Trò chơi: Hiểu queue​

🎮 Hiểu queue (FIFO)Câu 1/4· Điểm 0· 🔥 0

FIFO: vào trước ra trước. enqueue ở cuối, dequeue ở đầu.

Thuật toán nào dùng queue?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. FIFO nghĩa là?
2. Trong Python nên cài queue bằng?
3. Khác biệt chính giữa stack và queue?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.3.3 — Deque & bộ đệm vòng.