佇列

7.1 佇列的定義及其特性

佇列 是一種抽象的資料結構，表示為一個有序的元素集合，按照 "先進先出"（First In, First Out, FIFO）的原則組織。佇列可以想像成商店裡的人龍：排在最前面的人會最先被服務。

佇列的特性：

• FIFO (First In, First Out): 最早加入的元素將是最早被移除的元素。
• 有限操作： 佇列僅支持有限的操作集——添加（enqueue）、移除（dequeue）及查看（peek）前端的元素。
• 單向存取： 只能從前端（front）和後端（rear）訪問元素。
• 簡單實作： 佇列可以簡單地使用陣列或鏈結串列來實作。

FIFO 運作原理：

• 添加元素 (enqueue): 新元素加入佇列的末尾。
• 移除元素 (dequeue): 最早加入的元素從佇列的開頭被移除。
• 查看前端元素 (peek): 查看佇列前端的元素而不移除它。

佇列中的元素從一端（後面）加入，然後從另一端（前面）移除。因此，最早加入的元素會最先被移除。

7.2 基本操作

基本操作： enqueue, dequeue, peek

操作 enqueue: 將新元素加入佇列的末尾。

時間複雜度： O(1).

from collections import deque

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

操作 dequeue: 移除並返回佇列開頭的元素。

時間複雜度： O(1).

from collections import deque

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

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

操作 peek: 返回佇列前端的元素而不移除它。

時間複雜度： O(1).

from collections import deque

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

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

7.3 佇列的使用例子

接下來我們看看一些佇列的使用例子。

1 打印機任務管理

佇列用於管理打印機的任務，文件加入佇列並按照它們的到達順序進行打印。

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}")

# 使用例子:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # 輸出: Printing: Document1.pdf
printer_queue.print_job()  # 輸出: Printing: Document2.pdf

2 Web 伺服器上的請求處理

佇列用於管理發送到 Web 伺服器的客戶請求。請求按照它們的到達順序進行處理。

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}")

# 使用例子:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # 輸出: Processing request: GET /index.html
request_queue.process_request()  # 輸出: Processing request: POST /submit-form

3 訊息交換系統中的訊息佇列

佇列用於管理訊息交換系統中的訊息（例如，在訊息代理中）。訊息按照它們的到達順序進行處理。

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}")

# 使用例子:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # 輸出: Received message: Hello
message_queue.receive_message()  # 輸出: Received message: World