deque trong Python: hàng đợi hai đầu (collections)
Bài 3/25 · Chương 19
Thư viện chuẩn thường dùng
- 6 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 10
deque trong Python (đọc là "đéc") là một dãy của module collections cho phép thêm và lấy phần tử ở cả hai đầu với cùng một tốc độ, nên còn gọi là hàng đợi hai đầu. Bạn dùng nó cho hàng chờ gọi món: khách mới xếp vào cuối, đơn ưu tiên chen lên đầu, quầy pha chế lấy đơn ở đầu ra làm.
Cần biết trước: append() và pop() của list và lệnh import.
Thêm và lấy ở hai đầu
List có append() và pop() ở cuối. deque có thêm hai phương thức cho đầu bên kia: appendleft() thêm vào đầu, popleft() lấy phần tử ở đầu ra.
from collections import deque
hang_cho = deque(["DH1024", "DH1025"])
hang_cho.append("DH1026")
hang_cho.appendleft("DH1030")
print(hang_cho)
print(hang_cho.popleft(), hang_cho.pop())
print(hang_cho, len(hang_cho), hang_cho[0])KẾT QUẢ
deque(['DH1030', 'DH1024', 'DH1025', 'DH1026'])
DH1030 DH1026
deque(['DH1024', 'DH1025']) 2 DH1024Lấy theo chỉ số ở hai đầu (hang_cho[0], hang_cho[-1]), len(), in và vòng for dùng như trên list. Đổi hang_cho.appendleft("DH1030") thành hang_cho.append("DH1030") rồi chạy lại: dòng thứ hai in DH1024 DH1030.
Vì sao không dùng list? ds.insert(0, x) và ds.pop(0) cũng làm được việc ở đầu, nhưng list phải dời từng phần tử còn lại sang một ô, nên list càng dài thì mỗi lần càng chậm. deque giữ phần tử thành nhiều khối nối hai chiều, giống một đoàn tàu móc toa được ở cả hai đầu, nên thêm bớt ở đầu nào cũng không phải dời gì. Kiểu hàng chờ vào trước ra trước này gọi là hàng đợi (queue), bài hàng đợi dựng nó và so với các cách khác.
Giữ N phần tử gần nhất bằng maxlen
Màn hình quầy chỉ hiện ba đơn vừa pha xong. deque(maxlen=3) giữ tối đa ba phần tử: khi đã đủ mà append() thêm một phần tử, phần tử ở đầu bên kia tự bị bỏ.
from collections import deque
vua_xong = deque(maxlen=3)
for ma in ["DH1024", "DH1025", "DH1026", "DH1027"]:
vua_xong.append(ma)
print(list(vua_xong))KẾT QUẢ
['DH1024']
['DH1024', 'DH1025']
['DH1024', 'DH1025', 'DH1026']
['DH1025', 'DH1026', 'DH1027']Ở lượt cuối, DH1024 rơi khỏi đầu trái để nhường chỗ cho DH1027. Ngược lại, appendleft() trên một deque đã đầy bỏ phần tử ở đầu phải. maxlen=0 thì không giữ gì. Đổi maxlen=3 thành maxlen=2 rồi chạy lại: dòng cuối in ['DH1026', 'DH1027'].
Xoay vòng bằng rotate()
Bốn bạn Lan, Minh, Ngọc, Quân nhận đơn theo lượt. rotate(-1) chuyển người ở đầu xuống cuối, rotate(1) chuyển người ở cuối lên đầu, và rotate(n) xoay n bước một lần.
from collections import deque
ca_truc = deque(["Lan", "Minh", "Ngọc", "Quân"])
for ma in ["DH1024", "DH1025", "DH1026", "DH1027", "DH1028"]:
print(ma, "giao cho", ca_truc[0])
ca_truc.rotate(-1)
print(list(ca_truc))
ca_truc.rotate(2)
print(list(ca_truc))KẾT QUẢ
DH1024 giao cho Lan
DH1025 giao cho Minh
DH1026 giao cho Ngọc
DH1027 giao cho Quân
DH1028 giao cho Lan
['Minh', 'Ngọc', 'Quân', 'Lan']
['Quân', 'Lan', 'Minh', 'Ngọc']Đơn thứ năm quay về Lan vì sau bốn lần rotate(-1) cả hàng trở lại như cũ. rotate() sửa tại chỗ và trả về None, như các phương thức sửa list.
Muốn thêm nhiều phần tử một lúc, extend() thêm vào cuối theo đúng thứ tự, còn extendleft() thêm từng phần tử vào đầu, lần lượt từng cái.
Kiểm tra nhanh
Sau
from collections import deque,h = deque([1, 2, 3], maxlen=3)vàh.append(4), lệnhprint(list(h))in ra gì?[1, 2, 3, 4][2, 3, 4][1, 2, 3]
Sau
from collections import deque,h = deque("ABCD")vàh.rotate(1),"".join(h)cho kết quả gì?'DABC''BCDA''ABCD'
Với
from collections import dequevàh = deque(["Lan", "Minh"]), những dòng nào báo lỗi?h[0:1]h[-1]h.popleft()deque().popleft()
Sau
from collections import deque,h = deque([3])vàh.extendleft([1, 2]),list(h)cho kết quả gì?[1, 2, 3][3, 1, 2][2, 1, 3]
Bài tập
Mô phỏng hàng chờ và màn hình gọi món
Màn hình quầy pha chế hiện so_dong đơn vừa xong gần nhất. Viết hàm goi_mon(cac_su_kien, so_dong) đi qua list cac_su_kien theo thứ tự:
Một mã đơn như
"DH1024": thêm vào cuối hàng chờ."VIP:"ghép với mã đơn, như"VIP:DH1030": thêm mã"DH1030"vào đầu hàng chờ."XONG": lấy đơn ở đầu hàng chờ ra, đưa lên màn hình. Hàng chờ rỗng thì bỏ qua.
Dùng deque với appendleft(), popleft() cho hàng chờ và một deque có maxlen cho màn hình. Hàm không sửa cac_su_kien.
Ví dụ: goi_mon(["DH1024", "VIP:DH1030", "XONG"], 2) trả về (["DH1024"], ["DH1030"]).
Trả về: hàng chờ và màn hình (đơn xong sau cùng ở cuối), một tuple gồm hai list.
from collections import deque
def goi_mon(cac_su_kien, so_dong):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
dequethêm, lấy ở cả hai đầu:append(),pop()bên phải,appendleft(),popleft()bên trái.List phải dời phần tử khi
insert(0, x)haypop(0),dequethì không.deque(maxlen=n)giữ tối đanphần tử, thêm vào một đầu thì đầu kia tự bị bỏ.rotate(1)đưa phần tử cuối lên đầu,rotate(-1)đưa phần tử đầu xuống cuối.dequekhông cắt lát được,popleft()trêndequerỗng báoIndexError,extendleft()đảo thứ tự nhóm chèn.
Câu hỏi thường gặp
Nên dùng deque của collections hay dùng list?
deque thêm bớt ở đầu nhanh như ở cuối, có maxlen và rotate(). List lấy phần tử ở giữa theo chỉ số nhanh hơn, cắt lát được và có sort(). Dữ liệu chủ yếu đọc theo chỉ số thì dùng list, còn vào ra ở hai đầu thì dùng deque.
Hàng đợi hai đầu trong Python có an toàn khi nhiều luồng cùng dùng không?
append(), appendleft(), pop() và popleft() của deque an toàn khi nhiều luồng cùng gọi, theo tài liệu Python. Khi một luồng cần chờ cho tới lúc có phần tử, bạn dùng queue.Queue, bài Queue, Event và Condition dạy kiểu đó.
Làm sao lấy phần tử nhỏ nhất ra trước thay cho phần tử đến trước?
deque giữ đúng thứ tự thêm vào, không sắp xếp gì. Muốn mỗi lần lấy ra phần tử nhỏ nhất, như đơn có mức ưu tiên cao nhất, bạn dùng heap của module heapq, bài heapq dạy cách đó.
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.