队列：像排队打饭一样处理数据

在编程世界里，经常需要管理一系列按顺序等待处理的任务。比如，你同时打开多个网页，浏览器如何决定哪个网页先加载？或者你在游戏中发送多条指令，服务器如何保证先发的指令先被响应？这些场景都需要一种**先进先出（First In First Out, FIFO）**的规则——队列（Queue）。队列就像学校食堂里的队伍：先来的人先打到饭，后来的人排到最后，按顺序一个个处理。

队列是计算机科学中最基础也最实用的数据结构之一。它帮助程序有序地管理数据，确保公平性和顺序性。无论是操作系统管理打印任务、网络传输中的数据包，还是广度优先搜索算法，都离不开队列的身影。

队列是什么？——从排队讲起

生活中的排队

想象你去奶茶店买奶茶：你到店时前面有两个人，你只好排在队伍末尾。过了一会儿，最前面的人拿到奶茶离开，后面的人依次向前移动。如果你是第三个到的，那么必须等前两个人买完，才能轮到你。这就是先进先出——先排队的人先得到服务，后排队的人必须等待。

类似的例子还有很多：

打印任务：你和小明同时往打印机发送文档，你的先发送，打印机就会先打印你的，再打印小明的。
键盘缓冲区：你快速打字时，电脑可能来不及立即处理每个按键。输入的字符会按顺序存进一个队列，电脑再从队头一个一个取出来处理，这样就不会乱序。
班级里的作业提交：老师让同学们把作业本从第一组往后传，最后交到讲台上。第一个交的人放在最下面，最后一个交的人放在最上面。但是老师批改时，通常从最上面开始（其实是栈），如果老师要求“按交作业顺序批改”，那就需要用队列。

队列的示意图

我们可以用一张简单的图来表示队列：

      出队（Dequeue）←─────────── 队头（Front）
                                   │
                       ┌────┬────┬────┬────┐
               数据：  │ A  │ B  │ C  │    │
                       └────┴────┴────┴────┘
                                        │
                         入队（Enqueue）←── 队尾（Rear）

队头（Front）：队伍的最前面，数据从这里被取出（出队）。
队尾（Rear）：队伍的最后面，新数据从这里加入（入队）。
数据只能从队尾进入，从队头离开，就像排队一样，不能插队，也不能从中间离开。

队列的核心操作

队列主要有以下基本操作（记住它们就像记住“排队”的几个动作）：

入队（Enqueue）：相当于新同学站到队伍末尾。操作就是把一个元素添加到队尾。
出队（Dequeue）：相当于队伍最前面的人离开。操作就是把队头元素移除。
查看队头（Front / Peek）：看一眼队伍第一个是谁，但不让他离开。常见于需要知道下一个要处理什么，但不立即处理。
判断是否为空（IsEmpty）：看看队伍里有没有人。如果为空，就不能进行出队操作。
获取队列长度（Size）：数一数队伍里有多少人。用来监控任务数量。

这些操作的时间复杂度都是 O(1)——也就是说，无论队列有多长，执行一个操作需要的时间是固定的，非常高效。

队列可以用两种常见方式实现：数组和链表。用数组实现时，如果直接往数组尾部添加元素、从头部删除元素，会出现一个问题：头部删除后，前面的空间就浪费了，而且随着不断入队出队，队尾指针可能跑到数组末尾以外，但数组前面还有很多空位——这就是“假溢出”。为了避免浪费，通常使用循环队列（环形数组）来利用所有空间。不过循环队列需要另外处理边界条件。用链表实现就没有这个问题，因为链表节点是动态分配的，不会浪费空间，而且不需要担心数组大小限制（除了内存不足）。

对于初学者，链表实现更加直观易懂。下面我们先用单向链表实现一个简单队列，让你彻底理解内部原理。下一篇文章我们会介绍更高效的循环队列。

C++完整代码实现（链表方式）

我们用单向链表来实现队列，队列中保存的是 int 类型数据。每个节点包含数据和指向下一个节点的指针。

#include <iostream>
using namespace std;

// 链表节点定义
struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点

    Node(int val) : data(val), next(nullptr) {}
};

// 队列类定义（链表实现）
class Queue {
private:
    Node* front;    // 队头指针
    Node* rear;     // 队尾指针
    int count;      // 队列中元素个数

public:
    // 构造函数：初始化为空队列
    Queue() : front(nullptr), rear(nullptr), count(0) {}

    // 析构函数：释放所有节点
    ~Queue() {
        while (!isEmpty()) {
            dequeue();  // 逐个出队并释放
        }
    }

