队列（queue）——先进先出的“排队”魔法

你有没有在学校食堂排过队？排在队伍最后面的人，要等前面所有人都打完饭才能轮到自己。这种“先来先服务”的规则，就是队列（queue）的核心思想：先进先出（FIFO，First In First Out）。

队列在编程中就像一根“管道”：你从一端（队尾）放入数据，数据从另一端（队首）流出。你不能跳过中间的人，也不能插队。这种结构特别适合处理需要按顺序完成的任务，比如打印任务、聊天消息排序、游戏中的操作队列，甚至用来实现“广度优先搜索（BFS）”算法——你可以把BFS想象成沿着迷宫一层一层地找出口，每走完一层就把下一层的所有路口记下来，用队列来安排先到先走。

C++ 的 STL 提供了现成的 queue 容器适配器，几行代码就能实现一个队列。Python 中推荐用 collections.deque 来高效模拟队列。下面我们就一步步揭开队列的魔法。

队列的“公平规则”：先进先出（FIFO）

队列只允许在一端（队尾）添加元素，在另一端（队首）移除元素。想象一下你正在玩一个“传球游戏”：你从后面拿到一个球，只能从前面把球传给下一个人——球不能从中间漏掉，也不能从后面接回来。

生活里随处可见的队列

食堂打饭：最先到的同学最先打到饭。
打印机任务：你先提交的文档，打印机先打印出来。
银行叫号机：先取号的人先被叫到窗口。
手机聊天群：你发的消息会按发送时间先后显示在群里。
游戏中的操作队列：你连续按了好几个技能键，游戏会按你按的顺序依次释放技能，不能乱序。

队列的接口非常简洁，只有队首和队尾可以访问，不能像数组一样随便读取中间的元素。这就像队伍里你只能看到最前面和最后面的人，看不到中间的人在干嘛。

STL 中 queue 的用法（C++）

包含头文件与定义

使用 queue 前需要包含头文件 <queue>，然后定义一个队列对象，指定元素的类型。

#include <queue>        // 使用队列必须包含此头文件
using namespace std;

queue<int> q;            // 定义一个int类型的空队列，名字叫q
queue<string> name_queue; // 定义一个string类型的空队列，存放名字

常用成员函数

函数	作用	时间复杂度
`push(x)`	将元素 x 放入队尾（入队）	O(1)
`pop()`	移除队首元素（出队），不返回被删除的元素	O(1)
`front()`	返回队首元素的引用（不删除）	O(1)
`back()`	返回队尾元素的引用（不删除）	O(1)
`empty()`	判断队列是否为空，空返回 true，否则 false	O(1)
`size()`	返回队列中元素的个数	O(1)

特别提醒：pop() 只移除队首元素，不会把那个元素的值返回给你。如果你想先拿到队首再把它删掉，需要先调用 front() 把值存起来，再调用 pop()。

int first = q.front();  // 拿到队首元素
q.pop();                // 再把它从队列里移除

完整示例代码（C++）

下面是一个完整的 C++ 程序，模拟了“早操排队”的过程：同学们按名字顺序入队，然后老师按顺序喊人出列做操。

#include <iostream>
#include <queue>        // 使用queue的头文件
#include <string>       // 使用string

using namespace std;

int main() {
    // 定义一个string类型的队列，用来存放同学的名字
    queue<string> student_queue;

    // 检查队列是否为空
    if (student_queue.empty()) {
        cout << "队伍里还没有人。" << endl;
    }

    // 同学们陆续入队（push）
    student_queue.push("小明");   // 小明排在队尾
    student_queue.push("小红");
    student_queue.push("小刚");
    student_queue.push("小丽");
    student_queue.push("大壮");   // 大壮是最后来的

    cout << "现在队伍里有 " << student_queue.size() << " 位同学。" << endl;
    cout << "队首（最先来的）是：" << student_queue.front() << endl;  // 小明
    cout << "队尾（最后到的）是：" << student_queue.back() << endl;   // 大壮

    // 开始做操：老师每次喊队首的同学出来，然后该同学离开队伍
    cout << "做操顺序：";
    while (!student_queue.empty()) {
        string current = student_queue.front(); // 拿到当前队首的同学名字
        cout << current << " ";                  // 喊名字
        student_queue.pop();                     // 该同学离开队伍
    }
    cout << endl;

    cout << "所有同学都做完操了，队伍空了？" 
         << (student_queue.empty() ? "是的" : "不是") << endl;

    return 0;
}

运行结果：

队伍里还没有人。
现在队伍里有 5 位同学。
队首（最先来的）是：小明
队尾（最后到的）是：大壮
做操顺序：小明 小红 小刚 小丽 大壮 
所有同学都做完操了，队伍空了？是的

