当然也可以不看 ==> 阅读我的文章前请务必先阅读此文章！ 都是废话
目录
阅读文章须知
为了得到良好的阅读体验，请具备稍微完备的C++语法知识
在文章中出现类似[1]的标志，作者会在文章最后进行解释说明
注：只看蓝色加粗字加速阅读，红色加粗为误区或易错
引言
这篇文章接上篇文章C++vector浅显了解及运用继续讲解常用的数据结构，本篇讲解队列
队列(queue)
队列简介
队列是很常见的数据结构，顾名思义，就如日常排队，先进后出，因此push是从队尾进，pop是从队首出
队列的创建
queue<int> q;表示创建了一个名字为q的队列，queue中的元素类型是int，元素类型是可以更改的，比如下面这个
struct node
{
int x, y, z;
};
queue<node> a;
queue<pair<int, string>> b;以上代码中，queue a的元素类型是一个名为node的结构体，而queue b的元素类型是一个pair<int, string>类型（如果读者对于pair不熟悉的话，可以忽略此行）
在队列创建时，默认是空状态，即队列中没有任何元素
队列的操作
-
q.push(v) 表示将元素v插入队尾
-
q.pop() 表示将队首出队
-
q.front() 表示队首的元素 误区：q.front()只会返回队首元素而不会弹出队首！！！
-
q.back() 表示队尾的元素 同上
-
q.size() 表示队列的元素个数
-
q.empty() 返回一个bool型，false表示队列是空的，反之为true
易错： 队列在pop前 千万千万一定一定 要检查q.empty()是否为false，当年因为这个我调了1个小时，见代码
queue<int> q;
cout << q.empty() << endl;
q.pop();
cout << q.empty() << endl;你猜输出的是什么？第一行毫无疑问是1，但是第二行是0！
手写队列
如果你想实现队列的遍历，或者取出更改非头尾的值，那么我强烈建议你手写队列，这并不是什么难事。如果使用迭代器遍历队列非常的麻烦，并且依然很难修改制定的值，下面是一份手写队列的代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
struct que //将队列封装成一个结构体
{
int q[N + 5]; //队列主体
int head = 1, tail = 0; //头指针head，尾指针tail
/*
这里使用的head和tail可能与读者有所不同
head指向队首，tail指向队尾
因此当head == tail 时，队列中只有一个元素
而 head > tail 时，队列中就没有元素了
（见代码）
有些读者的tail可能会指向队列尾元素的下一位
因此push应该是q[tail++] = v
back应该是q[tail - 1]
empty应该是return head >= tail;
*/
void push(int v)
{
q[++tail] = v; //tail先向后移动一位，再将值放入tail的位置
return ;
}
void pop()
{
head++; //将head像右移动一位，变相的将原来的队首踢出去
return ;
}
int front()
{
return q[head]; //head指向的就是队首
}
int back()
{
return q[tail]; //同上
}
bool empty()
{
return head > tail; //见上方段注释
}
};
int main() //队列的遍历
{
//input
for(int i = q.head; i <= q.tail; i++)
{
int key = q.q[i];
//do something
}
//do something
}这看上去也非常简单，其实也不需要这么复杂，这些函数基本上都是一两行，建议直接放进代码中，调用函数也是需要时间成本的（我一同学就这么挂的，把函数展开就从TLE到AC了，当时他非常生气，把老师给吓了一跳），或者使用关键字inline，这里我们不细讲，下次我单独拉出来说
双端队列(deque)
与队列queue非常相似，因此这里很多内容一笔带过
双端队列简介
顾名思义，在队列的两个端点都可以进行操作
双端队列的创建
deque<int> q; //其他类型当然也可以双端队列的操作
- q.push_back(v) 将元素v加入队尾
- q.push_front(v) 将元素v加入队首
- q.pop_back() 弹出队尾
- q.pop_front() 弹出队首
- q.back() 返回队尾元素 误区：q.back()只会返回队首元素而不会弹出队首！！！
- q.front() 返回队首元素 同上
- q.empty() 同队列一样，返回一个bool类型，true表示队列空，反之为true
- q.size() 返回队列中元素的个数
手写双端队列（原理）
双端队列比队列难实现多了，细节非常的多，这里我只讲解原理，不贴代码了，因为我也不知道自己的细节处理是否正确。
先创建一个长度为n的数组，head和tail初始化
队尾加入元素很简单，tail+1就行了
但如果是队首加入元素，就麻烦了，按道理是head--，然后将元素插入q[head]，但是因为我喜欢下标从1开始，q[0]不是我想要的，或者说，我继续在队首加入元素，q[-1]更加不可能了，那么办法就是：从数组的最后开始往前加入
这里的n最好是数组极限大小，具体看题目要求，比如1e5+5
这里也不用担心tail和head会重合，因为你开的就是极限大小，比如题目要求数据范围是1e5，开1e5+5的数组怎么可能重合？
这里还比较好写，只需要写一个函数解决边界问题就行，比如
int real(int x)
{
if(x == 0) return N + 3;
if(x == N + 4) return 1;
}实现了下标从0变为N+3，从N+4变为1，之后每次指针改变都调用一下real函数
然后复杂的是判断empty，这个比较复杂，细节多，我不敢贴代码
写在最后
本文章讲解queue和deque的用法，还是写了好多...，此处回忆之前以为一篇文章就把vector，queue，stack讲完，真是做白日梦，本来想扩展优先队列和单调队列的，但是写到这里太累了，所以下一篇文章两个选择，一是讲解单调队列和优先队列，二是讲解stack，投票选吧（虽然不会多，但是感谢投票的人）
标签：deque,head,队列,队首,元素,C++,queue,tail From： https://blog.csdn.net/latiao520/article/details/140506900