双向队列容器（Deque）是C++ STL中的一种数据结构，是一种双端队列，允许在容器的两端进行快速插入和删除操作，可以看作是一种动态数组的扩展，支持随机访问，同时提供了高效的在队列头尾插入和删除元素的操作。
Deque 双向队列容器与Vector非常相似，它不但可以在数组尾部插入和删除元素，还可以在头部进行插入和删除，队列算法的时间复杂度也是常数阶O(1)，队列内部的数据机制和性能与Vector不同，一般来说当考虑到容器元素的内存分配策略和操作的性能时，Deque相对于Vector较有优势。
3.1 单向队列的基本操作
这是一段使用STL queue容器的C++代码，展示了如何定义并操作queue队列，包括如何向队列中添加元素、弹出元素、查询队头、队尾信息以及获取队列大小。
在代码中，首先定义了一个queue<int>类型的变量que，这是一个类型为int的队列容器。使用push()函数向队列中加入两个元素1和2。接着，使用while循环，判断队列是否为空，如果不为空，则使用front()和back()函数来分别查询队头和队尾元素。最后，使用pop()函数将队头元素出队列。
#include <iostream>
#include <queue>
using namespace std;
int main(int argc, char* argv[])
{
queue<int> que;
que.push(1); // 入队列
que.push(2);
while (!que.empty())
{
cout << "Head: " << que.front() << endl; // 队头
cout << "End: " << que.back() << endl; // 队尾
que.pop(); // 出队列
}
cout << "Size: " << que.size() << endl;
system("pause");
return 0;
}
3.2 双向队列的基本操作
这是一段使用STL deque容器的C++代码，展示了如何向deque双端队列中插入和弹出元素，以及如何查询和获取双端队列的元素信息。
在代码中，首先定义了一个双端队列deque<int>类型的变量deq，并使用花括号列表初始化的方式插入了10个整数元素。代码使用push_back()和push_front()函数向队列的末尾和首部分别添加了两个元素11和12。接着，使用pop_back()和pop_front()函数分别从队列的末尾和首部弹出了一个元素。
使用empty()函数判断双端队列是否为空，并使用front()和back()函数获取队列的首个元素和末尾元素value。同时，使用size()函数获取双端队列的元素个数和max_size()函数获取双端队列最大可容纳的元素数。
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char* argv[])
{
deque<int> deq{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
deq.push_back(11); // 向队尾放入元素
deq.push_front(12); // 向队头放入元素
deq.pop_back(); // 从队尾弹出一个元素
deq.pop_front(); // 从队头弹出一个元素
cout << "是否为空: " << deq.empty() << endl;
cout << "首个元素: " << deq.front() << endl;
cout << "末尾元素: " << deq.back() << endl;
cout << "元素个数: " << deq.size() << endl;
cout << "最大元素数: " << deq.max_size() << endl;
system("pause");
return 0;
}
3.3 双向队列正/反向遍历
这是一段使用STL deque容器的C++代码，展示了如何遍历双端队列，并通过迭代器实现正向和反向遍历。
代码使用reverse_iterator类型的迭代器实现了双端队列的反向遍历。由于双端队列底层实现是双向链表，因此支持反向遍历。
最后，代码使用cout输出遍历时访问到的每个元素的值。需要注意的是，在输出时，对于迭代器类型的元素需要通过解引用符(*)来获取其值。
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char* argv[])
{
deque<int> deq{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// 双向队列的正向遍历: 此处有两种遍历方法
for (int x = 0; x < deq.size(); x++) // 第一种,通过下标遍历数据
cout << deq[x] << " " ;
cout << endl;
deque<int>::iterator start, end; // 第二种,通过迭代器遍历数据
end = deq.end();
for (start = deq.begin(); start != end; start++)
cout << (*start) << " " ;
cout << endl;
// 双向队列的反向遍历: 此处我们使用迭代器遍历
deque<int>::reverse_iterator rstart, rend;
rend = deq.rend();
for (rstart = deq.rbegin(); rstart != rend; rstart++)
{
cout << (*rstart) << " " ;
}
system("pause");
return 0;
}
3.4 双向队列插入/弹出元素
这是一段使用STL deque容器的C++代码，展示了如何定义并操作deque双端队列，包括插入、弹出和删除元素等操作。代码通过调用pop_front()和pop_back()函数从队列的首尾部分别弹出元素。同时，使用erase()函数删除了第二个元素(下标索引为1)。
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char* argv[])
{
deque<int> deq{ 1, 2, 3, 4, 5 };
deq.push_back(6); // 从队列末尾追加元素
deq.push_front(0); // 从队列首部追加元素
deq.insert(deq.begin() + 1, 9); // 在第二个元素前插入9
deq.pop_front(); // 从队列首部弹出元素
deq.pop_back(); // 从队列尾部弹出元素
deq.erase(deq.begin() + 1); // 弹出第二个(下标索引)元素
for (int x = 0; x < deq.size(); x++)
cout << deq[x] << " ";
cout << endl;
system("pause");
return 0;
}
3.5 函数参数传递双向队列
该代码展示了如何定义并操作deque双端队列，以及如何通过定义只读迭代器实现遍历输出。
在代码中，首先定义了一个双端队列deque<int>类型的变量deq，并使用花括号列表初始化的方式插入了9个整数元素。
然后，代码定义了一个PrintDeque函数来输出双端队列的元素。这个函数的参数是一个const引用类型的deque<int>对象，表示只读的双端队列。在函数内部，使用了const_iterator类型的迭代器来遍历deque中的所有元素，并依次输出。
接着，代码调用PrintDeque函数，将之前创建的变量deq作为参数传递给这个函数，从而展示了如何遍历输出双端队列的所有元素。
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
// 定义只读deque双端队列
void PrintDeque(const deque<int> &deq)
{
for (deque<int>::const_iterator item = deq.begin(); item != deq.end(); item++)
{
// 迭代器类型: iterator=>普通迭代器 reverse_iterator=>逆序迭代器 const_iterator=>只读迭代器
cout << (*item) << endl;
}
}
int main(int argc, char* argv[])
{
deque<int> deq = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
PrintDeque(deq);
system("pause");
return 0;
}
本文作者： 王瑞
本文链接： https://www.lyshark.com/post/29f63c41.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！