Loading... # 栈的基础介绍 栈只是能再某一端插入和删除的特殊线性表。 用桶堆积物品,先堆进来的压在底下,随后一件一件往上堆取走时,只能从上面一件一件取。堆和取都在顶部进行,底部一般是不动的。 栈就是一种类似桶堆积物品的数据结构,进行删除和插入的一端称栈顶,另一端称栈底。插入一般称为进站(PUSH),删除则称为退栈(POP)。栈也称为后进先出表(LIFO表)。 一个栈可以用定长为n的数组s来表示,用一个栈指针top指向栈顶。若top=0,表示栈空,top=n时栈满。进栈时top加1,退栈时top减1。当top<0时为下溢。栈指针在运算中永远指向栈顶。 ![](https://blog.fivk.cn/usr/uploads/2021/07/2645896254.png) **1.进栈(PUSH)算法** 1. 若top>=n时,则会给出溢出信息,作出错误处理(进栈前首先检查栈是否已满,满则溢出;不满则操作2); 2. top++(栈指针加1,指向进栈地址); 3. s[top]=x,结束(x为新进栈的元素)。 **2.退栈(pop)算法** 1. 若top<=0,则给出下溢信息,作出错误处理(退栈前先检查是否已为空栈,空则下溢;不空则操作2); 2. x=s[top],(退栈后的元素赋给x); 3. top--,结束(栈指针减1,指向栈顶)。 **进栈、出栈的C++实现过程程序:** ```cpp #define n 100 void push(int s[],int *top,int *x) //入栈 { if(*top==n) printf("overflow\n"); else { (*top)++; s[*top]=*x; } } void pop(int s[],int *y,int *top) //出栈 { if(*top==0) printf("underflow\n"); else { *y=s[*top]; (*top)--; } } ``` 对于出栈运算中的“下溢”,程序中仅给出了一个标志信息,而在实际应用中,下溢可用来做为控制程序转移的判断标志,是十分有用的。对于入栈运算中的“上溢”,则是一种致命的错误,将使程序无法继续运行,所以要设法避免。 **堆栈的数组模拟** 十进制数n和其他d进制数的转换是实现计算的基本问题,解决方法很多,下面给出一种算法原理: <div class="tip inlineBlock success"> n=(n/d)*d+n%d (其中/为整除运算,%为求余运算)。 </div> 例如:$(1348)_{10}=(2504)_{8}$运算过程如下: | n | n/8 | n%8 | | ------ | ----- | ----- | | 1348 | 168 | 4 | | 168 | 21 | 0 | | 21 | 2 | 5 | | 2 | 0 | 2 | **数制转化参考程序** ```cpp #include<cstdlib> #include<iostream> using namespace std; #define SIZE 100 int a[SIZE+1],n,d,i=0,j; int main() { cout<<"Please enter a number(N) base 10:"; cin>>n; cout<<"Please enter a number(d):"; cin>>d; do{ a[++i]=n%d; n/=d; }while(n!=0); for(j=i;j>=1;j--) cout<<a[j]; return 0; } ``` ![运行过程](https://blog.fivk.cn/usr/uploads/2021/07/1632824774.png) # 经典例题 ### 例1.1 括号的匹配(表达式的合法性检查) 【问题描述】 假设一个表达式由英文字母(小写)、运算符(+、一、* 、/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES";否则返回“NO”。假设表达式长度小于255,左圆括号少于20个。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-af592f36d6670a9bec5d646141074ecf45" aria-expanded="true"><div class="accordion-toggle"><span style="">【算法分析】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-af592f36d6670a9bec5d646141074ecf45" class="collapse collapse-content"><p></p> 假设输入的字符串存储在c中(char c[256])。我们可以定义一个栈: char s[ maxn+1]; int top; 用它来存放表达式中从左往右的左圆括号(maxn=20)。 算法的思路为:顺序(从左往右)扫描表达式的每个字符c[i,若是“(”,则让它进栈;若遇到的是“)”,则让栈顶元素出栈;当栈发生下溢或当表达式处理完毕而栈非空时,都表示不匹配,返回“NO”;否则表示匹配,返回“YES”。 <p></p></div></div></div> <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-142933cc9d7a93d5ec60734cc9ea7b7c76" aria-expanded="true"><div class="accordion-toggle"><span style="">【参考程序】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-142933cc9d7a93d5ec60734cc9ea7b7c76" class="collapse collapse-content"><p></p> ```cpp #include<cstdio> #include<cstdlib> #define MAXN 20 using namespace std; char c[256]; bool judge(char c[]) { int top = 0, i=1; while(c[i]!='@') { if(c[i]=='(') top++; if(c[i]==')') { if(top>0) top--; else return 0; } i++; } if(top!=0) return 0; //检查栈是否为空。不空则说明有未匹配的括号 else return 1; } int main() { gets(c); if(judge(c)) printf("YES"); else printf("NO"); system("pause"); return 0; } ``` <p></p></div></div></div> ### 例1.2 编程求一个后缀表达式的值 【问题描述】 从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(+)、减(一)乘( * )、除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标志。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-9553a3a7e9242c21e32aeb7fe283766e12" aria-expanded="true"><div class="accordion-toggle"><span style="">【算法分析】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-9553a3a7e9242c21e32aeb7fe283766e12" class="collapse collapse-content"><p></p> 后缀表达式的处理过程很简单,过程如下:扫描后缀表达式,凡遇操作数则将之压进堆栈,遇运算符则从堆栈中弹出两个操作数进行该运算,将运算结果压栈,然后继续扫描,直到后缀表达式被扫描完毕为止,此时栈底元素即为该后缀表达式的值。 比如,16-9 *(4+3)转换成后缀表达式为:16⚪9⚪4⚪3⚪+ * -,在字符数组A中的形式为: ![](https://blog.fivk.cn/usr/uploads/2021/07/2004926767.png) 栈中的变化情况: ![](https://blog.fivk.cn/usr/uploads/2021/07/2734625845.png) 运行结果:-47 <p></p></div></div></div> <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-f89c572943813fbb2976230dac72133113" aria-expanded="true"><div class="accordion-toggle"><span style="">【参考程序】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-f89c572943813fbb2976230dac72133113" class="collapse collapse-content"><p></p> ```in 16 9 4 3 +*-@ ``` ```cout -47 ``` 书上参考代码: ```cpp #include<cstdio> #include<cstdlib> #include<string> #include<cstring> using namespace std; int stack[101]; char s[256]; int comp(char s[]) { int i=0,top=0,x,y; while(i<=strlen(s)-2) { switch(s[i]) { case '+':stack[--top] += stack[top+1];break; case '-':stack[--top] -= stack[top+1];break; case '*':stack[--top] *= stack[top+1];break; case '/':stack[--top] /= stack[top+1];break; default: x=0; while(s[i]!=' ') x=x*10+s[i++]-'0'; stack[++top]=x; break; } i++; } return stack[top]; } int main() { printf("input a string(@_over):"); gets(s); printf("result=%d\n",comp(s)); system("pause"); return 0; } ``` 使用stack容器: 最后不用输入@ ```cpp #include<iostream> #include<stack> #include<string> using namespace std; stack<long long> s; string str; int main() { getline(cin,str); for(int i=0;i<str.length();i++) { if(str[i]=='+') { long long temp=s.top(); s.pop(); s.top()+=temp; }else if(str[i]=='-') { long long temp=s.top(); s.pop(); s.top()-=temp; }else if(str[i]=='*') { long long temp=s.top(); s.pop(); s.top()*=temp; }else if(str[i]=='/') { long long temp=s.top(); s.pop(); s.top()/=temp; }else if(str[i]>='0'&&str[i]<='9') { long long x=0; while(str[i]!=' ') x=x*10+str[i++]-'0'; s.push(x); } } cout<<s.top()<<endl; system("pause"); return 0; } ``` <p></p></div></div></div> ### 例1.3车厢调度 【问题描述】 有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有n节(n<=1000),分别按照顺序编号为1,2,3,…,n。假定在进人车站前,每节车厢之间都不是连着的,并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C,它就不能再回到A方向的铁轨上了,并且一旦当它进入B方向的铁轨,它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以al,a2,…, an 的顺序从B方向驶出,请你来判断能否得到指定的车厢顺序。 ![](https://blog.fivk.cn/usr/uploads/2021/07/3038377298.png) 【输入】 输入文件的第一行为一个整数n,其中n< =1000,表示有n节车厢,第二行为n个数字,表示指定的车厢顺序。 【输出】 如果可以得到指定的车厢顺序,则输出一个字符串”YES",否则输出”NO”(注意要大写,不包含引号)。 <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-3552c466f4412977fa223e1bbdc6ade756" aria-expanded="true"><div class="accordion-toggle"><span style="">【算法分析】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-3552c466f4412977fa223e1bbdc6ade756" class="collapse collapse-content"><p></p> 该题就是前面思考题的一部分。车站C相当于一个栈。我们用模拟法来做,假设我们已经处理了前i-1节从B方向驶出的车厢,我们现在要让ai驶出。若ai不在车站C中,我们就让若干车厢从A方向驶入车站C,直到 ai驶入,再将它从B方向驶出;若ai在车站C中,如果它是车站C中停在最前面的,则将它从B方向驶出,否则原问题无解。 如样例中,出栈序列是**35421**,模拟过程如下: 1. 一开始栈为空; 2. 由于3不在栈中,就需要把1,2,3依次进栈,再出栈,这样符合出栈序列第一个数是3,当前栈为{1,2}; 3. 第2个出栈的是5,5不在栈中,就要把4,5压栈,再出栈就可以得到5,此时栈为{1,2,4}; 4. 第3个出栈的是4,正好是栈顶元素,直接出栈,栈变为{1,2}; 5. ⑤、第4个出栈的是2,正好是栈顶元素,直接出栈,栈变为{2}; 6. 第5个出栈的是1,正好是栈顶元素,直接出栈,栈变为{得}。 在模拟过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况,所以该方案可行。 <p></p></div></div></div> <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-0c9a31b79f54368f4fa73f9614d2a6f425" aria-expanded="true"><div class="accordion-toggle"><span style="">【参考程序】</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-0c9a31b79f54368f4fa73f9614d2a6f425" class="collapse collapse-content"><p></p> ```in 3 5 4 2 1 ``` ```out YES ``` 书上参考代码: ```cpp #include<iostream> #include<algorithm> using namespace std; const int N = 1010; int stack[N],a[N]; int top,n; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; top=0; for(int i=1,cur=1;i<=n;i++) { while(cur<=a[i]) stack[++top]=cur++; if(stack[top]==a[i]) top--; else{ cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; system("pause"); return 0; } ``` 使用stack容器: 换汤不换药 ```cpp #include<iostream> #include<algorithm> #include<stack> using namespace std; const int N = 1010; int a[N]; stack<int> s; int top,n; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; top=0; for(int i=1,cur=1;i<=n;i++) { while(cur<=a[i]) s.push(cur++); if(s.top()==a[i]) s.pop(); else{ cout<<"NO"<<endl; return 0; } } cout<<"YES"<<endl; system("pause"); return 0; } ``` <p></p></div></div></div> 最后修改:2021 年 09 月 12 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