114 std::queue
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 概述
std::queue 是 C++ 标准模板库(STL)中的一个容器适配器，它提供了先进先出(FIFO)的数据结构功能。
1.1 基本特性
- 队列数据结构，遵循 FIFO (First-In First-Out) 原则
- 是一个容器适配器，底层默认使用
std::deque作为容器 - 需要包含头文件
<queue>
2. 模板声明
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
template <class T, class Container = deque<T>>
2
class queue;
2.1 模板参数
T: 存储元素的类型Container: 底层容器类型，默认为std::deque<T>
3. 成员类型
| 成员类型 | 定义 |
|---|---|
value_type | Container::value_type |
reference | Container::reference |
const_reference | Container::const_reference |
size_type | Container::size_type |
container_type | Container |
4. 成员函数
4.1 元素访问
| 函数 | 描述 |
|---|---|
front() | 返回队列首元素的引用 |
back() | 返回队列尾元素的引用 |
4.2 容量
| 函数 | 描述 |
|---|---|
empty() | 检查队列是否为空 |
size() | 返回队列中元素的数量 |
4.3 修改器
| 函数 | 描述 |
|---|---|
push() | 在队列尾部插入元素 |
emplace() | 在队列尾部原位构造元素 |
pop() | 移除队列首元素 |
swap() | 交换两个队列的内容 |
5. 非成员函数
| 函数 | 描述 |
|---|---|
operator==, operator!= | 比较两个队列的内容 |
operator<, operator<= | 按字典序比较两个队列 |
operator>, operator>= | 按字典序比较两个队列 |
std::swap(queue) | 特化的 std::swap 算法 |
6. 底层容器选择
std::queue 可以使用不同的底层容器：
- std::deque (默认)
- std::list
6.1 不同容器的性能比较
| 操作 | std::deque | std::list |
|---|---|---|
push() | O(1) | O(1) |
pop() | O(1) | O(1) |
front() | O(1) | O(1) |
back() | O(1) | O(1) |
7. 使用示例
7.1 基本使用
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <queue>
3
4
int main() {
5
std::queue<int> q;
6
7
// 添加元素
8
q.push(1);
9
q.push(2);
10
q.push(3);
11
12
// 访问元素
13
std::cout << "Front element: " << q.front() << std::endl;
14
std::cout << "Back element: " << q.back() << std::endl;
15
16
// 移除元素
17
q.pop();
18
std::cout << "After pop, front element: " << q.front() << std::endl;
19
20
// 大小
21
std::cout << "Queue size: " << q.size() << std::endl;
22
23
return 0;
24
}
7.2 使用自定义底层容器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <queue>
3
#include <list>
4
5
int main() {
6
std::queue<int, std::list<int>> q;
7
8
q.push(10);
9
q.push(20);
10
q.push(30);
11
12
while (!q.empty()) {
13
std::cout << q.front() << " ";
14
q.pop();
15
}
16
17
return 0;
18
}
8. 注意事项
std::queue不提供迭代器，不能遍历队列中的元素- 调用
front()或back()前应确保队列不为空 - 调用
pop()前应确保队列不为空 - 对于多线程环境，需要额外的同步机制
9. 性能考虑
- 所有操作的时间复杂度都是 O(1)
- 内存使用取决于底层容器的实现
- 如果需要频繁的随机访问，应考虑其他数据结构
10. 应用场景
- 任务调度系统
- 广度优先搜索(BFS)算法
- 消息传递系统
- 缓冲区管理
- 打印队列等需要 FIFO 顺序的场景
std::queue 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
push | 在队列尾部插入元素 | void push( const T& value ); | queue<int> q; q.push(10); | 将元素拷贝到队列尾部。时间复杂度：O(1)。 |
emplace | 在队列尾部直接构造元素 | template< class... Args > void emplace( Args&&... args ); | queue<std::string> q; q.emplace("hello"); | 避免拷贝，直接构造元素。C++11 引入。 |
pop | 移除队列头部元素 | void pop(); | queue<int> q; q.push(1); q.pop(); | 不返回被删元素。需确保队列非空（否则 UB）。 |
front | 访问队列头部元素 | reference front();const_reference front() const; | queue<int> q{ {1,2} }; cout << q.front(); // 输出1 | 返回引用，可直接修改元素。需确保队列非空。 |
back | 访问队列尾部元素 | reference back();const_reference back() const; | queue<int> q{ {1,2} }; cout << q.back(); // 输出2 | 同 front，但操作尾部元素。 |
size | 返回队列元素数量 | size_type size() const; | queue<int> q; cout << q.size(); // 输出0 | 返回值为无符号整数。 |
empty | 检查队列是否为空 | bool empty() const; | if (q.empty()) cout << "队列为空"; | 等价于 size() == 0，但可能更高效。 |
swap | 交换两个队列的内容 | void swap( queue& other ) noexcept; | queue<int> q1, q2; q1.swap(q2); | C++11 引入，高效（仅交换内部指针）。 |
补充说明：
- 底层容器：
std::queue默认基于std::deque，也可指定其他容器（如std::list）：queue<int, list<int>> customQueue; - 异常安全：除
emplace可能因构造失败抛异常外，其他操作通常提供强异常保证。 - 线程安全：需用户自行同步访问（非线程安全容器）。
完整示例代码：
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <queue>
3
using namespace std;
4
5
int main() {
6
queue<int> q;
7
8
q.push(1); // 队列: [1]
9
q.emplace(2); // 队列: [1, 2]
10
cout << "Front: " << q.front() << endl; // 1
11
cout << "Back: " << q.back() << endl; // 2
12
13
q.pop(); // 队列: [2]
14
cout << "Size: " << q.size() << endl; // 1
15
16
queue<int>().swap(q); // 清空队列
17
cout << "Empty? " << q.empty() << endl; // 1 (true)
18
}
文章目录