Queue (hàng đợi) là cấu trúc dữ liệu tuyến tính hoạt động theo cơ chế First In First Out (FIFO - Vào trước ra trước).
Phần tử nào vào trước trong queue sẽ được xử lý trước.
Ví dụ minh họa
Cấu trúc dữ liệu queue có thể hiểu qua ví dụ hàng đợi ở trạm xe buýt.
Người đến đầu tiên ở trạm xe buýt là người đầu tiên trong hàng đợi và những người khác đứng sau theo thứ tự đến. Khi xe buýt đến, người đến đầu tiên sẽ lên xe trước và những người còn lại lên theo thứ tự họ đến. Do đó, cơ chế FIRST IN FIRST OUT được tuân theo.
Triển khai Queue trong Python
Queue trong Python có thể triển khai theo nhiều cách dùng các cấu trúc dữ liệu tuyến tính khác hoặc module built-in trong thư viện Python.
Phương pháp 1 – Triển khai dùng list
Queue trong Python có thể triển khai dùng list. Nó không hiệu quả lắm vì chèn hoặc xóa phần tử ở đầu list tốn thời gian O(n), chậm hơn so với triển khai bằng cách khác.
Các phép toán liên quan
append() – Hàm này thêm phần tử vào cuối queue.
pop(0) – Hàm này xóa và trả về phần tử đầu tiên trong queue.
Ví dụ
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
print("Queue ban đầu:", queue)
print("Phần tử pop từ queue:")
print(queue.pop(0))
print(queue.pop(0))
print("Queue sau khi pop một vài phần tử:", queue)Kết quả
Queue ban đầu: [1, 2, 3] Phần tử pop từ queue: 1 2 Queue sau khi pop một vài phần tử: [3]
Không thể xóa thêm phần tử khi queue rỗng. Làm vậy sẽ gây exception.
queue.pop(0) IndexError: pop from empty list
Phương pháp 2 – Triển khai dùng queue.Queue
Đây là cách triển khai queue dùng module built-in của Python. Cần import Queue từ queue. Có thể khởi tạo queue với kích thước cụ thể. Kích thước 0 nghĩa là queue vô hạn.
Các phép toán liên quan
maxsize – số lượng phần tử tối đa cho phép trong queue
get() – xóa và trả về phần tử đầu từ queue. Nếu queue rỗng, chờ cho đến khi queue có ít nhất một phần tử.
get_nowait() – xóa và trả về phần tử đầu từ queue. Nếu queue rỗng, ném exception.
put(item) – thêm phần tử vào cuối queue. Nếu queue đầy, chờ cho đến khi có ô trống.
put_nowait(item) – thêm phần tử vào cuối queue. Nếu queue đầy, ném exception.
full() – trả về true nếu queue đầy, ngược lại false.
empty() – trả về True nếu queue rỗng, ngược lại false.
qsize() – trả về số phần tử hiện có trong queue.
Ví dụ
from queue import Queue
q = Queue(maxsize=3)
q.put(1)
q.put(2)
q.put(3)
print("Queue đầy?", q.full())
print("Phần tử pop từ queue:")
print(q.get())
print(q.get())
print("Số phần tử trong queue:", q.qsize())
print("Queue rỗng?", q.empty())Kết quả
Queue đầy? True Phần tử pop từ queue: 1 2 Số phần tử trong queue: 1 Queue rỗng? False
Phương pháp 3 – Triển khai dùng collections.deque
Đây là cách khác triển khai queue trong Python. Cần import deque từ module collections.
Các phép toán liên quan
append() – Hàm này thêm phần tử vào cuối queue.
popleft() – Hàm này xóa và trả về phần tử đầu trong queue với độ phức tạp O(1).
Ví dụ
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print("Queue ban đầu:", queue)
print("Phần tử pop từ queue:")
print(queue.popleft())
print(queue.popleft())
print("Queue sau khi pop một vài phần tử:", queue)Kết quả
Queue ban đầu: deque([1, 2, 3]) Phần tử pop từ queue: 1 2 Queue sau khi pop một vài phần tử: deque([3])
Dùng popleft() trên deque rỗng sẽ ném exception.