编辑“︁队列结构”︁

{{DISPLAYTITLE:队列结构}}

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

== 基本概念 ==
队列是一种受限的线性表，其操作遵循以下规则：
* '''入队（Enqueue）'''：在队列的尾部添加一个元素。
* '''出队（Dequeue）'''：从队列的头部移除一个元素。
* '''队首（Front）'''：队列的第一个元素，即将被移除的元素。
* '''队尾（Rear）'''：队列的最后一个元素，新元素将在此插入。

队列的示意图如下：
<mermaid>
graph LR
    A[Front] --> B[Element 1]
    B --> C[Element 2]
    C --> D[Element 3]
    D --> E[Rear]
</mermaid>

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

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

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

'''示例输入与输出：'''
<syntaxhighlight lang="python">
q = Queue(3)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 输出: 10
print(q.peek())     # 输出: 20
</syntaxhighlight>

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

<syntaxhighlight lang="python">
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
</syntaxhighlight>

'''示例输入与输出：'''
<syntaxhighlight lang="python">
q = LinkedListQueue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(q.dequeue())  # 输出: "A"
print(q.peek())     # 输出: "B"
</syntaxhighlight>

== 队列的操作复杂度 ==
队列的常见操作时间复杂度如下：
* '''入队（Enqueue）'''：<math>O(1)</math>
* '''出队（Dequeue）'''：<math>O(1)</math>
* '''访问队首元素（Peek）'''：<math>O(1)</math>

== 队列的变种 ==
队列有多种变体，适用于不同的场景：
* '''双端队列（Deque）'''：允许在队首和队尾进行插入和删除操作。
* '''优先队列（Priority Queue）'''：元素按优先级出队，而非插入顺序。
* '''循环队列（Circular Queue）'''：通过循环利用数组空间提高效率。

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

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

=== 广度优先搜索（BFS） ===
在图或树的遍历中，BFS使用队列存储待访问的节点，确保按层级顺序遍历。

<syntaxhighlight lang="python">
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
</syntaxhighlight>

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]