第8章 queue 容器详解

queue（队列）是 STL 中的容器适配器，基于序列式容器（默认 deque）封装而成，遵循"先进先出（FIFO）"原则，即先插入的元素先被访问、先被删除，与 stack（先进后出）形成互补，常与 set、map 等容器配合使用。

🎯 本章学习目标

学完本章，你将能够：

理解队列的"先进先出"（FIFO）核心思想
熟练使用 queue 的 push、pop、front、back 等基本操作
理解 queue 是容器适配器，掌握底层容器的选择
掌握广度优先搜索（BFS）的基本思想与队列的配合
理解队列与栈的核心区别
了解队列的常见应用场景
在实际问题中识别并应用队列的思想
掌握队列的常见误区与注意事项

🗺️ 本章知识图谱

queue 队列
├── 核心特性
│   ├── 先进先出（FIFO）
│   ├── 容器适配器
│   ├── 仅头尾操作
│   └── 无迭代器
├── 基本用法
│   ├── 定义与头文件
│   ├── push（队尾入队）
│   ├── pop（队头出队）
│   ├── front（访问队头）
│   ├── back（访问队尾）
│   ├── empty（判空）
│   └── size（大小）
├── 底层实现
│   ├── 默认 deque
│   ├── 可选 list
│   └── 底层容器对比
├── 经典应用
│   ├── BFS 广度优先搜索
│   ├── 任务排队
│   ├── 消息队列
│   └── 缓冲区
├── 注意事项
│   ├── 无 clear 方法
│   ├── 不可遍历
│   └── 空队访问 front 崩溃
└── 适用场景与选型

一、queue 核心特性

🍎 生活比喻：queue 就像排队买奶茶——先来的人排在前面，先拿到奶茶先走。后来的人排在队尾，必须等前面的人都买完才能轮到自己。你不能插队（中间插入），也不能直接叫中间的人出来（中间删除）。

容器适配器：不独立存储数据，依赖底层容器（默认 deque，也可指定 list）；
先进先出（FIFO）：第一个插入的元素第一个被删除，类似排队买票，先到先得；
操作限制：仅支持在队尾插入、队头删除和访问，不支持随机访问和中间插入删除；
高效操作：插入（队尾）和删除（队头）效率高，具体取决于底层容器（deque 默认最优），均为 O(1)。

queue 与 set、stack 的核心区别：

与 set：set 是关联式容器，侧重去重、查找；queue 是容器适配器，侧重"先进先出"的顺序操作；
与 stack：stack 是"先进后出"，queue 是"先进先出"，二者均为容器适配器，适用场景不同。

🔥 高频考点：FIFO 特性、队尾插入队头删除、时间复杂度 O(1)，这些是选择题的高频考点。

二、queue 基础用法（完整代码）

使用 queue 需包含 <queue> 头文件。

cpp

#include <iostream>
#include <queue>  // queue的头文件
#include <list>   // 可指定底层容器为list
using namespace std;

int main() {
    // 1. 定义queue（多种方式）
    queue<int> q1;  // 默认底层容器为deque，存储int类型
    queue<int, list<int>> q2;  // 指定底层容器为list
    queue<int> q3(q1);  // 拷贝构造
    
    // 2. 插入元素（队尾插入）
    q1.push(1);  // 队尾插入1，队列：[1]
    q1.push(2);  // 队尾插入2，队列：[1, 2]
    q1.push(3);  // 队尾插入3，队列：[1, 2, 3]
    
    // 3. 访问元素（仅能访问队头和队尾）
    cout << "队头元素：" << q1.front() << endl;  // 输出：1（队头，第一个插入的元素）
    cout << "队尾元素：" << q1.back() << endl;   // 输出：3（队尾，最后一个插入的元素）
    
    // 4. 删除元素（队头删除）
    q1.pop();  // 删除队头元素1，队列：[2, 3]
    cout << "删除队头后，队头元素：" << q1.front() << endl;  // 输出：2
    
    // 5. 常用操作
    cout << "\n队列大小（元素个数）：" << q1.size() << endl;  // 输出：2
    if (q1.empty()) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列非空" << endl;
    }
    
    // 6. 遍历队列（需通过弹出元素实现，会破坏原队列）
    cout << "\n队列遍历（弹出元素）：";
    while (!q1.empty()) {
        cout << q1.front() << " ";
        q1.pop();  // 弹出队头元素
    }
    cout << endl;  // 输出：2 3（遍历后队列为空）
    
    // 补充：指定list为底层容器的queue
    q2.push(10);
    q2.push(20);
    cout << "\nq2队头：" << q2.front() << "，队尾：" << q2.back() << endl;  // 输出：10 20
    
    return 0;
}

