Hướng dẫn cấu trúc dữ liệu hàng đợi Python
Làm chủ các hoạt động hàng đợi FIFO trong Python. Thực thi và chạy ví dụ về hàng đợi tương tác của chúng tôi hiển thị các phương thức enqueue và dequeue.
Tổng quan
Hàng đợi là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc Nhập trước, xuất trước (FIFO). Các phần tử được thêm vào ở phía sau (enqueue) và bị xóa khỏi phía trước (dequeue), giống như quầy thanh toán trong cửa hàng.
Hàng đợi rất quan trọng trong khoa học máy tính để xử lý các tác vụ theo thứ tự chính xác mà chúng đến. Chúng hoạt động như bộ đệm tách rời các quy trình của nhà sản xuất và người tiêu dùng.
Python cung cấp nhiều cách để xây dựng hàng đợi: danh sách cơ bản, mô-đun `collections.deque` cho các hoạt động nhanh chóng an toàn theo luồng và mô-đun `queue.Queue` được thiết kế đặc biệt cho các ứng dụng đa luồng.
Đầu ra mã & thực thi
Hàng đợi FIFO tương tác được xây dựng bằng cách sử dụng bộ sưu tập.deque để thực hiện các hoạt động loại bỏ phía trước hiệu quả.
from collections import deque
class Queue:
def __init__(self):
self.buffer = deque()
def enqueue(self, item):
self.buffer.append(item)
print(f"Enqueued: {item}")
def dequeue(self):
if self.is_empty():
return "Underflow: Queue is empty"
dequeued = self.buffer.popleft()
print(f"Dequeued: {dequeued}")
return dequeued
def is_empty(self):
return len(self.buffer) == 0
def size(self):
return len(self.buffer)
# Test the Queue
q = Queue()
q.enqueue("Customer 1")
q.enqueue("Customer 2")
q.enqueue("Customer 3")
print(f"Queue Size: {q.size()}")
q.dequeue()
q.dequeue()
print(f"Remaining in Queue: {list(q.buffer)}")Enqueued: Customer 1
Enqueued: Customer 2
Enqueued: Customer 3
Queue Size: 3
Dequeued: Customer 1
Dequeued: Customer 2
Remaining in Queue: ['Customer 3']Triển khai từng bước
- Xử lý các yêu cầu không đồng bộ trong khung web máy chủ
- Hàng đợi lập lịch công việc trong hệ điều hành
- Trình môi giới tin nhắn và bộ đệm hàng đợi (như RabbitMQ hoặc Redis)
Câu hỏi thường gặp
Tại sao không sử dụng list.pop(0) để dequeue trong Python?
Việc sử dụng `list.pop(0)` chậm vì nó yêu cầu dịch chuyển tất cả các phần tử tiếp theo trong bộ nhớ sang trái một chỉ mục, dẫn đến hiệu suất O(n). Ngược lại, `deque.popleft()` chạy trong thời gian không đổi O(1).
Hàng đợi ưu tiên là gì?
Hàng đợi ưu tiên là một biến thể trong đó các phần tử được phục vụ dựa trên mức độ ưu tiên liên quan thay vì thứ tự đến. Python thực hiện điều này thông qua mô-đun `heapq`.
Chủ đề liên quan
Triển khai ngăn xếp LIFO trong Python. Chạy ví dụ về mã ngăn xếp tương tác của chúng tôi để làm chủ các giới hạn đẩy, bật, nhìn trộm và dung lượng.
Triển khai danh sách liên kết đơn PythonTìm hiểu cách triển khai danh sách liên kết đơn trong Python. Khám phá phân bổ bộ nhớ động, thao tác nút, chèn, truyền tải và xóa.