Bỏ qua đến nội dung chính
Mục lục

Queue là gì? Hàng đợi (queue) trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 4/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 6 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Queue là gì? Queue, hay hàng đợi, là một dãy thêm phần tử vào ở cuối và lấy ra ở đầu, nên phần tử vào trước được phục vụ trước. Bạn dùng nó cho hàng chờ ở quầy: người lấy số trước được gọi trước, người mới tới đứng sau cùng.

Cần biết trước: deque, ngăn xếp (stack) và độ phức tạp Big O.

Vào trước ra trước

Quy tắc của hàng đợi là vào trước ra trước, viết tắt FIFO (first in, first out). Ngăn xếp lấy ra ở cùng đầu với lúc thêm vào, hàng đợi thì lấy ở đầu bên kia. Dùng list, bạn thêm bằng append() và lấy người ở đầu bằng pop(0):

python
hang_cho = []
hang_cho.append("A01")
hang_cho.append("A02")
hang_cho.append("A03")
print("Mời", hang_cho.pop(0))
hang_cho.append("A04")
print("Mời", hang_cho.pop(0))
print("Còn chờ:", hang_cho)

KẾT QUẢ

Mời A01
Mời A02
Còn chờ: ['A03', 'A04']

A04 tới sau khi A01 đã được gọi nhưng vẫn đứng sau A03, đúng như một hàng người thật. Đổi lần pop(0) thứ hai thành pop() rồi chạy lại: dòng thứ hai in Mời A04, người vừa tới chen lên trước, tức là list lại thành ngăn xếp.

Vì sao pop(0) của list chậm

Kết quả đúng, nhưng mỗi lần pop(0) list phải dời mọi phần tử còn lại lên một ô để lấp chỗ trống ở chỉ số 0. Đoạn dưới đếm số lần dời khi phục vụ hết một hàng 1000 người:

python
hang_cho = []
for i in range(1000):
    hang_cho.append(f"A{i:03d}")
so_lan_doi = 0
for _ in range(1000):
    so_lan_doi += len(hang_cho) - 1
    hang_cho.pop(0)
print(so_lan_doi)

KẾT QUẢ

499500

Mỗi pop(0) là O(n), nên phục vụ hết n người tốn O(n²). Tài liệu module collections (docs.python.org/3/library/collections.html, mục deque, xem ngày 15/11/2026) ghi rằng deque thêm và lấy ở hai đầu với khoảng O(1) bước, còn list tốn O(n) cho pop(0) và insert(0, v) vì phải dời dữ liệu trong bộ nhớ. Một hàng chờ vài chục người thì không thấy khác. Một hàng đợi xử lý hàng trăm nghìn yêu cầu thì khác rất xa.

Dùng deque làm hàng đợi

deque là kiểu Python dành cho việc này: append() thêm vào cuối, popleft() lấy ở đầu, không dời phần tử nào. Mô phỏng một quầy mỗi phút có người tới và quầy gọi một người:

python
from collections import deque

hang_cho = deque()
toi_theo_phut = [["A01", "A02"], ["A03"], [], ["A04", "A05"]]
for phut, nguoi_toi in enumerate(toi_theo_phut, start=1):
    for ma in nguoi_toi:
        hang_cho.append(ma)
    if hang_cho:
        print(f"Phút {phut}: mời {hang_cho.popleft()}")
print("Còn chờ:", list(hang_cho))

KẾT QUẢ

Phút 1: mời A01
Phút 2: mời A02
Phút 3: mời A03
Phút 4: mời A04
Còn chờ: ['A05']

Phút thứ ba không ai tới nhưng quầy vẫn gọi A03, người đã chờ từ phút trước. if hang_cho: chặn trường hợp quầy rảnh mà hàng đã hết, vì popleft() trên deque rỗng báo lỗi. Thứ tự gọi ra đúng bằng thứ tự lấy số, dù người tới theo từng đợt.

Phục vụ hết hàng chờ

Cuối ca, quầy gọi lần lượt mọi người còn trong hàng. Số lượt cần gọi đúng bằng độ dài hàng lúc bắt đầu, nên bạn lặp len(hang_cho) lần và mỗi lượt popleft() một người:

python
from collections import deque

hang_cho = deque(["A06", "A07", "A08"])
for _ in range(len(hang_cho)):
    print("Mời", hang_cho.popleft())
print(len(hang_cho))