操作汇总表

操作	语法	说明
插入（队尾）	push(元素)	在队列尾部插入一个元素，效率 O(1)
删除（队头）	pop()	删除队列头部的元素，无返回值，效率 O(1)
访问队头	front()	返回队列头部的元素（不删除），需确保队列非空
访问队尾	back()	返回队列尾部的元素（不删除），需确保队列非空
判空	empty()	队列为空返回 true，否则返回 false
获取大小	size()	返回队列中元素的个数
清空	无 clear()	需通过循环 pop() 弹出所有元素

💡 小技巧：queue 没有 clear() 方法，清空队列的标准写法是 while (!q.empty()) q.pop();。也可以用技巧 queue<int>().swap(q); 来快速清空。

三、queue 的底层容器选择

queue 是容器适配器，底层依赖其他容器实现，常用的底层容器有 3 种，各有优劣：

1. deque（默认，推荐）

优势：deque 支持双端插入/删除，队头队尾操作效率都是 O(1)，内存管理灵活，不会像 vector 那样有扩容拷贝问题；
劣势：随机访问效率略低于 vector（但 queue 不需要随机访问）；
适用场景：绝大多数场景，默认即可。

2. list

优势：list 插入删除效率高，任意位置都是 O(1)；
劣势：内存不连续，缓存命中率低，空间开销大（每个节点有指针）；
适用场景：元素很大、频繁插入删除的场景（但对 queue 来说影响不大）。

3. vector（不推荐）

劣势：vector 的队头删除效率是 O(n)（需要移动所有元素），性能极差；
结论：绝对不要用 vector 作为 queue 的底层容器。

四、常见误区与注意事项

⚠️ 易错点 1：queue 没有 clear() 方法。清空队列需通过循环 pop() 弹出所有元素，或者用 queue<int>().swap(q) 技巧。

⚠️ 易错点 2：不能访问中间元素。queue 仅支持访问队头和队尾，无法访问队列中间的元素，也不支持遍历。

⚠️ 易错点 3：弹出元素前需判空。调用 pop()、front()、back() 前，需先通过 empty() 判断队列是否非空，否则会导致未定义行为（程序崩溃）。

⚠️ 易错点 4：混淆 front 和 back。front 是队头（最先插入的元素），back 是队尾（最后插入的元素），不要搞反了。

⚠️ 易错点 5：底层容器影响效率。选择不同的底层容器会影响 queue 的效率，默认用 deque 即可，不要用 vector。

🔥 高频考点：空队列调用 front()/back()/pop() 会崩溃，这是判断题和选择题的常考点。

五、实战应用场景

queue 的"先进先出"特性决定了其适用场景，常与 set、map 等容器配合使用：

1. 广度优先搜索（BFS）—— 算法题高频

BFS 是图和树的常用遍历算法，核心就是用 queue 存储待访问的节点，按层次顺序遍历。

示例：二叉树的层序遍历

cpp

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void levelOrder(TreeNode* root) {
    if (root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";  // 访问当前节点
        if (node->left != NULL) q.push(node->left);   // 左子节点入队
        if (node->right != NULL) q.push(node->right); // 右子节点入队
    }
}

🔥 高频考点：BFS 是 queue 最经典的应用，几乎是算法竞赛的必考题。

2. 任务排队场景

如后台任务队列、消息队列、打印任务队列等，先来的任务先处理。

3. 缓冲区

如生产者-消费者模型中的缓冲区，生产者往队尾放数据，消费者从队头取数据。

4. 限流场景

如控制请求访问频率，按顺序处理请求，超出容量的请求被拒绝。

六、queue 与 stack 对比

