Hàng đợi

7.1 Định nghĩa hàng đợi và thuộc tính của nó

Hàng đợi — là một cấu trúc dữ liệu trừu tượng, là một tập hợp các phần tử được sắp xếp theo nguyên tắc "vào trước – ra trước" (First In, First Out, FIFO). Hàng đợi có thể được tưởng tượng như hàng đợi người trong siêu thị: người đầu tiên trong hàng sẽ được phục vụ đầu tiên.

Thuộc tính của hàng đợi:

• FIFO (First In, First Out): Phần tử được thêm vào đầu tiên sẽ là phần tử được xóa đầu tiên.
• Hạn chế các thao tác: Hàng đợi hỗ trợ một tập hợp giới hạn các thao tác — thêm (enqueue), xóa (dequeue) và xem phần tử ở vị trí đầu (peek).
• Truy cập một chiều: Truy cập các phần tử chỉ có thể từ các phía trước (front) và sau (rear).
• Thực hiện đơn giản: Hàng đợi có thể dễ dàng thực hiện bằng mảng hoặc danh sách liên kết.

Nguyên tắc hoạt động của FIFO:

• Thêm phần tử (enqueue): Phần tử mới được thêm vào cuối hàng đợi.
• Xóa phần tử (dequeue): Phần tử đầu tiên được thêm vào sẽ bị xóa khỏi đầu hàng đợi.
• Xem phần tử đầu tiên (peek): Cho phép xem phần tử ở vị trí đầu hàng đợi mà không xóa nó.

Các phần tử trong hàng đợi được thêm vào từ một đầu (phía sau) và bị xóa khỏi đầu kia (phía trước). Do đó, phần tử đầu tiên được thêm vào sẽ là phần tử đầu tiên bị xóa.

7.2 Các thao tác cơ bản

Các thao tác cơ bản: enqueue, dequeue, peek

Thao tác enqueue: Thêm một phần tử mới vào cuối hàng đợi.

Độ phức tạp thời gian: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Output: deque([10, 20])

Thao tác dequeue: Xóa và trả về phần tử ở đầu hàng đợi.

Độ phức tạp thời gian: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Output: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Output: 10
print(queue)  # Output: deque([20])

Thao tác peek: Trả về phần tử ở vị trí đầu hàng đợi mà không xóa nó.

Độ phức tạp thời gian: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Output: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Output: 10

7.3 Ví dụ sử dụng hàng đợi

Hãy xem một vài ví dụ về việc sử dụng hàng đợi.

1 Quản lý các công việc in ấn

Hàng đợi được sử dụng để quản lý các công việc in ấn, nơi các tài liệu được thêm vào hàng đợi và được in theo thứ tự chúng được nhận.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job}")

# Ví dụ sử dụng:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Output: Printing: Document1.pdf
printer_queue.print_job()  # Output: Printing: Document2.pdf

2 Xử lý yêu cầu trên web server

Hàng đợi được sử dụng để quản lý các yêu cầu của khách hàng gửi đến web server. Các yêu cầu được xử lý theo thứ tự chúng được nhận.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Processing request: {request}")

# Ví dụ sử dụng:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Output: Processing request: GET /index.html
request_queue.process_request()  # Output: Processing request: POST /submit-form

3 Hàng đợi tin nhắn trong hệ thống trao đổi tin nhắn

Hàng đợi được sử dụng để quản lý tin nhắn trong hệ thống trao đổi thông tin (như trong các broker tin nhắn). Tin nhắn được xử lý theo thứ tự chúng được nhận.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Received message: {message}")

# Ví dụ sử dụng:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Output: Received message: Hello
message_queue.receive_message()  # Output: Received message: World