queue知识点整理总结

往期内容： STL总目录-超详细

目录

1. queue是什么
2. 变量声明及成员函数
3. 队列的遍历
4. 循环队列

queue是什么？

queue的中文名字是队列，是一种“线性”储存结构，听了这两个名字，我们来想象一个画面，在游乐园的某个项目门口，排起了一条长长的直队(图文不符请谅解，只可意会不可言传)
队列就是一个“队列”一样的容器，先来的人站到队伍的最前面，后来的只能排在后面，队伍前面的先离队，后面的只有等排到自己时才能离开。
所以我们能总结出queue的性质：

• 先进先出，first in first out，就是我们常说的“FIFO”
• 只能从队尾插入元素，每次只能弹出队首的元素

这样大家应该就能理解我们为什么会称队列为一种“线性结构”了。
下面用一组图标演示一下队列中存储数据的特点

同样的，队列中存储的数据的类型也是任意的~

接下来看一下queue中的几个概念

• 队头（首）：即允许元素删除的一端
• 队尾：即允许元素插入的一端
• 入队：队列的插入操作
• 出队：队列的删除操作
• 空队列：没有插入任何元素的队列

变量声明及成员函数

相较于set和map来说，queue的用法更为简单，因为它的结构较为简单，没有复杂的功能，所以大可放心食用下面的内容

头文件

#include <queue>

定义与声明

用法（结构）：queue<类型> 名称

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
    queue<int> a;
    //定义一个名为a，存储int类型数据的队列
    queue<string> b;
    //定义一个名为b，存储string类型数据的队列
    return 0;
}

入队（插入元素） .push()

定义完一个属于我们自己的队列，接下来的第一步当然是要向队列中存入数据了，这时候便要用到.push()了。就像我们在前面说过的，由于队列具有FIFO的性质，所以.push()是将一个数据放到队尾（将一个数据压入队尾）。
用法（格式）：名称.push(x)x为与队列类型相同的数据

queue<int> que;
//构造int类型的队列

que.push(1); //que:1
que.push(3); //que:1,3
que.push(2); //que:1,3,2(队列不具有有序性，按存入顺序储存)

出队（弹出元素） .pop()

对应着入队的就是出队了，我们可以看到它的另一个名字叫“‘弹出’元素”，既然叫弹出，就表示了这个函数能够使队头元素被“弹出”，即删除队头元素而不返回队头元素的值。
用法（格式）：名称.pop()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

que.pop();
//que:3,2
//一定要记住弹出的是第一个元素而不是最后一个
que.pop();
//que:2

查看队列的长度 .size()

几乎是每个STL容器必备的函数.size()，依然，它的返回值是队列中元素的个数
用法（格式）：名称.size()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

cout << que.size() << endl;
//输出：3
que.pop();
cout << que.size() << endl;
//输出：2

查看队列是否为空 .empty()

同样是极为常见但较为少见的函数，它万年不变功能就是返回一个bool类型用于判断一个队列是否为空队列，如果为空队列返回true，否则返回false。一般作为if条件语句的判断条件。
用法（结构）：名称.empty()

queue<int> que;
//构造

if (que.empty()) {
    cout << "Nothing here" << endl;
} else {
    cout << "Have something" << endl;
}
//输出：Nothing here

que.push(1);
//向队列中插入一个元素，使队列不为空

//再判断
if (que.empty()) {
    cout << "Nothing here" << endl;
} else {
    cout << "Have something" << endl;
}
//输出：Have something

查看队头元素的值 .front() 查看队尾元素的值 .back()

与set和map不同的是，queue不需要也没有迭代器的写法！好耶ヽ(✿ﾟ▽ﾟ)ノ元素的调用更为简单，但有一定的限制，我们可以直接通过.front()和.back()查看和调用队头和队尾的元素。但同时，我们也只有这两个函数可用。这就意味着，我们无法查看队伍中间的其他元素。
用法（格式）：名称.front() 名称.back()

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

cout << a.front() << endl;
//输出：1
cout << a.back() << endl;
//输出：2

队列的遍历

为什么要单独说一说遍历呢？因为，队列的遍历方式不是靠单个函数或用法就能实现的，我们已经说过，队列中，只有队头元素和队尾元素是可以直接访问的，这就意味着，队列的遍历需要一点点小技巧。

思路1：

