队列结构

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。在队列中，元素的插入（入队）发生在队列的尾部，而元素的删除（出队）发生在队列的头部。队列广泛应用于计算机科学中，如任务调度、缓冲区管理、广度优先搜索（BFS）等场景。

基本概念

队列是一种受限的线性表，其操作遵循以下规则：

• 入队（Enqueue）：在队列的尾部添加一个元素。
• 出队（Dequeue）：从队列的头部移除一个元素。
• 队首（Front）：队列的第一个元素，即将被移除的元素。
• 队尾（Rear）：队列的最后一个元素，新元素将在此插入。

队列的示意图如下：

graph LR A[Front] --> B[Element 1] B --> C[Element 2] C --> D[Element 3] D --> E[Rear]

队列的实现

队列可以通过数组或链表实现。以下是两种常见的实现方式：

数组实现

使用数组实现队列时，需要维护两个指针：`front` 和 `rear`，分别指向队首和队尾。为了避免空间浪费，可以使用循环队列（Circular Queue）。

class Queue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, item):
        if self.is_full():
            raise Exception("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue[self.front]

示例输入与输出：

q = Queue(3)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 输出: 10
print(q.peek())     # 输出: 20

链表实现

链表实现队列更加灵活，无需预先分配固定大小的空间。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front is None

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return item

    def peek(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.front.data

示例输入与输出：

q = LinkedListQueue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(q.dequeue())  # 输出: "A"
print(q.peek())     # 输出: "B"

队列的操作复杂度

队列的常见操作时间复杂度如下：

• 入队（Enqueue）：$O(1)$
• 出队（Dequeue）：$O(1)$
• 访问队首元素（Peek）：$O(1)$

队列的变种

队列有多种变体，适用于不同的场景：

• 双端队列（Deque）：允许在队首和队尾进行插入和删除操作。
• 优先队列（Priority Queue）：元素按优先级出队，而非插入顺序。
• 循环队列（Circular Queue）：通过循环利用数组空间提高效率。

实际应用案例

队列在计算机科学中有广泛的应用，以下是一些典型场景：

任务调度

操作系统使用队列管理进程调度。例如，多个进程按照到达顺序排队等待CPU资源。

广度优先搜索（BFS）

在图或树的遍历中，BFS使用队列存储待访问的节点，确保按层级顺序遍历。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')  # 输出: A B C D E F

消息队列

在分布式系统中，消息队列（如RabbitMQ、Kafka）用于异步通信，确保消息按顺序处理。

总结

队列是一种基础且重要的数据结构，其FIFO特性使其在任务调度、缓冲管理和算法实现中具有不可替代的作用。通过数组或链表实现队列，可以灵活应对不同场景的需求。理解队列及其变种，有助于解决实际问题并优化程序性能。