C++STL栈、队列(Stack & Queue)
一、栈的概念
栈是一种特殊的线性表，其插入操作和删除操作限定在表的一端进行，这一段被称为“栈顶”（top），相对的另一端称为“栈底”（bottom）。插入操作一般称之为“压栈”（push），删除操作称之为“退栈”（pop）。栈的特点是“先进后出” (LIFO,First In Last Out) 。
二、栈的操作
1.定义
stack<typename> 栈的名字;
1
其中typename是想要的数据类型。
哦，对了，要使用栈，还需要加上一个头文件：（加了万能头文件就不需要了）
#include <stack>
1
如果要存int,可以这么写:
stack<int> s
1
2.栈的函数
假设已经定义一个栈，名字是s，那么就有这些函数：
s.push(x); //插入元素,x表示要插入的值,什么都行（但是类型必须和定义的相同）
s.pop(); //将栈顶弹出,无返回值
s.empty(); //判断是否是空栈
s.size(); //返回栈中有多少个元素
s.top(); //返回栈顶
s.swap(s2); //交换s和s2里面的值(s2需要和s是一个类型)
1
2
3
4
5
6
stack默认是空队列，如果不想怎么办?
假设已经定义了s1是stack<int>类型,那么可以这么写:
stack<int> s2(s1);
1
2
注意！stack没有重载=号！
举个栗子:（倒序输出）
#include <iostream>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
stack<int> s;
for(int i=1;i<=5;i++)
s.push(i);
while(!s.empty()){ //只要非空就循环
cout<<s.top()<<' ';
s.pop(); //这一步千万不要忘了
}
cout<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
来几道题
表达式括号匹配(stack)
分析:不是括号不需要入栈，如果是左括号就入栈，如果是右括号就看栈顶是不是左括号，如果是，就把左括号弹出，否则输出NO，结束程序。如果最后栈为空（所有左括号都被弹出了），输出YES，否则输出NO。
字符串匹配问题(strs)
分析:其实和上一道差不多，只不过多了几组数据和优先级，可以一组数据一组数据的做，再弄一个栈，来保存每一个的最大的优先级是多少，在入栈的时候判断是否可行，如果可行把这个栈加上这个的优先级，在出栈的同时把这个栈也删一个。
表达式求值
分析：还是先分离，因为符号肯定比数字少一个，所以循环数字就行了，每循环一次就把这个数入栈，如果符号没越界，那么就判断符号是什么，如果是“+”，把栈顶的两个数入栈，否则把这两个数乘起来在对10000取模，再把结果入栈。因为栈里面的数都是要加的，所以把这些数加起来（加的同时要对10000取模），再输出
后缀表达式
分析:可以遍历一遍，把数找出来入栈，如果是符号，从栈里弹出两个做运算（注意要下面的-上面的（下面的/上面的））
中缀表达式转后缀表达式
分析，用了这个方法：
先定义一个栈，用来存运算符，遍历一遍中缀表达式
如果这个字符是数字，则输出
否则，如果是运算符的话，
3.1. 如果栈为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈
3.2. 如果优先级比栈顶运算符的优先级高，也将运算符压入栈
3.3.将栈顶的运算符弹出并输出，再次转到分析的第4行与栈中新的栈顶运算符相比较。
否则（是括号）
4.1 如果是左括号，直接压入栈
4.2 如果是右括号，则依次弹出栈顶的运算符，并输出，直到遇到左括号为止，此时将左括号弹出（因为右括号没有入栈）。
还有一道题，也是表达式求值（有+ - * /），我是用了前面两个的结合加判错：（自己试试，不给代码）
中缀表达式值(expr)
--------------------------------------分割线--------------------------------------
验证栈序列
分析（一组数据）:可以把输入的出栈序列的值改为在入栈序列中的位置，然后遍历b数组，如果已入栈， 则看栈顶是否是它，如果不是，可以直接输出“No”，看下一组数据了。如果未入栈，那就把它前面的都入栈，最后输出“Yes”。
出栈序列
分析：我这里用一个计数器来记录出栈了几个，如果都出栈了，就结束循环
在大小为(c-栈的大小)的窗口里找最小的
如果栈非空
2.1 如果这个数比栈顶元素还小， 把前面的都入栈，当前元素输出
2.2 否则，输出栈顶元素并出栈
否则，把前面的都入栈，当前元素输出
移动到下一个窗口
自己尝试做一做吧~
代码
表达式括号匹配(stack)
#include <iostream>
#include <conio.h>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
char c;
stack<char> s;
do{
cin>>c;
if(c=='(')
s.push(c); //压栈
else if(c==')'){
if(!s.empty()&&s.top()=='(')
s.pop(); //把左括号弹出
else{
cout<<"NO\n"; //没有左括号
return 0;
}
}
}while(c!='@');
if(s.empty()) //如果左括号都弹出了
cout<<"YES\n";
else
cout<<"NO\n";
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
字符串匹配问题(strs)
#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <string>
#include <stack>
using namespace std;
int priority(char c) { //返回c的优先级
if(c=='<'||c=='>')
return 1;
if(c=='('||c==')')
return 2;
if(c=='['||c==']')
return 3;
if(c=='{'||c=='}')
return 4;
return -1;
}
bool is_left(char c) { //判断是否是左括号
return c=='('||c=='['||c=='{'||c=='<';
}
bool is_right(char c) {
return c==')'||c==']'||c=='}'||c=='>';
}
//两个括号是否匹配
bool match(char a,char b) {
if(!is_left(a)) //如果左边的不是左括号
return false;
if(a=='(')
return b==')';
if(a=='[')
return b==']';
if(a=='{')
return b=='}';
if(a=='<')
return b=='>';
}
//一个一个判断
bool func(stack<char>& s,char c,stack<int>& prioritys) {
if(is_left(c)) { //如果是左括号
if(prioritys.top()>=priority(c)) {
s.push(c);
prioritys.push(priority(c));
} else {
return false; //优先级太高
}
} else if(is_right(c)) { //如果是右边
if(!s.empty()&&match(s.top(),c)) { //如果匹配
s.pop();
if(!prioritys.empty()) //非空
prioritys.pop();
} else
return false;
}
return true;
}
bool check(string str) {
stack<char> s;
stack<int> prioritys; //优先级
prioritys.push(0x7fffffff); //很大很大的数
for(int i=0; i<str.size(); i++) {
char c=str[i];
if(!func(s,c,prioritys)) {
return false;
}
}
return s.empty();
}
int main(int argc,char* argv[],char** env) {
int n;
cin>>n;
getchar(); //以防把n后面的换行当成第一个字符
while(n--) {
string str;
getline(cin,str); //保险，其实完全可以用cin>>str;
if(check(str))
cout<<"YES\n";
else
cout<<"NO\n";
}
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
表达式求值
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) {
return c>='0'&&c<='9';
}
string num[100003],operators; //数字和运算符
int calc(string str) { //分离
int n=0,len=str.size();
for(int i=0; i<len; ++i) {
if(is_digit(str[i])) {
num[n]+=str[i];
} else {
n++;
operators+=str[i];
}
}
return ++n; //因为什么，所以要加1?
}
int main(int argc,char* argv[],char** env) {
string str;
getline(cin,str);
int n=calc(str);
stack<int> s;
stack<char> op;
for(int i=0; i<n; i++) {
bool flag=false;
//下面用C++11的函数来把num[i]转换成int，用的要在Dev-C++
//编译选项->代码生成/优化->代码生成->语言标准 设置位ISO C++11或GNU C++11
int x=stoi(num[i]);
s.push(x%10000);
char c;
if(i+1<n)
c=operators.at(i); //或operators[i]
else
flag=true; //最后一个
if(op.empty()||op.top()=='+') {
op.push(c);
} else { //op.top=='*'
s.pop();
int y=s.top();
s.pop();
s.push(x*y%10000);
op.push(c); //别忘了把当前的加进去
}
if(flag) { //最后一个要在这里判断，为什么自己想想
int sum=0;
while(!s.empty()) {
sum+=s.top()%10000; //其实对不对10000取模都一样，因为反正push的时候
//都对10000取模了
sum%=10000; //这里非常重要，我就是没写这个才过不去，如果不写这个的话下面的
//cout<<sum<<endl;就得改成cout<<sum%10000<<endl;
s.pop();
}
cout<<sum<<endl;
return 0; //加不加随便，反正都是最后一轮
}
}
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
后缀表达式
#include <iostream>
#include <conio.h>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) { //判断是否为数字，也可以用algorithm中的
return c>='0'&&c<='9';
}
int calc(string input) {
int x=0;
stack<int> s;
for(int i=0; i<input.size(); i++) {
char c=input[i];
if(is_digit(c)) { //如果是数字
x=x*10+c-'0'; //当前的数
} else {
if(c=='@') //结束符
break;
if(c=='.') //分隔符
s.push(x);
x=0; //清0
if(c=='+'||c=='-'||c=='*'||c=='/') { //是运算符
int b=s.top(); //注意要先取b，因为下面要a+b或a-b或a*b或a/b
s.pop(); //取一个弹出一个
int a=s.top();
s.pop(); //这一步很重要
switch(c) {
case '+': {
s.push(a+b);
break;
}
case '-': {
s.push(a-b);
break;
}
case '*': {
s.push(a*b);
break;
}
case '/': {
s.push(a/b);
break;
}
default: {
break;
}
}
}
}
}
return s.top(); //栈里面应该只剩结果了
}
int main(int argc,char* argv[],char** env) {
string s;
getline(cin,s); //保险
cout<<calc(s)<<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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
中缀表达式转后缀表达式
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool is_digit(char c) {
return c>='0'&&c<='9';
}
int priority(char c) { //优先级
if(c=='+'||c=='-')
return 1;
if(c=='*'||c=='/')
return 2;
}
string change(string str){ //把中缀表达式转成后缀表达式
string ans,x;
stack<char> s;
for(int i=0; i<str.size(); i++) {
char c=str[i];
if(is_digit(c)) {
x+=c;
if(i+1==str.size()||!is_digit(str[i+1])){
ans+=x; //将结果加这个数
ans+=' '; //为了区分是哪个数
x=""; //清空数
}
} else if(c=='+'||c=='-'||c=='*'||c=='/') {
while(1) {
if(s.empty()||s.top()=='(') {
s.push(c);
break;
} else if(priority(c)>priority(s.top())) {
s.push(c);
break;
} else {
char t=s.top();
s.pop();
ans+=t;
}
}
} else {
if(c=='(') {
s.push(c);
} else { //右括号
while(s.top()!='(') {
char t=s.top();
s.pop();
ans+=t;
}
s.pop(); //将左括号弹出，不要忘了
}
}
}
while(!s.empty()){
ans+=s.top();
s.pop();
}
return ans;
}
int main(int argc,char* argv[],char** env) {
string str;
getline(cin,str); //保险
cout<<change(str)<<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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
验证栈序列
#include <iostream>
#include <stack>
#include <map>
using namespace std;
bool check(int a[],int b[],bool is_pushed[],int n) {
stack<int> s;
for(int i=1; i<=n; i++) { //遍历b数组
if(is_pushed[b[i]]) { //b[i]已入栈
if(!s.empty()&&s.top()!=a[b[i]])
return false;
s.pop(); //如果等于，将这个数弹出
} else { //b[i]未入栈
//把a[b[i]]的前面的元素入栈.
int j=b[i],k;
is_pushed[j]=true;
for(k=j-1;k>0;k--) //找到没入栈的开头-1
if(is_pushed[k])
break;
for(int l=k+1; l<j; l++) { //把前面的都入栈
s.push(a[l]);
is_pushed[l]=true;
}
}
}
return true;
}
int main(int argc,char* argv[],char** env) {
int n,t;
cin>>t;
while(t--) {
map<int,int> mp; //mp[i]表示i在a数组中的下标
cin>>n;
int a[n+2],b[n+2],x; //a数组记录入栈序列,b数组存出栈序列的数在a[]中的下标
bool is_pushed[n+2]; //is_pushed[i]记录a[i]有没有入栈
for(int i=1; i<=n; i++) {
cin>>a[i];
//初始化
is_pushed[i]=0;
mp[a[i]]=i;
}
for(int i=1; i<=n; i++){
cin>>x;
b[i]=mp[x];
}
if(check(a,b,is_pushed,n)) //这里传is_pushed因为完全可以在输入的时候初始化，不需要在里面初始化
cout<<"Yes\n";
else
cout<<"No\n";
}
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
出栈序列
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(int argc,char* argv[],char** env){
stack<int> s; //栈里存在a数组中的下标
int x,n,c,cnt=0;
cin>>n>>c;
int a[n+2],begin=0,end=c-1; //窗口的开头和结尾
for(int i=0;i<n;i++)
cin>>a[i];
while(cnt<n){
//找a数组中最小
int MinIndex=min(begin,n-1);
for(int i=min(begin,n-1);i<=end&&i<n;i++){
if(a[i]<a[MinIndex])
MinIndex=i;
}
//判断
if(!s.empty()){ //栈非空
if(a[s.top()]<a[MinIndex]){ //如果栈顶元素比这个数还小
cout<<a[s.top()]<<' '; //出栈
cnt++;
a[s.top()]=0x7fffffff; //记录已经出栈了
end++;
s.pop();
} else {
//把前面的都入栈
for(int i=begin;i<MinIndex;i++){
if(a[i]<0x7fffffff){
s.push(i);
begin=i;
}
}
if(begin==MinIndex)
begin++;
else
begin+=2;
cout<<a[MinIndex]<<' '; //输出
cnt++;
a[MinIndex]=0x7fffffff;
end++;
}
} else { //栈为空
//把前面的都入栈
for(int i=begin;i<MinIndex;i++){
if(a[i]<0x7fffffff){
s.push(i);
begin=i;
}
}
if(begin==MinIndex)
begin++;
else
begin+=2;
cout<<a[MinIndex]<<' '; //也是输出
cnt++;
a[MinIndex]=0x7fffffff;
end++;
}
}
return 0;
}
————————————————
版权声明：本文为CSDN博主「2345浏览器」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/orangebench11/article/details/104618433
