编辑“︁普通队列（Queue）”︁（章节）

= 普通队列（Queue） =
'''队列'''（Queue）是一种遵循'''先进先出'''（First-In-First-Out, FIFO）原则的线性数据结构。它模拟了现实生活中的排队现象，例如顾客在超市收银台前的等待队列。

== 基本特性 ==
* '''操作限制'''：元素只能从'''队尾（rear）'''插入（称为'''入队 enqueue'''），从'''队头（front）'''删除（称为'''出队 dequeue'''）。
* '''时间复杂度'''：
** 入队和出队操作在理想情况下均为 <math>O(1)</math>。
* '''核心用途'''：管理需要按顺序处理的元素。

== 实现方式 ==
队列可通过以下两种主要方式实现：

=== 1. 数组实现 ===
需维护 <code>front</code> 和 <code>rear</code> 指针，可能遇到"假溢出"问题（即数组未满但无法插入新元素）。

<syntaxhighlight lang="python">
class ArrayQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1  # 初始为空队列

    def enqueue(self, item):
        if self.rear == self.capacity - 1:
            print("队列已满")
            return
        if self.front == -1:  # 首次入队
            self.front = 0
        self.rear += 1
        self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            print("队列为空")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:  # 最后一个元素
            self.front = self.rear = -1
        else:
            self.front += 1
        return item

# 示例用法
q = ArrayQueue(3)
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())  # 输出: 10
print(q.dequeue())  # 输出: 20
</syntaxhighlight>

=== 2. 链表实现 ===
更灵活的实现方式，无需担心容量问题。

<syntaxhighlight lang="python">
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = self.rear = 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.front is None:
            return None
        item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return item

# 示例用法
q = LinkedListQueue()
q.enqueue('A')
q.enqueue('B')
print(q.dequeue())  # 输出: 'A'
print(q.dequeue())  # 输出: 'B'
</syntaxhighlight>

== 可视化表示 ==
<mermaid>
graph LR
    subgraph 队列操作
        direction LR
        A[入队 enqueue] --> B[元素1]
        B --> C[元素2]
        C --> D[元素3]
        D --> E[出队 dequeue]
    end
</mermaid>

== 实际应用案例 ==
=== 1. 打印机任务管理 ===
多用户共享打印机时，打印任务按提交顺序排队执行。

=== 2. 广度优先搜索（BFS） ===
在图遍历中，队列用于存储待访问的节点：
<syntaxhighlight lang="python">
def bfs(graph, start):
    visited = set()
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend([x for x in graph[vertex] if x not in visited])
    return visited
</syntaxhighlight>

=== 3. 消息队列系统 ===
如RabbitMQ等消息中间件的基础数据结构。

== 复杂度分析 ==
{| class="wikitable"
|+ 时间复杂度对比
! 操作 !! 数组实现 !! 链表实现
|-
| 入队(enqueue) || <math>O(1)</math>* || <math>O(1)</math>
|-
| 出队(dequeue) || <math>O(1)</math> || <math>O(1)</math>
|-
| 访问队首(peek) || <math>O(1)</math> || <math>O(1)</math>
|}
<small>* 注：数组实现可能需要动态扩容，最坏情况下为<math>O(n)</math></small>

== 常见问题 ==
{{Warning|1=循环队列可以解决数组实现的"假溢出"问题，这是普通队列的重要优化方向}}

=== Q: 如何处理数组实现的固定大小问题？ ===
'''解决方案'''：
1. 动态扩容（代价是偶尔的<math>O(n)</math>时间）
2. 使用循环队列实现

=== Q: 线程安全场景如何处理？ ===
在多线程环境中需要使用：
* 锁机制
* 线程安全队列实现（如Python的<code>queue.Queue</code>）

== 扩展练习 ==
1. 实现一个能动态扩容的队列
2. 用队列实现栈结构
3. 设计支持查询最大/最小元素的队列变体

{{DataStructureNavigation}}

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