队列

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 处理网络服务器上的请求

队列用于管理发送到网络服务器的客户端请求。请求按照到达的顺序被处理。

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