C++ STL之queue详解_c++ stl queue

返回主目录

3 queue

3.1 介绍

队列是一种先进先出的数据结构。

//头文件
#include<queue>
//定义初始化
queue<int> q;
1
2
3
4

3.2 方法函数

3.3 队列模拟

使用q[]数组模拟队列

hh表示队首元素的下标，初始值为0

tt表示队尾元素的下标，初始值为-1，表示刚开始队列为空

一般来说单调栈和单调队列写法均可使用额外变量 tt 或 hh 来进行模拟

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int q[N];

int main() {
	int hh = 0,tt = -1;
//	入队 
	q[++tt] = 1;
	q[++tt] = 2; 
//	将所有元素出队 
	while(hh <= tt) {
		int t = q[hh++];
		printf("%d ",t);
	}
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.4 队列模拟例题

题目链接： https://atcoder.jp/contests/abc247/tasks/abc247_d

#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
using pii = pair<int, int>;
const int N = 250005, mod = 998244353;

int q[N], num[N];

void solve() {
	int qq, hh = 0, tt = -1;
	cin >> qq;
	while(qq--) {
		int op;
		cin >> op;
		int x, c;
		if(op == 1) {
			cin >> x >> c;
			q[++tt] = c;
			num[tt] = x;
		} else {
			cin >> c;
			ll res = 0;
			while(c) {
				if(q[hh] > c) {
					q[hh] -= c;
					res += 1ll * c * num[hh];
					break;
				} else {
					res += 1ll * q[hh] * num[hh];
					c -= q[hh++];
				}
			}
			cout << res << "\n";
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	// cin >> t;
	t = 1;
	while(t--)
		solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

如要获取所有内容的PDF文件，请在公众号【行码棋】回复【STL】获取，非常抱歉了。
Update：2023-12-11更新PDF文件