C++ STL之队列queue和双端队列deque
一. 概述
1.1 queue
std::queue 是 C++ STL 中的一个容器适配器，用于实现先进先出（FIFO，First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。
注：
- 先进先出：第一个插入的元素最先被移除。
- 底层容器：通常使用 deque 或 list 作为底层容器。
- 不支持随机访问。只能通过队头和队尾操作。且元素只能从队尾添加并从队首移除。
- 当队列为空时，调用 front、back 或 pop 会导致未定义行为。
1.2 deque
std::deque 是 C++ STL 中的双端队列，允许在两端高效地插入和删除元素。在C++中以模板类的形式存在，允许存储任意类型的数据。
注：
- 双端队列：可以在队首和队尾进行插入和删除操作。在两端插入和删除元素的时间复杂度为 O(1)，而在中间插入或删除的时间复杂度为 O(n)。
- 类型泛化：可以存储任意类型，包括内置类型、自定义类等。
- 动态大小：可以根据需要动态扩展。
- 支持随机访问，能够使用下标访问元素。
二. 初始化
2.1 头文件
#include <queue> // 队列
#include <deque> // 双端队列
2.2 queue的初始化
// 默认构造
queue<int> q;
// 使用 deque 初始化队列
deque<int> d = {1, 2, 3};
queue<int> q(d);
// 初始化列表
queue<int> q({1, 2, 3});
// 拷贝构造
queue<int> q1;
q1.push(1);
q1.push(2);
queue<int> q2 = q1;
2.3 deque的初始化
// 默认构造
deque<int> d;
// 初始化列表
deque<int> d = {1, 2, 3};
// 指定大小并初始化元素
deque<int> d(5);
// 指定大小并指定初始值
deque<int> d(5, 10);
// 通过已有容器初始化
vector<int> v = {1, 2, 3};
deque<int> d(v.begin(), v.end());
三. 成员函数
3.1 queue
| 接口 | 含义 |
|---|---|
| push | 添加元素到队尾。 |
| pop | 移除队头元素。 |
| front | 返回队首元素的引用。 |
| back | 返回队尾元素的引用。 |
| empty | 判断队列是否为空，空（true）。 |
| size | 获取队列中元素个数。 |
| emplace | 在队尾直接构造元素，避免了不必要的复制或移动操作。 |
3.2 deque
| 接口 | 含义 |
|---|---|
| push_back | 在队尾添加元素。 |
| push_front | 在队头添加元素。 |
| pop_back | 移除队尾元素。 |
| pop_front | 移除队头元素。 |
| front | 返回队首元素的引用。 |
| back | 返回队尾元素的引用。 |
| empty | 判断队列是否为空，空（true）。 |
| size | 获取队列中元素个数。 |
| resize | 改变实际元素的个数。 |
| assign | 用新元素替换原有内容。 |
| operator[] | 访问指定索引的元素。 |
| at | 使用经过边界检查的索引访问元素。 |
| begin | 返回指向容器中第一个元素的迭代器。 |
| end | 返回指向容器最后一个元素所在位置后一个位置的迭代器。 |
| rbegin | 返回指向最后一个元素的迭代器。 |
| rend | 返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin | 和 begin 相同，但在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend | 和 end 相同，但在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin | 和 rbegin 相同，但在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend | 和 rend 功能相同，但在其基础上，增加了 const 属性，不能用于修改元素。 |
| insert | 在指定的位置插入一个或多个元素。 |
| erase | 移除一个元素或多个元素。 |
| clear | 移出所有的元素，容器大小变为 0。 |
| swap | 交换两个容器的所有元素。 |
| emplace | 在指定的位置直接生成一个元素。 |
四. 遍历方式
4.1 queue
不支持直接遍历，因为它没有提供迭代器（因此不能直接使用范围基于的 for 循环）
4.1.1 使用 pop 方法遍历
注意队列的内容会被修改，因此在遍历后队列将变为空
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
// 通过 pop 遍历队列
while (!q.empty()) {
cout << q.front() << " "; // 输出队头元素
q.pop(); // 移除队头元素
}
return 0;
}
/*
output:
1 2 3
*/
4.1.2 使用辅助容器
使用辅助容器可以保留原队列的内容，但会增加额外的内存开销
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
// 将元素复制到 vector
vector<int> vec;
while (!q.empty()) {
vec.push_back(q.front());
q.pop();
}
// 遍历 vector
for (const auto& value : vec) {
cout << value << " "; // 输出 1 2 3
}
return 0;
}
/*
output:
1 2 3
*/
4.1.3 使用 std::deque 作为底层容器
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
int main() {
deque<int> d = {1, 2, 3};
queue<int, deque<int>> q(d); // 使用 deque 初始化队列
// 通过 deque 遍历
for (const auto& value : d) {
cout << value << " "; // 输出 1 2 3
}
return 0;
}
/*
output:
1 2 3
*/
4.2 deque
4.2.1 for循环
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4, 5};
for (size_t i = 0; i < d.size(); ++i) {
cout << d[i] << " ";
}
return 0;
}
/*
output:
1 2 3 4 5
*/
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4, 5};
for (const auto& value : d) {
cout << value << " ";
}
return 0;
}
/*
output:
1 2 3 4 5
*/
4.2.2 迭代器
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4, 5};
for (auto it = d.begin(); it != d.end(); ++it) {
cout << *it << " ";
}
return 0;
}
/*
output:
1 2 3 4 5
*/
4.2.3 反向迭代器
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> d = {1, 2, 3, 4, 5};
for (auto it = d.rbegin(); it != d.rend(); ++it) {
cout << *it << " ";
}
return 0;
}
/*
output:
5 4 3 2 1
*/
原文地址：https://blog.csdn.net/qq_44961737/article/details/142442329
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！