STL应用 —— deque

STL应用 —— deque

deque是一个双端队列，可以在两端进出队，支持数组表示法和随机访问，经常在序列两端操作时应用。使用deque时，需要引入头文件#include。

【双端队列的成员函数】

• push_front(x)/push_back(x)：x 从队头或队尾入队。
• pop_front()/pop_back()：从队头或队尾出队。
• front()/back()：返回队头或队尾元素。
• size()：返回队中的元素个数。
• empty()：判断队空，若为空，则返回true。
• clear()：清空双端队列。

【举个例子】

HDU No.6375 度度熊学队列

官方题目地址

【题目描述】

度度熊正在学习双端队列，它对翻转和合并产生了很大的兴趣。初始时有N 个空的双端队列（编号为1～N），度度熊的Q 次操作如下：

① 1 u w val：在编号为u 的队列中加入一个权值为val的元素（w=0表示加在最前面，w =1表示加在最后面）。

② 2 u w ：询问编号为u 的队列中的某个元素并删除它（w =0表示询问并操作最前面的元素，w =1表示询问并操作最后面的元素）

③ 3 u v w ：把编号为v 的队列“接在”编号为u 的队列的最后面。w =0表示顺序接（将队列v 的开头和队列u 的结尾连在一起，将队列v 的结尾作为新队列的结尾），w =1表示逆序接（先将队列v 翻转，再按顺序接在队列u 的后面）。而且在该操作完成后，队列v 被清空。

【输入输出】

输入： 有多组数据。对于每一组数据，第1行都包含两个整数N 和Q 。接下来有Q 行，每行3～4个数，意义如上。N ≤1.5×10^5 ；Q≤4×10^5 ；1≤u ,v ≤N ；0≤w ≤1；1≤val≤10^5 ；所有数据里Q 的和都不超过5×10^5 。

输出： 对于每组数据的每一个操作②，都输出一行表示答案。如果操作②的队列是空的，则输出−1且不执行删除操作。

样例

【算法设计】

典型的一个双端队列，使用deque进行解决。

1. 定义一个deque数组d[ ]
2. 判断分别执行3种操作，第② 种操作需要进行输出操作。
3. 第3种情况，由于deque不支持翻转， 可以使用反向迭代器进行控制。

【算法实现】

#include
#include

using namespace std;

const int maxn = 15e4 + 10;

int n , m;

deque<int> d[maxn];

//读入过大，进行读入优化
void read(int &x){
	char ch = getchar();
	x = 0;
	
	for(;ch < '0' || ch > '9' ; ch = getchar());
	
	for(;ch >= '0' && ch <= '9' ; ch = getchar()){
		x = x * 10 + ch - '0';
	}
}

int main(){
	
	while(~scanf("%d%d",&n , &m)){
		
		//初始化n个双端队列，编码为1 - n 
		
		for(int i = 1; i <= n ; i++){
			
			d[i].clear();
			
		}
		
		int k , u , v , w;
		
		while(m --){
			
			read(k);
			switch(k){
				case 1:
					read(u);
					read(w);
					read(v);
					if(w == 0){
						d[u].push_front(v);
					}
					else{
						d[u].push_back(v);
					}
					break;
				case 2:
					read(u);
					read(w);
					if(d[u].empty()){
						printf("-1\n");
					}
					else{
						if(w == 0){
							printf("%d\n",d[u].front());
							d[u].pop_front();
						}
						else{
							printf("%d\n",d[u].back());
							d[u].pop_back();
						}
					}
					break;
				case 3:
					read(u);
					read(v);
					read(w);
					if(w){
						d[u].insert(d[u].end() , d[v].rbegin(), d[v].rend());
					}
					else{
						d[u].insert(d[u].end() , d[v].begin() , d[v].end());
					}
					d[v].clear();
					break;
			}
			
		}		
	}
	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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87