KẾT QUẢ

Mời A06
Mời A07
Mời A08
0

range(len(hang_cho)) được tính một lần trước lượt đầu, nên việc hàng ngắn dần không làm đổi số lượt.

Kiểm tra nhanh

  1. Sau ds = ["A01", "A02", "A03"] và ds.append("A04"), lệnh print(ds.pop(0), ds.pop(0)) in ra gì?

    • A01 A02
    • A04 A03
    • A01 A04
  2. Trong ví dụ đếm số lần dời, nếu hàng chỉ có 4 người thì dòng in ra là số nào?

    • 4
    • 6
    • 16
  3. Sau from collections import deque và h = deque(["A01", "A02", "A03"]), h.pop() trả về gì?

    • 'A01'
    • 'A02'
    • 'A03'
  4. Những cách nào phục vụ hết một deque tên hang mà không báo lỗi?

    • for _ in range(len(hang)): hang.popleft()
    • for ma in hang: hang.popleft()
    • for _ in range(len(hang)): print(hang.popleft())
    • for _ in range(len(hang) + 1): hang.popleft()
Đúng hết lần đầu +15 XP

Bài tập

Viết quầy gọi số bằng hàng đợi

Quầy cấp số cho khách và gọi theo thứ tự lấy số. Hàng chờ là self.hang, một deque đã tạo sẵn. Viết thân ba phương thức của QuayGoiSo:

  • lay_so(ma): thêm ma vào cuối hàng.

  • goi(): lấy mã ở đầu hàng ra bằng popleft() và trả về mã đó, hàng rỗng thì trả về None.

  • so_nguoi_truoc(ma): số người đang đứng trước ma trong hàng, ma không có trong hàng thì trả về -1.

Trả về: goi() trả về mã khách, một str, hoặc None. so_nguoi_truoc() trả về một int.

python
from collections import deque

class QuayGoiSo:
    def __init__(self):
        self.hang = deque()

    def lay_so(self, ma):
        pass  # Viết thân các phương thức thay cho các dòng pass

    def goi(self):
        pass

    def so_nguoi_truoc(self, ma):
        pass

Tóm tắt

  • Hàng đợi thêm vào ở cuối, lấy ra ở đầu, theo quy tắc vào trước ra trước (FIFO).

  • List làm hàng đợi với append() và pop(0) cho kết quả đúng nhưng mỗi pop(0) dời mọi phần tử còn lại: O(n).

  • deque thêm bằng append() và lấy bằng popleft() với O(1) bước.

  • Lấy bằng pop() biến hàng đợi thành ngăn xếp mà không báo lỗi.

  • Phục vụ hết hàng bằng for _ in range(len(hang)), không lấy ra khỏi deque mà for đang đi qua.

Câu hỏi thường gặp

Hàng đợi là gì, khác ngăn xếp ở đâu?

Hàng đợi lấy ra phần tử vào đầu tiên, ngăn xếp lấy ra phần tử vào sau cùng. Hàng chờ ở quầy là hàng đợi, nút hoàn tác là ngăn xếp. Trong Python, cả hai đều dựng được trên deque, khác nhau ở chỗ lấy bằng popleft() hay pop().

Hàng đợi (queue) trong Python nên dùng deque hay module queue?

Chương trình chạy một luồng dùng collections.deque. Module queue có queue.Queue cho nhiều luồng cùng thêm và lấy, kèm khả năng chờ tới khi có phần tử, bài Queue, Event và Condition dạy nó. Nó chậm hơn deque vì phải khóa ở mỗi thao tác.

Muốn lấy ra phần tử ưu tiên cao nhất thay cho phần tử đến trước thì làm sao?

Đó là hàng đợi ưu tiên: mỗi lần lấy ra phần tử có mức ưu tiên cao nhất, bất kể nó tới lúc nào. Python làm việc này bằng module heapq, bài heapq dạy cách dùng.

Hàng đợi dùng ở đâu ngoài hàng chờ ở quầy?

Hàng đợi có mặt ở những chỗ việc tới nhanh hơn lúc xử lý được: lệnh in chờ máy in, yêu cầu chờ máy chủ, tin nhắn chờ gửi. Trong giải thuật, duyệt đồ thị theo chiều rộng dùng hàng đợi để xét các trạm gần trước, bài BFS và DFS dựng nó trên bản đồ tuyến xe.

Chủ đề

queue là gì

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập