3.1 C++ STL 双向队列容器

双向队列容器(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()函数向队列的末尾和首部分别添加了两个元素1112。接着,使用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;
}