STL初步学习(queue,deque)

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;
}
上一篇:C++ 知识总结 P03:容器


下一篇:python-stack