河北大学程序设计训练营
[TOC]
stack
称为栈(或者堆栈)，堆栈是一个不容忽视的概念。堆栈都是一种数据项按序排列的数据结构，只能在一端( 称为栈顶(top) )对数据项进行插入和删除.
特点: 先进后出
头文件
增加元素
删除元素
返回栈中元素数目
返回栈顶元素
判断是否为空
练习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
stack<int> s;
int n = 10;
while(n--){
s.push(n);
}
while(s.size()!=0){
cout << s.top() << ",";
s.pop();
}
}
|
stack 括号匹配
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
| #include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
int T;
string str;
cin >> T;
while(T--){
stack<char> s;
cin >> str;
int flag = 1;
for(int i=0; i < str.length(); ++i){
if( str[i]=='(' || str[i]=='[' ||
str[i]=='{' ) {
s.push(str[i]);
} else {
if(!s.empty()){
if( (s.top()=='(' && str[i]==')') ||
(s.top()=='{' && str[i]=='}') ||
(s.top()=='[' && str[i]==']') ) {
s.pop();
} else{
flag = 0;
break;
}
} else{
flag = 0;
break;
}
}
}
if(flag==0){
cout << "No" << endl;
} else {
if(s.size()==0){
cout << "Yes" << endl;
} else{
cout << "No" << endl;
}
}
}
}
|
queue
队列是一种特殊的 线性表 ，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
特点: 先进先出
头文件
增加元素
删除
获取第一个元素
1
| front()：返回 queue 中第一个元素的引用
|
获取最后一个元素
1
| back()：返回 queue 中最后一个元素的引用
|
练习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<iostream>
#include<queue>
using namespace std;
int main(){
queue<int> q;
for(int i=0; i < 10 ; ++i){
q.push(i);
}
cout << "队列内元素数: " << q.size() << endl;
cout << "现在的头和尾: "<< q.front() << " " << q.back() << endl;
q.pop();
cout << "队列内元素数: " << q.size() << endl;
cout << "pop后的头和尾:"<< q.front() << " " << q.back() << endl;
}
|
例题:
队列queue Pro 银行业务队列简单模拟
这个题比较简单不再做讲解
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
| #include<iostream>
#include<queue>
using namespace std;
int main(){
queue<int> qA,qB;
int n,id,count1,count2;
cin >> n;
count1 = n;
count2 = n;
while(count1--){
cin >> id;
if(id%2==1) qA.push(id);
else qB.push(id);
}
while( count2 ){
if(!qA.empty()){
cout << qA.front();
qA.pop();
count2--;
if(n-count2!=n) cout << " ";
}
if(!qA.empty()){
cout << qA.front();
qA.pop();
count2--;
if(n-count2!=n) cout << " ";
}
if(!qB.empty()){
cout << qB.front();
qB.pop();
count2--;
if(n-count2!=n) cout << " ";
}
}
}
|
队列 queue 无聊的队列
因为1000ms的限时，故正常的反转操作都无法通过时间。
所以这里可以使用双端队列。
双端队列做法
https://blog.csdn.net/qq_45475271/article/details/107420369
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
deque<int> dq;
int main(){
int qwq,n,x,flag=0;
cin >> qwq;
while(qwq--){
scanf("%d",&n);
if(n==1){
scanf("%d",&x);
!flag ? dq.push_back(x):dq.push_front(x);
}else if(n==2){
if(!dq.empty()) !flag ? dq.pop_front():dq.pop_back();
}else{
flag = !flag;
}
cout << ((dq.empty())?-1:(dq.front()^dq.back())) << endl;
}
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
| #include <iostream>
using namespace std;
const int N = 8e5+10;
int q[N];
int head = N >> 1, tail = head - 1,flag = 1;
bool empty()
{
if(flag == 1 && tail >= head ) return 0;
if(flag == -1 && head >= tail ) return 0;
return 1;
}
int main()
{
int n;
cin >> n;
while(n --)
{
int choice;
scanf("%d",&choice);
if( choice == 1)
{
int x;
scanf("%d",&x);
tail = tail + flag;
q[tail] = x;
}
else if( choice == 2 && !empty() ) head += flag;
else {
swap(head,tail);
flag = -flag;
}
if(!empty()) printf("%d\n",q[head] ^ q[tail]);
else printf("-1\n");
}
}
|