既然我们能访问的只有队头元素和队尾元素，那最简单的遍历方式便是：每次都查看队头元素，然后将队头元素弹出，队列中有几个元素我们就执行几次，这当然是可以很轻松的实现的：

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

for (int i = 0; i < que.size(); i++) { //遍历每一个元素
    cout << que.front() << " "; //输出当前队头元素
    que.pop(); //将队头元素弹出，使第二个元素变成队头元素
}
//输出：1 3 2

但问题是，如果我们用这种方式遍历完整个队列，我们的队列就被我们清空了！所以在大多数情况下，这种方式是不可行的。那么怎么办呢？

思路2

既然我们想保留这个队列，那我们就再开一个新的队列，一边输出一边存入不就好了吗？

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

queue<int> que1;
//构造一个新的队列用来重新存储原队列中的元素

for (int i = 0; i < que.size(); i++) {
    cout << que.front() << " ";
    que1.push(que.front()); //将原队列中的队头元素压入到新队列中
    que.pop();
}
//输出：1 3 2
//que1:1,3,2
//使que1成功的代替了que

思路3

虽然我们已经完成了任务，但我们可以发现这种方法还是太麻烦了，还要重新开一个新的队列，浪费空间不说，还容易让人搞混，典型的费力不讨好，那有没有更好的方法呢？当然有！
我们发现：思路2中其实并没有开一个新的队列的必要，我们完全可以将两个队列合并为一个，方法也很简单，循环的次数是一定的，而队尾的元素也不会对循环过程产生影响，那我们为什么要开一个新的队列呢，把原来的队首元素直接输出后移动到队尾不就好了吗？如果难以理解请继续看…

queue<int> que;
que.push(1);
que.push(3);
que.push(2);
//构造
//que:1,3,2

for (int i = 0; i < que.size(); i++) {
    cout << que.front() << " ";
    que.push(que.front());//将队首元素再次压入队尾
    que.pop();//弹出队头元素
}
//输出：1 3 2

上述代码中队列中元素的变化：

que:
1 3 2 (初始状态)

输出当前队头元素1  
//cout << que.front() << " ";

将当前队头元素1重新压入队尾 
//que.push(que.front());
1 3 2 1

弹出队头元素1 
//que.pop();
3 2 1

输出当前队头元素3

将当前队头元素3重新压入队尾
3 2 1 3

弹出当前队头元素3
2 1 3

输出当前队头元素2

将当前队头元素2重新压入队尾
2 1 3 2

弹出当前队头元素2
1 3 2

可以看到，经过一番操作，队列被我们完整的遍历了一遍，并且队列中元素的个数和顺序都没有发生改变，这样，我们就完成了对队列的完整遍历！ψ(｀∇´)ψ
此外，还有一点需要注意的是：我们可以发现循环的条件中用到了.size()，这意味着我们不能在循环的过程中插入或弹出一个元素（即改变队列的长度），所以如果我们想插入元素的话，需要实现定义好一个常量存储循环的次数，如int n = a.size()这样就避免了改变队列而导致循环次数出现变化的情况。

循环队列

这部分内容属于进阶内容，难度较高，理解难度较大，本蒟蒻也只是略知一二，仅为对循环队列的概念的理解做一个参考，代码实现部分还需要在修炼修炼Orz

同样是从名字入手，“‘循环’队列”重在这循环二字，我们刚刚讲过的队列是一条线，那么怎么会出现循环呢？没有错，当我们把一条线首位相接，出现的难道不就是一条循环的数据了吗。而循环队列正式这样的一种存储方式。
用更加专业一些的文字叙述：

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
——百度

那么在循环队列中数据是如何存入的呢？我们说了循环队列是形如一条闭环的，但他本质上还是一条线，并且是一条长度固定的线，那么我们依然有从尾部压入数据的存储方式，同时由于环形（循环）的特性，对于尾部空间排满的情况下，在头部存入一个数据的效果和在尾部压入的效果是一样的。所以：

在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。——百度

我能说的也就这么多了，剩下的部分需要和大家一起再学学…
循环队列（度娘）
循环队列的实现

链队列

如名，链队列就是用链表实现的队列…

这个登西更难QAQ，所以…

传送门：
链队列知识
链队列的实现

尾声

终于码完了
队列好难a
图片来自网络，如有侵权，请立刻联系我（我改还不行嘛）QAQ
emm…应该没什么了
不对！

点赞！收藏！关注！

帮我宣传一下也不是不可以
好啦！

ヾ(•ω•`)o掰掰