普通队列（Queue）[编辑 | 编辑源代码]

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

基本特性[编辑 | 编辑源代码]

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

实现方式[编辑 | 编辑源代码]

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

1. 数组实现[编辑 | 编辑源代码]

需维护 front 和 rear 指针，可能遇到"假溢出"问题（即数组未满但无法插入新元素）。

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

2. 链表实现[编辑 | 编辑源代码]

更灵活的实现方式，无需担心容量问题。

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'

可视化表示[编辑 | 编辑源代码]

实际应用案例[编辑 | 编辑源代码]

1. 打印机任务管理[编辑 | 编辑源代码]

多用户共享打印机时，打印任务按提交顺序排队执行。

2. 广度优先搜索（BFS）[编辑 | 编辑源代码]

在图遍历中，队列用于存储待访问的节点：

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