特性	queue（队列）	stack（栈）
核心原则	先进先出（FIFO）	先进后出（LIFO）
插入位置	队尾（back）	栈顶（top）
删除位置	队头（front）	栈顶（top）
访问元素	front()、back()	top()
底层容器	默认 deque	默认 deque
典型应用	BFS、任务排队	括号匹配、递归模拟
生活比喻	排队买奶茶	摞盘子

七、🔖 本章小结

queue 是一种简单、高效的容器适配器，核心优势是"先进先出"的特性和 O(1) 的头尾操作效率。使用时需注意：无 clear() 方法、不支持遍历、访问 front/back 前需判空。BFS 是 queue 最经典的应用场景，默认使用 deque 作为底层容器即可满足绝大多数需求。

八、📝 实战练习

练习题 1（选择题）

题目： queue 遵循的核心原则是？

A. 先进后出（LIFO） B. 先进先出（FIFO） C. 优先级高的先出 D. 随机访问

🔑 点击查看答案与解析

答案： B

**解析：**queue（队列）的核心特性是先进先出（First In First Out），最先入队的元素最先出队。A 是 stack 的特性，C 是 priority_queue 的特性，D 是 vector、deque 的特性。

练习题 2（判断题）

题目： queue 可以使用迭代器遍历所有元素（）

🔑 点击查看答案与解析

答案： 错误

**解析：**queue 是容器适配器，屏蔽了底层容器的迭代器接口，不支持遍历。只能通过 front() 和 back() 访问队头和队尾，或者依次弹出元素来访问（会破坏原队列）。

练习题 3（选择题）

题目： queue 的默认底层容器是？

A. vector B. list C. deque D. array

🔑 点击查看答案与解析

答案： C

**解析：**queue 默认底层容器是 deque。deque 支持双端操作，队头队尾插入删除都是 O(1)，非常适合作为队列的底层。vector 队头删除是 O(n)，效率低，不适合。

练习题 4（程序阅读题）

题目： 阅读以下代码，写出输出结果：

cpp

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << q.front() << " ";
    q.pop();
    q.push(40);
    cout << q.back() << " ";
    cout << q.front() << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 10 40 20

解析：

push(10) → 队列：[10]
push(20) → 队列：[10, 20]
push(30) → 队列：[10, 20, 30]
front() → 队头是 10，输出 10
pop() → 删除队头 10，队列：[20, 30]
push(40) → 队列：[20, 30, 40]
back() → 队尾是 40，输出 40
front() → 队头是 20，输出 20

最终输出：10 40 20

练习题 5（选择题）

题目： 以下关于 queue 的说法，正确的是？

A. queue 支持在中间插入元素 B. queue 的 pop() 返回被删除的元素 C. 空队列调用 front() 会导致未定义行为 D. queue 有 clear() 方法可以直接清空

🔑 点击查看答案与解析

答案： C

解析：

A 错误：queue 只能在队尾插入、队头删除，不能中间操作
B 错误：pop() 只删除不返回，要获取元素用 front()
C 正确：空队列调用 front()、back()、pop() 都会导致未定义行为（程序崩溃）
D 错误：queue 没有 clear() 方法，需要循环 pop

练习题 6（编程题）

题目： 输入 n 个整数，依次入队，然后依次出队并输出，模拟队列的先进先出特性。

**输入格式：**第一行一个整数 n，第二行 n 个整数 **输出格式：**一行，出队顺序的整数，用空格隔开

样例输入：

5
1 2 3 4 5

样例输出：

1 2 3 4 5

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<int> q;
    
    // 依次入队
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    
    // 依次出队并输出
    while (!q.empty()) {
        cout << q.front();
        q.pop();
        if (!q.empty()) cout << " ";
    }
    cout << endl;
    
    return 0;
}

**解析：**这道题是队列的基础应用题。元素按输入顺序入队，再按入队顺序出队，正好体现了队列"先进先出"的特性。注意输出格式，最后一个元素后面不要有多余的空格。

练习题 7（编程题）

题目： 给定一个正整数 n，使用队列输出 1 到 n 的二进制表示。 **输入格式：**一行，一个正整数 n。 **输出格式：**一行，1 到 n 的二进制表示，用空格隔开。

样例输入：