    // 入队操作：在队尾添加元素 x
    void enqueue(int x) {
        Node* newNode = new Node(x);   // 创建新节点
        if (isEmpty()) {
            // 如果队列为空，新节点既是队头也是队尾
            front = rear = newNode;
        } else {
            // 否则将新节点链接到当前队尾后面，并更新队尾
            rear->next = newNode;
            rear = newNode;
        }
        count++;
    }

    // 出队操作：移除队头元素，不返回
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty, cannot dequeue!" << endl;
            return;
        }
        Node* temp = front;          // 保存当前队头节点
        front = front->next;         // 队头指针后移
        delete temp;                 // 释放被删除的节点
        count--;

        // 如果出队后队列为空，需要将 rear 也置空
        if (front == nullptr) {
            rear = nullptr;
        }
    }

    // 获取队头元素（不出队）
    int getFront() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return front->data;
    }

    // 判断队列是否为空
    bool isEmpty() {
        return front == nullptr;  // 或者 count == 0
    }

    // 获取队列元素个数
    int size() {
        return count;
    }
};

// 测试代码
int main() {
    Queue q;

    // 入队 3 个元素
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "队头元素: " << q.getFront() << endl; // 输出 10
    q.dequeue();                                  // 移除 10
    cout << "出队后队头元素: " << q.getFront() << endl; // 输出 20
    cout << "队列大小: " << q.size() << endl;     // 输出 2

    // 再入队一个元素
    q.enqueue(40);
    cout << "队列是否为空? " << (q.isEmpty() ? "是" : "否") << endl; // 否

    // 依次出队所有元素
    while (!q.isEmpty()) {
        cout << q.getFront() << " ";
        q.dequeue();
    }
    cout << endl;  // 输出 20 30 40

    return 0;
}

代码解释

链表节点 Node 包含 data 和 next 指针。
队列类维护三个成员：front（队头指针）、rear（队尾指针）、count（元素个数）。
enqueue 操作：创建新节点，如果队列为空则同时设置 front 和 rear 指向新节点；否则将新节点链接到 rear->next，然后更新 rear。
dequeue 操作：保存当前 front，然后 front 移向下一个节点，再删除原节点。注意如果出队后队列变空，也要将 rear 置空。
所有操作的时间复杂度均为 O(1)，因为队列两端都维护了指针。
注意：链表实现需要手动管理内存（new/delete），C++中最好使用智能指针，但这里为了清晰使用原始指针。

Python 完整代码实现

Python 中可以用列表模拟队列，但列表在头部删除（pop(0)）的时间复杂度是 O(n)，效率低。更好的方法是使用 collections.deque，它是双端队列，在两端插入删除都是 O(1)。当然我们也可以自己用链表实现，下面是链表版的 Queue 类。

