c++的STL（8） -- queue

queue容器概述 

•  queue容器实现了实现了和队列相同结构的容器。

如图，队列这种结构有两端:  队首和队尾。 对于队列，我们添加数据只能从队尾添加，删除数据只能从队首删除。是一种先进先出的结构。 --  当然读取数据也只能从队首或者队尾读取。

queue容器的实现 

queue也是一个模板类:

template <class _Ty, class _Container = deque<_Ty>>  class queue{}

上面就是其模板的类型参数，很明显，它接受两个参数，一个是其存储数据的类型，一个则是一个容器类型。 

为什么要接受一个容器类型呢? 

因为queue容器其实是在我们之前学习的deque，list容器的基础上，实现了其它的功能，其内部存储数据还是使用这三个容器(其内部定义了容器的对象)。

为什么要这么做呢?

因为，我们之前学习过的容器功能已经很强大了，但是在某些场景下它们的功能可能并不适用，但是重新开发新的容器也并不高效。

所以我们可以根据我们已有的容器，通过相应的封装和组合，实现对应的功能。

queue就是这样的一个容器，它在deque，list这三个容器的基础之上进行了封装，实现了符合栈结构的容器。(基于这种原理，我们也可以实现我们自己的容器)  --  对于queue而言这两个容器为基础容器。

queue中的函数 

注意: 我们前面说到，理论上deque可以使用vector，list，deque三个容器存储数据，但是具体情况还需要根据queue所要实现的功能来定。(就是看实现queue所需要的功能时用到的函数容器支不支持)

对与queue，只要容器支持  front()、back()、push_back()、pop_front()、empty() 和 size()这 6个成员函数就可以作为queue第二个模板类型参数。  --   因为queue是一个先进先出的结构，并且访问元素也只能访问队首和队尾的元素。 

queue需要基础容器支持pop_front();  所以vector容器是不能作为queue的基础容器的，因为它不支持此函数。

1. 创建queue对象 

创建一个不包含任何参数的对象

queue<int> q1;   // 创建了一个存储int数据的queue对象， 如果我们不传入第二个类型参数，那么默认使用deque作为queue的 基础容器。

指定queue容器的基础容器 

我们可以通过类型参数的第二个参数指定queue的基础容器，但是只能使用list，deque这两个容器中的一个。

queue<int,list<int>>  q1;   // 创建q1，我们指定了list容器作为queue容器的基础容器。

注意:  除去默认情况(使用deque容器为默认情况)，我们要使用其它容器作为queue容器的基础容器，需要导入对应容器的头文件。

还有，虽然我们可以指定基础容器，但是默认的基础容器的效率是最高的。

比如:   使用list为基础容器，需要导入list头文件

#include <list> 

#inlcude <queue> 

queue<int,list<int>> q1; 

使用基础容器初始化stack容器。 

注意: 使用基础容器初始化queu容器，必须保证使用的基础容器和queu内部的基础容器是相同的。

deque<int> d1{ 1,2,3,4,5 };

// 使用别的容器初始化
queue<int> q1(d1);   // 使用deque容器的数据初始化queue，此时queue的基础容器应该为deque(也就是默认情况)。

list<int> l1{ 1,2,3,4,5 };

// 使用别的容器初始化
queue<int,list<int>> q1(l1);  // 使用list容器的数据初始化queue，此时queue的容器应该为vector。 

使用别的stack容器给stack初始化 

    list<int> l1{ 1,2,3,4,5 };
    // 使用别的容器初始化
    queue<int,list<int>> q1(l1);

    queue<int, list<int>> q2(q1);   // 方式1:  使用s1初始化s2
    queue<int, list<int>> q3 = s1; // 方式2:   使用s1初始化s3

2. queue容器中的函数 

•  push(elem)

用于在队尾插入元素，函数内部其实是调用基础容器的push_back()方法在其尾部添加一个元素。//  因为队尾元素是最后位置的元素，所以对于基础容器就是在尾部添加数据。
 

• pop()  --  无需参数

用于在队首删除元素,  函数内部其实是调用基础容器的pop_front()方法在其尾部添加一个元素。//  因为队首元素是最前面位置的元素，所以对于基础容器就是在首部删除数据。

• 其余函数

其余函数和上面函数是一样的，都是通过调用内部基础容器的相应函数来实现功能，但是其用法和基础容器对应函数的用法是一样的，所以就不再说明了。

queue没有迭代器 

因为queue结构的原因，删除元素我们只能在对首删除，添加元素我们只能在队尾添加，查询元素也只能查询队首和队尾的元素，要想查询别的元素就需要将前面的元素出队，让查询的元素作为队首，我们才能查询到对应的元素。

在这种场景下，是不需要迭代器的，使用迭代器的话要想访问别的数据，就不一定需要出队了。 而使用迭代器，可以直接访问任意位置的元素，就会破坏这种结构。