队列——queue

Hello，这是你们的苦力怕。今天我去医院做核酸检测，排了老长的队，wait了半个多小时才做完，真是把我整无语死了，但是我在wait的过程中突然想到了一个问题：啥数据结构跟排队很像？对了，就是大名鼎的队列

---

目录

什么是队列？

队列的用法

队列的头文件

队列的定义

用法

栗子

队列的更改操作

在尾部增加一个元素

在头部删除一个元素

栗子

访问操作

查询队列是否为空

查询队列的元素个数

查询队列的队首

查询队尾的值

栗子

原理

总结

---

什么是队列？

队列是一种线性数据结构，也就意味着它的本质上就是有特殊功能的数组，当然我们不能直接用一个数组来实现它。具体实现方法我后面会说。

同时，队列的英文为queue，是一种具有先进先出机制的数据结构，相当于说，队列就是先进去的先出来，后进去的后出来，井然有序，绝不会出现插队的现象。

它支持的改变队列内部结构和值的操作应有两个

1. 在整个队列的尾部增加一个元素
2. 在整个队列的头部删除一个元素

而一般来说，队列所支持的访问操作应有四个：

1. 查询队列是否为空
2. 查询队列的元素个数

3. 查询队首（front）的值

4. 查询队尾（tear）的值

关于队列有这几个名词要大家记一下 ：

1. 队头（front）指整个队列的头部
2. 队尾（tear）指整个队列的尾端
3. 先进先出（FIFO，first in first out）指队列这种第一个进来第一个出去的机制
4. 队列（queue）指具有先进先出机制的线性数据结构

---

队列的用法

队列的头文件

在我们万能的C++标准库中也有关于队列(queue)的实现，它是用容器模板实现的，所以它就可以往里面放入各种类型的元素，并且头文件也叫<queue>，所以我们可以直接包含它，当然，它也包含在我们的万能头中。所以如果我们要使用标准库中的queue函数，我们就应该先在整个代码的前面加上一句

#include <queue>

虽然看起来很简单，但是其实很容易被遗忘，Debug的时间又longer了。-_-

队列的定义

用法

队列的定义语法如下

queue<Type, Container> Name

其中Type指的是所存放元素的类型是必填的

Container指的是存放元素的容器，可填可不填，不填时默认为deque。

注意：Container不能为vector，因为vector没法从开头删除元素。

Name指的是你定义的这个queue的名称，为合法标识符。

所以我这里给大家举几个栗子，让大家熟悉下

栗子

queue<int> q1;
queue<double, list> q2;
queue<long long, deque> q3;
queue<char, vector> q4;
queue<short> 4times;

我们可以看到，第一个q1肯定是合法的，它定义了一个名字为q1，以默认的deque为容器载体的存放int类型的queue

第二个它也是合法的，它定义了一个名字为q2,以list为容器载体的存放double类型的queue

第三个也是合法的，它定义了一个名字为q3，以deque为容器载体的存放long long类型的queue（注：尖括号里的第二项可以省略不写，达到同样的效果）

第四个是不合法的，因为vector不能做queue的容器载体，原因前面讲过，因为vector不支持pop_front()操作。

第五个也是不合法的，因为4times不是一个合法标识符，它以数字开头，使它变成了不合法标识符。

队列的更改操作

在尾部增加一个元素

在尾部（tear）增加一个元素，就好比在排队过程中，又有一个人来排队了，这种操作在queue中为push

语法：

Name.push(Value);

其中Name表示要在名称为Name的队列里添加元素

Value表示要被添加到Name里的元素的值（注：如果Value不是队列Name的类型，会报编译错误）

无返回值

在头部删除一个元素

在头部（front）删除一个元素，就好比在排队过程中，有一个人处理完了，便离开队伍了，这种操作在queue中为pop

语法:

Name.pop();

Name代表所要删除头部元素的队列的名称

无返回值

栗子

接下来我举几个栗子

queue<int> q;
q.push(5);
q.pop();
q.pop();
q.push('5');

我们可以看到第二行显然是正确的，它的作用是往q的尾部塞一个值为5的元素。

第三行也是正确的，它的作用是把q的头部，元素5删除。

第四行是错误的，因为q已经为空了，没法再删除元素了。

第五行也是错误的，因为'5'是一个char类型，没法加到int类型的q里去。

访问操作

查询队列是否为空

这种操作在STL中语法为empty，跟其他的数据结构很像

语法：

Name.empty();

这个函数的返回值为bool，队列为空时为true，非空时为false

其中Name代表的是要查询的队列的名称

查询队列的元素个数

这种操作在STL中语法为size，跟其他的数据结构很像

语法：

Name.size();

这个函数的返回值为一个无符号整数，代表这个队列所包含的元素的个数

其中Name代表的是要查询的队列的名称

查询队列的队首

这种操作在STL中语法为front

语法：

Name.front();

这个函数的返回值为一个Name的类型的值，代表这个队列的队首的值

其中Name代表的是要查询的队列的名称

查询队尾的值

这种操作在STL中语法为back

语法：

Name.back();

这个函数的返回值为一个Name的类型的值，代表这个队列的队尾的值

其中Name代表的是要查询的队列的名称

栗子

然后我再举几个栗子。

queue<int> q;
q.push(88);
cout << q.front() << " " << q.back() << endl;
q.push(99);
q.push(11);
cout << q.front() << " " << q.back() << endl;
q.pop();
cout << q.size() << endl;
q.pop();
q.pop();
cout << q.empty() << endl;

这段代码应输出

88 88
88 11
2
1

我们一个一个来看，第一行输出88 88，因为q里只有一个元素88，所以队首与队尾都是88

第二行输出88 11，因为此时q里已经有3个元素：88 99 11了，那它的队首就是88，队尾就是11

第三行输出2，因为此时q里被删了一个元素，成了99 11了，所以它的大小就是2

第四行输出1，因为此时q已经变成空队列了，所以是true，即1

原理

C++queue默认是依靠deque来运作的，而deque的原理就是循环队列

循环队列原理如下：

循环队列是将一个队列放到一个数组里去，用一个变量head标记在该数组中队头的位置，用一个变量tail来标记在该数组中队尾后一个的位置（因为如果直接记队尾的话会更不好操作），初始状态下，head=tail，代表该队列为空，加入一个元素就是先把数组的tail位置更换成加入的元素，再tail++，删除一个元素就是把数组的head++（因为如果把每一个位置都往前移的话，就会把时间复杂度拉到O(N)，相比之下，一个元素的空间可以忽略不计）。判断是否为空就是判断head是否等于tail，如果相等就是空的，反之非空。判断队首和队尾就直接把相应位置的值输出即可（tail要减1）。判断长度就是把head+数组的大小减去tail再模上数组的大小输出（想想为什么）。如果head或tail超过了数组的上线，head和tail可以重新变成1，这也是为什么叫它循环队列。

总结

队列是一个非常常用的数据结构，大家一定要掌握它哦。

今天苦力怕就讲到这里，886