class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    """链表实现的队列"""
    def __init__(self):
        self.front = None   # 队头指针
        self.rear = None    # 队尾指针
        self.size = 0       # 队列长度

    def enqueue(self, item):
        """入队：将元素添加到队尾"""
        new_node = Node(item)
        if self.is_empty():
            # 空队列时新节点既是头也是尾
            self.front = self.rear = new_node
        else:
            # 将新节点链接到队尾后面
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1

    def dequeue(self):
        """出队：移除队头元素并返回其值"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        data = self.front.data
        self.front = self.front.next
        # 如果出队后队列为空，rear 也要置空
        if self.front is None:
            self.rear = None
        self.size -= 1
        return data

    def get_front(self):
        """查看队头元素（不出队）"""
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.front.data

    def is_empty(self):
        """判断队列是否为空"""
        return self.front is None

    def length(self):
        """返回队列长度"""
        return self.size

# 测试代码
if __name__ == "__main__":
    q = Queue()

    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)

    print("队头元素:", q.get_front())  # 输出 10
    q.dequeue()                        # 移除 10
    print("出队后队头元素:", q.get_front())  # 输出 20
    print("队列长度:", q.length())     # 输出 2

    q.enqueue(40)
    print("队列是否为空?", q.is_empty())  # 输出 False

    # 依次出队所有元素
    while not q.is_empty():
        print(q.dequeue(), end=" ")    # 输出 20 30 40
    print()

代码解释

我们定义了 Node 类作为链表节点。
Queue 类使用 front 和 rear 指针，以及 size 计数。
入队、出队、查看队头的逻辑和 C++ 版本完全一致，只是用 Python 语法实现。
注意 dequeue 返回被移除的元素值，而 C++ 版本中我们返回 void。两种设计都可以。
在 Python 实际编程中，更推荐使用 collections.deque 来实现队列，因为它已经封装好且效率高。例如：

from collections import deque
q = deque()
q.append(10)    # 入队（队尾）
q.popleft()     # 出队（队头）

但为了学习数据结构原理，手写链表实现能更好地理解内部机制。

新手容易犯的错误

1. 忘记处理空队列

出队前必须检查是否为空，否则会导致程序崩溃（访问空指针或越界）。
在 C++ 中，如果忘记判断空队列就调用 dequeue()，front->next 会访问空指针；在 Python 中会引发 AttributeError。

2. 出队后忘记将 `rear` 置空

当队列中只有一个元素时，出队后该元素被删除，front 变为 null（空），但 rear 还指向那个已经被删除的节点。这个节点虽然被释放/回收，但 rear 仍指向无效内存。下次入队时判断 isEmpty() 可能出错（例如 front == nullptr 但 rear 非空，导致逻辑混乱）。所以在出队后，如果 front 变为空，务必把 rear 也设为空。

3. 用数组实现时产生“假溢出”

如果用普通数组实现队列，每次出队都把头部元素删除，然后移动所有元素（像列表 pop(0) 那样），效率会很低（O(n)）。更常见的是使用固定大小数组，分别记录队头和队尾下标。但如果只后移队头指针而不释放前面的空间，随着入队和出队，队尾下标可能超出数组长度，而数组前面有很多空位——这就是假溢出。解决方案是循环队列（ring buffer）。

4. 混清栈和队列

栈是“后进先出”，队列是“先进先出”。初学者容易把两者的操作记反。可以这样记：栈像叠盘子，最后放上去的盘子最先被拿走；队列像排队，第一个来的先被服务。

5. 在 Python 中使用列表模拟队列时的性能问题

很多新手直接用 list 的 append() 入队，pop(0) 出队。但 pop(0) 会把列表所有元素向前移动一位，导致 O(n) 的时间复杂度。当队列数据量大时，程序会变得非常慢。应该用 collections.deque 或者自己写链表。

队列的应用场景

队列在计算机科学中无处不在，下面是一些经典应用：

广度优先搜索（BFS）：在图或树的遍历中，用队列记录待访问的节点。先访问的节点先扩展其邻居，保证了按层遍历。
操作系统进程调度：多个进程等待 CPU 时，按先来先服务（FCFS）调度，本质就是一个队列。
打印机任务排队：多个打印任务进入队列，打印机从队头开始打印。
消息队列：在微服务架构中，不同服务之间通过消息队列（如 RabbitMQ、Kafka）传递消息，解耦并保证顺序。
键盘缓冲区：击键事件存入队列，应用程序按顺序读取。
课程在线选课：同学们同时选课时，选课请求按时间顺序排入队列，系统依次处理。

总结要点

队列是一种先进先出（FIFO）的数据结构，元素从队尾进入，从队头离开。
生活中的例子：排队打饭、打印机任务队列、键盘缓冲区，都体现了队列的思想。
基本操作：enqueue（入队）、dequeue（出队）、getFront（查看队头）、isEmpty（判空）、size（获取长度）。
实现方式：可以用数组（需要循环队列避免假溢出）或链表。链表实现简单直观，入队和出队都是O(1)。
时间复杂度：所有基本操作都是O(1)（链表实现），用普通数组实现时出队是O(n)，因此通常用循环队列或链表。
应用场景：广度优先搜索（BFS）、任务调度、消息队列、缓冲区管理、广度优先遍历等。
注意点：使用数组实现队列时要注意“假溢出”问题，通常用循环队列解决；使用链表实现时要注意手动管理内存（C++）或使用deque（Python）。

队列是计算机科学中最重要的数据结构之一，和栈一样是学习更多高级算法的基础。建议同学们动手实现队列，并尝试用它解决“约瑟夫问题”、“二叉树的层序遍历”等经典问题。

队列的概念与实现——像排队打饭一样处理数据

队列：像排队打饭一样处理数据

队列是什么？——从排队讲起

生活中的排队

队列的示意图

队列的核心操作

队列的实现方式

C++完整代码实现（链表方式）

代码解释

Python 完整代码实现

代码解释

新手容易犯的错误

1. 忘记处理空队列

2. 出队后忘记将 `rear` 置空

3. 用数组实现时产生“假溢出”

4. 混清栈和队列

5. 在 Python 中使用列表模拟队列时的性能问题

队列的应用场景

总结要点

相关指引

例题精讲