有关栈的练习
赞
踩
栈练习1
给定一个栈（初始为空，元素类型为整数，且小于等于 109），只有两个操作：入栈和出栈。先给出这些操作，请输出最终栈的栈顶元素。
操作解释：
1 表示将一个数据元素入栈；
2 表示出栈。保证出栈的时候栈里数据不为空。
输入
第一行，一个数字 N，表示操作个数。1≤N≤10^5
其后 N 行，表示 N 个操作（如果是入栈则后面还会有一个入栈元素）。
具体见样例（输入保证栈空时不会出栈）。
输出
最终栈顶元素，若最终栈空，输出”impossible!”（不含引号）。
样例输入
- 3
- 1 2
- 1 9
- 2
样例输出
2代码：
- #include<bits/stdc++.h>
- using namespace std;
- stack<int>a;
- int n,x,y;
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++){
- cin>>x>>y;
- if(x==2){
- a.pop();
- }
- else if(x==1){
- a.push(y);
- }
- }
- if(!a.empty())cout<<a.top();
- else cout<<"impossible!";
- return 0;
- }
栈练习2
此题与相比栈练习1改了 2 处：1、加强了数据，2、不保证栈空时不会出栈。
给定一个栈（初始为空，元素类型为整数，且小于等于 109），只有两个操作：入栈和出栈。先给出这些操作，请输出最终栈的栈顶元素。
操作解释：
1 表示将一个元素入栈；
2 表示出栈。出栈的时候栈可能为空。
输入
第一行，一个数字 N，表示操作个数。1≤N≤105。
其后 N 行，表示 N 个操作（如果是入栈则后面还会有一个入栈元素）。
具体见样例（输入不保证栈空时不会出栈）。
输出
最终栈顶元素。若最终栈空，或每次栈空时有出栈操作，输出”impossible!”（不含引号）。
样例输入
- 3
- 1 2
- 2
- 2
样例输出
- impossible!
- impossible!
代码：
- #include<bits/stdc++.h>
- using namespace std;
- long long n,a,b;
- stack<long long>s;
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a;
- if(a==1)
- {
- cin>>b;
- s.push(b);
- }
- if(a==2)
- {
- if(!s.empty())s.pop();
- else cout<<"impossible!"<<endl;
- }
- }
- if(!s.empty())cout<<s.top();
- else cout<<"impossible!";
- return 0;
- }
栈练习3
比起栈练习1，本题加了另外一个操作，访问栈顶元素（编号 3，保证访问栈顶元素时或出栈时栈不为空），现在给出这 N 次操作，输出结果。
输入
第一行，一个数字 N，表示操作个数。1≤N≤105。
其后 N 行，表示 N 个操作：
1 入栈；入栈元素大小不会超过 109。
2 出栈；
3 访问栈顶。
输出
K行（K为中间询问的次数）每次的结果
样例输入
- 6
- 1 7
- 3
- 2
- 1 9
- 1 7
- 3
样例输出
- 7
- 7
代码：
- #include<bits/stdc++.h>
- using namespace std;
- long long n,a,b;
- stack<long long>s;
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a;
- if(a==1)
- {
- cin>>b;
- s.push(b);
- }
- if(a==2)
- s.pop();
- if(a==3)
- cout<<s.top()<<endl;
- }
- return 0;
- }
栈练习4
比起栈练习3，本题不保证访问栈顶元素时或出栈时栈不为空，现在给出这 N 此操作，输出结果。
输入
第一行，一个数字 N，表示操作个数。1≤N≤105。
其后 N 行，表示 N 个操作：
1 入栈；入栈元素大小不会超过 109。
2 出栈；
3 访问栈顶。
输出
若干行每次的结果。
对于2操作。如果栈为空，每次操作输出 impossible!。
对于3操作。如果栈为空，每次操作输出 impossible!。如果栈不为空，输出对应的栈顶数据
样例输入
- 6
- 1 7
- 3
- 2
- 2
- 1 9
- 3
样例输出
- 7
- impossible!
- 9
代码：
- #include<bits/stdc++.h>
- using namespace std;
- long long n,a,b;
- stack<long long>s;
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a;
- if(a==1)
- {
- cin>>b;
- s.push(b);
- }
- if(a==2)
- {
- if(!s.empty())s.pop();
- else cout<<"impossible!"<<endl;
- }
- if(a==3)
- {
- if(!s.empty())cout<<s.top()<<endl;
- else cout<<"impossible!"<<endl;
- }
- }
- return 0;
- }
洗盘子
晨晨和涵涵将联手洗掉 N (1<= N <= 10,000) 个脏盘子。晨晨洗，涵涵来擦干它们。每个盘子有一个指 定的编号，范围 1..N。开始，所有盘子按顺序排列在栈中（只能竖着叠放盘子的盒子）， 1 号盘子在顶端， N 号盘子在底端。
晨晨会先洗一些盘子，然后放在洗过的盘子栈里（这样与原来的顺序刚好颠倒）。然后，或者她洗别 的盘子，或者涵涵擦干她已经洗好的部分或全部盘子，放在擦干的盘子栈里。这样直到所有盘子洗完擦干 后放置的顺序是什么？
输入
第一行：一个整数 N，表示盘子的数量。
接下来若干行：每一行两个整数，第一个整数为 1 表示洗盘子，为 2 表示擦盘子，第二个整数表示盘子数量
输出
共 N 行：擦干后盘子从顶端到底端的顺序
样例输入
- 5
- 1 3
- 2 2
- 1 2
- 2 3
样例输出
- 1
- 4
- 5
- 2
- 3
代码：
- #include<bits/stdc++.h>
- using namespace std;
- long long n,x,y,bj;
- stack<long long>a;
- stack<long long>b;
- stack<long long>c;
- int main(){
- cin>>n;
- for(int i=n;i>=1;i--)
- a.push(i);
- while(cin>>x>>y)
- {
- if(x==1)
- {
- while(y>0)
- {
- b.push(a.top());
- a.pop();
- y--;
- }
- }
- else
- {
- while(y>0)
- {
- c.push(b.top());
- b.pop();
- y--;
- bj++;
- }
- }
- if(bj==n)break;
- }
- while(!c.empty())
- {
- cout<<c.top()<<endl;
- c.pop();
- }
- return 0;
- }
程序员输入问题
程序员输入程序出现差错时，可以采取以下的补救措施：按错了一个键时，可以补按一个退格符“#”，以表示前一个字符无效；发现当前一行有错，可以按一个退行符“@”，以表示“@”与前一个换行符之间的字符全部无效。
输入
输入一行字符，个数不超过100。
输出
输出一行字符，表示实际有效字符。
样例输入
sdfosif@for (ii#=1,#; i<.#=8; i+++#);样例输出
for (i=1; i<=8; i++);提示
因为输入只有一行，所以题目所讲的遇到@退行符就是清空当前栈里面所有元素
代码：
- #include<bits/stdc++.h>
- using namespace std;
- string s,s1;
- stack<char>a;
- int main(){
- getline(cin,s);
- for(int i=0;i<s.size();i++)
- {
- if(s[i]=='#')a.pop();
- if(s[i]=='@')
- {
- while(!a.empty())
- {
- a.pop();
- }
- }
- if(s[i]!='#'&&s[i]!='@')
- {
- a.push(s[i]);
- }
- }
- while(!a.empty())
- {
- s1=a.top()+s1;
- a.pop();
- }
- cout<<s1;
- return 0;
- }
表达式括号匹配
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。
输入
一行数据，即表达式。
输出
一行，即“YES” 或“NO”。
样例输入
2*(x+y)/(1-x)@样例输出
YES代码：
- #include<bits/stdc++.h>
- using namespace std;
- stack<char>a;
- int main()
- {
- char ch;
- cin>>ch;
- while(ch!='@')
- {
- if(ch=='(')a.push(ch);
- else if(ch==')' && a.empty())
- {
- cout<<"NO";
- return 0;
- }
- else if(ch==')')a.pop();
- cin>>ch;
- }
- if(a.empty())cout<<"YES";
- else cout<<"NO";
- return 0;
- }
括弧匹配检验
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ］）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。
现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。输入一个字符串：［（［］［］）］，输出：OK。
输入
输入仅一行字符（字符个数小于255）。
输出
匹配就输出 “OK” ，不匹配就输出“Wrong”。
样例输入
[(])样例输出
Wrong代码：
- #include<bits/stdc++.h>
- using namespace std;
- int top;
- bool f;
- int main(){
- string s;
- char a[3000];
- cin>>s;
- int l=s.size(),n,m;
- for(int i=0;i<l;i++){
- if(s[i]=='('||s[i]==')')n++;
- if(s[i]=='['||s[i]==']')m++;
- if(s[i]=='('||s[i]=='[')a[++top]=s[i];
- if(s[i]==')'){
- if(a[top]=='(')top--;
- else{
- f=1;
- break;
- }
- }
- if(s[i]==']'){
- if(a[top]=='[')top--;
- else{
- f=1;
- break;
- }
- }
- }
- if(n%2==1||m%2==1){
- cout<<"Wrong";
- return 0;
- }
- if(f==1)cout<<"Wrong";
- else cout<<"OK";
- return 0;
- }
符号匹配
假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ］）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。
现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “YES” ，不匹配就输出“NO”。输入一个字符串：［（［］［］）］，输出：YES。
输入
输入包括多组测试数据，每组数据是一个字符串，字符串只包含“()[]”等字符。
输出
对于每组数据输出“YES”表示当前字符串中的括号是匹配的，否则输出“NO”（不包括引号）
样例输入
- ()
- ([)]
样例输出
- YES
- NO
代码：
- #include<bits/stdc++.h>
- using namespace std;
- string s;
- int main(){
- while(cin>>s){
- int top=0;
- bool f=0;
- char a[3000];
- for(int i=0;i<=2999;i++)a[i]=' ';
- int l=s.size(),n=0,m=0;
- for(int i=0;i<l;i++){
- if(s[i]=='('||s[i]==')')n++;
- if(s[i]=='['||s[i]==']')m++;
- if(s[i]=='('||s[i]=='[')a[++top]=s[i];
- if(s[i]==')'){
- if(a[top]=='(')top--;
- else{
- f=1;
- break;
- }
- }
- if(s[i]==']'){
- if(a[top]=='[')top--;
- else{
- f=1;
- break;
- }
- }
- }
- if(n%2==1||m%2==1){
- cout<<"NO\n";
- continue;
- }
- if(f==1)cout<<"NO\n";
- else cout<<"YES\n";
- }
-
- return 0;
- }
