3.1 C++ STL 双向队列容器_c++双向队列

双向队列容器（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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23