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);// 将元素复制到 vectorvector<int> vec;while (!q.empty()) {vec.push_back(q.front());q.pop();}// 遍历 vectorfor (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 
*/