样例输出：

1 10 11 100 101

提示：利用队列的 BFS 思想，每次出队一个数，在后面分别加 0 和 1 入队。

🔑 点击查看答案与解析

参考代码：

cpp

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<string> q;
    q.push("1");  // 初始入队 "1"
    
    for (int i = 0; i < n; i++) {
        string curr = q.front();
        q.pop();
        cout << curr;
        if (i < n - 1) cout << " ";
        
        // 在当前二进制串后面加 0 和 1，入队
        q.push(curr + "0");
        q.push(curr + "1");
    }
    cout << endl;
    
    return 0;
}

**解析：**这道题巧妙利用了队列的 BFS 特性。二进制数可以看作是一棵二叉树（根是"1"，左子树加"0"，右子树加"1"），层序遍历的结果就是从小到大的二进制数。每次出队一个数，把它加 0 和加 1 的结果入队，就能按顺序生成所有二进制数。

九、📊 考点总结表

知识点	重要程度	出题形式	易错点
FIFO 特性	⭐⭐⭐⭐⭐	选择题、判断题	与 LIFO 混淆
push/pop/front/back	⭐⭐⭐⭐⭐	选择题、编程题	front 和 back 搞反
空队访问 front/back/pop	⭐⭐⭐⭐	判断题、选择题	忘记判空导致崩溃
无 clear() 方法	⭐⭐⭐	选择题、判断题	误以为有 clear
无迭代器、不可遍历	⭐⭐⭐	判断题	试图遍历队列
底层容器（默认 deque）	⭐⭐⭐	选择题	误以为默认是 vector
BFS 应用	⭐⭐⭐⭐⭐	编程题、阅读题	入队出队顺序
队列时间复杂度 O(1)	⭐⭐⭐⭐	选择题	与其他容器混淆

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  queue 必背速记卡                     │
├──────────────────────────────────────┤
│  1. 先进先出 FIFO，先来先服务         │
│  2. 队尾入队 push，队头出队 pop       │
│  3. 队头用 front，队尾用 back         │
│  4. 所有操作时间复杂度都是 O(1)       │
│  5. 默认底层容器是 deque              │
│  6. 没有 clear()，需循环 pop 清空     │
│  7. 没有迭代器，不能直接遍历          │
│  8. 空队调用 front/back/pop 会崩溃    │
│  9. 经典应用：BFS、任务排队           │
│  10. 与 stack 区别：FIFO vs LIFO     │
└──────────────────────────────────────┘

第8章 queue 容器详解 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、queue 核心特性 ​

二、queue 基础用法（完整代码） ​

操作汇总表 ​

三、queue 的底层容器选择 ​

1. deque（默认，推荐） ​

2. list ​

3. vector（不推荐） ​

四、常见误区与注意事项 ​

五、实战应用场景 ​

1. 广度优先搜索（BFS）—— 算法题高频 ​

2. 任务排队场景 ​

3. 缓冲区 ​

4. 限流场景 ​

六、queue 与 stack 对比 ​

七、🔖 本章小结 ​

八、📝 实战练习 ​

练习题 1（选择题） ​

练习题 2（判断题） ​

练习题 3（选择题） ​

练习题 4（程序阅读题） ​

练习题 5（选择题） ​

练习题 6（编程题） ​

练习题 7（编程题） ​

九、📊 考点总结表 ​

⭐ 必背速记卡 ​

第8章 queue 容器详解

🎯 本章学习目标

🗺️ 本章知识图谱

一、queue 核心特性

二、queue 基础用法（完整代码）

操作汇总表

三、queue 的底层容器选择

1. deque（默认，推荐）

2. list

3. vector（不推荐）

四、常见误区与注意事项

五、实战应用场景

1. 广度优先搜索（BFS）—— 算法题高频

2. 任务排队场景

3. 缓冲区

4. 限流场景

六、queue 与 stack 对比

七、🔖 本章小结

八、📝 实战练习

练习题 1（选择题）

练习题 2（判断题）

练习题 3（选择题）

练习题 4（程序阅读题）

练习题 5（选择题）

练习题 6（编程题）

练习题 7（编程题）

九、📊 考点总结表

⭐ 必背速记卡