Queue là gì? Hàng đợi (queue) trong Python
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
Trong bài này · 12
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):
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:
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Ả
499500Mỗ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:
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:
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
0range(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
Sau
ds = ["A01", "A02", "A03"]vàds.append("A04"), lệnhprint(ds.pop(0), ds.pop(0))in ra gì?A01 A02A04 A03A01 A04
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
Sau
from collections import dequevàh = deque(["A01", "A02", "A03"]),h.pop()trả về gì?'A01''A02''A03'
Những cách nào phục vụ hết một
dequetênhangmà 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()
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êmmavào cuối hàng.goi(): lấy mã ở đầu hàng ra bằngpopleft()và trả về mã đó, hàng rỗng thì trả vềNone.so_nguoi_truoc(ma): số người đang đứng trướcmatrong hàng,makhô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.
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):
passTó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ỗipop(0)dời mọi phần tử còn lại: O(n).dequethêm bằngappend()và lấy bằngpopleft()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ỏidequemà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ủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.