4.queue

queue就是队列，平时用得非常多。栈的操作是只能是先进先出，与栈不同，是先进后出，与之后的deque也有区别。个人感觉手写队列有点麻烦，有什么head和tail什么的，所以说 STL大法好！！！

queue的定义

#include<queue>
using namespace std;
queue<typename> a;
queue<int> a;
queue<string> a;
queue<node> a;

queue这个东西没有遍历，主要讲函数

①push（），push（x）将 x 入队，时间复杂度为O（1），

②front（），back（），分别为访问队首和队尾元素，时间复杂度为O（1）

③pop（），将队首元素出队，时间复杂度为O（1）

④empty（），检测队列是否为空，空则返回true，非空则返回false，时间复杂度为O（1）

⑤size（），返回队列中元素个数，时间复杂度为O（1）

时间复杂度全为O（1），舒服啊

因为queue的主要运用感觉不会涉及到很多题目（是我孤陋寡闻），主要是在广度优先搜索时，自己手写队列的话，可能会导致一些错误，用STL的话可以提高一些程序正确率吧。但是在使用时一定要注意，关于queue，包括其他一些stack之类的，使用前一定要注意empty的判断

至于一些好的题目，我也没找到什么。。就做一做广搜的题吧

5.deque

deque为双端队列，与queue不同的是，deque可以任意地调用和弹出队首和队尾元素，queue只能弹出队首元素

deque的定义

#include<deque>
using namespace std;
deque<typename> a;
deque<int> a;
deque<string> a;
deque<node> a;

同queue一样，这玩意没有遍历（函数的话，我自己不大清楚，应该时间复杂度也都是O（1）吧）

①front（），返回队首元素；back（），返回队尾元素

②pop_front（），删除队首元素；pop_back（），删除队尾元素

③push_front（x），将元素x加入到队首；push_back（x），将元素x加入到队尾

关于deque的应用，最经典的就是对于单调队列。单调队列中的元素为递增和递减，并且队列中的元素与序列中的元素顺序应该一致，并且能从队首和队尾加入（删除）元素

经典例题

P1886 滑动窗口，单调队列的模板题，如果实力足够的大佬 应该除了我都行 可以尝试用线段树，树状数组，ST表之类的过这一道题

以最小值为例。从1开始枚举到n，如果当前的元素满足a[ i ] <= a[ q.back（）] （注意，优先队列中存储的是下标，而不是对应的元素的值），那么我们将优先队列中的队尾元素弹出，这样做是为了维护这个优先队列事从小到大的，然后将当前的 i 推入队列中

这样只会，当 i >= k 时，就开始输出答案了。在输出之前，先判断当前的队首元素是否在 k 这个长度范围内，如果不是在，记得弹出（注意判空），这样之后，输出队首元素就可以了。至于最大值的情况，把上面的比较换为 > 就可以了

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
deque<int> q;
int main(){
	scanf("%d%d",&n,&k);
	for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(register int i=1;i<=n;i++){
		while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();
		q.push_back(i);
		if(i>=k){
			while(!q.empty()&&q.front()<=i-k) q.pop_front();
			printf("%d ",a[q.front()]);
		}
	}
	while(!q.empty()) q.pop_back();
	puts("");
	for(register int i=1;i<=n;i++){
		while(!q.empty()&&a[q.back()]<a[i]) q.pop_back();
		q.push_back(i);
		if(i>=k){
			while(!q.empty()&&q.front()<=i-k) q.pop_front();
			printf("%d ",a[q.front()]);
		}
	}
	return 0;
}

P1714 切蛋糕，一道单调队列的稍微多动点脑筋的题。因为连续吃 k 个蛋糕，我直接打了一个前缀和+暴力枚举看看能得多少分，用前缀和是为了统计区间的值，也方便计算区间内的幸运值。还是不错的，有40分（吸氧也救不了我），继续想单调队列

其实同之前的滑动窗口一样，因为我们要连续吃 k 块蛋糕，求区间的最大值，前缀和还是需要用到的，我们只需要将上面滑动窗口中的比较元素改为比较前缀和就行了，代码和上面基本相同

#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum[550005];
deque<int> q;
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		sum[i]=sum[i-1]+x;
	}
	int ans=-99999999;
	for(register int i=1;i<=n;i++){
		while(!q.empty()&&sum[q.back()]>=sum[i]) q.pop_back();
		q.push_back(i);
		while(!q.empty()&&q.front()<=i-m) q.pop_front();
		ans=max(ans,sum[i]-sum[q.front()]);
	}
	cout<<ans;
	return 0;
}