底层实现说明

queue 默认基于 deque（双端队列）实现，也可以在定义时指定底层容器为 list。但不能用 vector，因为 vector 在头部删除元素时需要移动所有剩余元素，效率非常低（O(n)）。而 deque 和 list 在两端添加删除都是 O(1) 的。

// 指定用list作为底层容器
queue<int, list<int>> q_with_list;

Python 中模拟队列（使用 deque）

Python 最推荐的队列实现是 collections.deque（双端队列），它支持左右两端的高效添加和删除。注意：不要用普通的 list 来模拟队列，因为 list.pop(0) 会移动所有剩余元素，时间复杂度 O(n)，数据量大时会非常慢。

基本操作对应表

C++ queue 函数	Python deque 方法	说明
push(x)	q.append(x)	从右边（队尾）添加元素
pop()	q.popleft()	从左边（队首）移除元素并返回
front()	q[0]	访问队首元素（不删除）
back()	q[-1]	访问队尾元素（不删除）
empty()	not q 或 len(q)==0	判断是否为空
size()	len(q)	获取元素个数

完整示例代码（Python）

和 C++ 例子一样，模拟早操排队：

from collections import deque  # 从collections模块导入deque

def main():
    # 创建一个空队列，存放同学名字
    student_queue = deque()

    # 检查队列是否为空
    if not student_queue:
        print("队伍里还没有人。")

    # 同学们陆续入队（从右边添加）
    student_queue.append("小明")
    student_queue.append("小红")
    student_queue.append("小刚")
    student_queue.append("小丽")
    student_queue.append("大壮")

    print("现在队伍里有", len(student_queue), "位同学。")
    print("队首（最先来的）是：", student_queue[0])   # 小明
    print("队尾（最后到的）是：", student_queue[-1])  # 大壮

    # 做操：依次弹出队首（从左端弹出）
    print("做操顺序：", end="")
    while student_queue:                     # 只要队列非空
        current = student_queue.popleft()    # 弹出队首同学的名字
        print(current, end=" ")              # 打印名字
    print()

    print("所有同学都做完操了，队伍空了？", "是的" if not student_queue else "不是")

if __name__ == "__main__":
    main()

运行结果与 C++ 完全相同。

为什么不用 list？

如果你尝试用 list 模拟队列：

q = []
q.append(10)   # 入队：没问题
x = q.pop(0)   # 出队：会移动剩下的所有元素，很慢！

当队列里有成千上万个元素时，每次 pop(0) 都要移动后面所有元素，程序会变得非常慢。所以绝对不要用 list 当队列。

新手常犯的错误

1. 空队列上调用 front() 或 back()

队列为空时，front() 和 back() 的行为是未定义的（程序可能会崩溃）。所以使用前一定要判断是否为空。

queue<int> q;
// 错误：q 是空的，直接访问 front() 会导致未定义行为
// int x = q.front(); 

// 正确做法：
if (!q.empty()) {
    cout << q.front() << endl;
}

2. 忘记 pop() 只删除不返回

很多新手以为 pop() 会返回被删除的元素，于是写出这样的代码：

int x = q.pop();  // 错误！pop() 返回类型是 void

正确做法：

int x = q.front();
q.pop();

3. 混淆队首和队尾

队列是“先进先出”，所以 front() 是最先添加的元素，back() 是最后添加的。不要和 stack（栈）搞混了，栈是“后进先出”，用 top() 访问栈顶。

4. 在遍历时修改队列

如果一边用 front() 和 pop() 遍历，一边又往队列里 push 新元素，循环条件（!q.empty()）会永远为真，导致无限循环。务必小心：如果需要一边处理一边添加新任务，要控制好循环次数或用计数器。

// 危险示例（可能无限循环）
while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (满足某种条件) {
        q.push(x + 1);  // 又添加了新元素，队列永远不为空
    }
}

queue 的经典应用：广度优先搜索（BFS）

队列最出名的一个用途就是实现 广度优先搜索（BFS）。例如，你要在一个迷宫里找从起点到终点的最短路径，可以这样想：

从起点出发，把起点放入队列。
每次从队首取出一个格子，看看它四周（上、下、左、右）有没有可以走的格子，把这些新格子放入队尾。
重复第2步，直到找到终点或队列为空。

因为队列的“先进先出”特性，我们会先探索离起点最近的格子，再探索稍远的，一层一层往外扩，第一次到达终点的路径一定是最短的。这就是“广度优先”的含义。

如果你对 BFS 感兴趣，可以继续学习：图论基础、树的层序遍历、迷宫最短路径 等知识点。

queue队列适配器——先进先出的“排队”魔法