简答题
偏难
#7388
栈基本操作 依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否…
栈基本操作
依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。
时间限制:1000
内存限制:65535
输入
输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)
输出
如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”
样例输入
7 4 5 3 6 2 7 1
样例输出
PUSH 1 PUSH 2 PUSH 3 PUSH 4 POP 4 PUSH 5 POP 5 POP 3 PUSH 6 POP 6 POP 2 PUSH 7 POP 7 POP 1
提示
给定序列中有可能有不在1...n之间的数字
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[100001],t=1,i;
int l1[100001],l2[100001],l=0;
stack <int> s;
for(i=1;i<=n;i++)
cin>>a[i];
i=1;
int f=0;
while(1)
{
s.push(t);
l++;
l1[l]=0;
l2[l]=t;
t++;
while(1)
{
if(s.size()==0) break;
if(a[i]!=s.top()) break;
i++;
l++;
l1[l]=1;
l2[l]=s.top();
s.pop();
}
if(s.size()==0 && t-1==n && i-1==n) break;
if(s.size()>0 && t-1==n && i-1<n)
{
cout<<"NO";
return 0;
}
}
for(i=1;i<=l;i++)
{
if(l1[i]==1) cout<<"POP ";
else cout<<"PUSH ";
cout<<l2[i]<<endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">
//解法2
#include <bits/stdc++.h>
using namespace std;
int main()
{
queue<string> q;
stack<int> s;
string x="PUSH ",y="POP ";
int n;
cin>>n;
for(int i=1,j=1,a;i<=n;i++){
cin>>a;
if(a>n){
cout<<"NO";return 0;
}
if(s.empty()){
s.push(j);
q.push(x+char(j+'0'));
j++;
}
while(s.top()<a){
s.push(j);
q.push(x+char(j+'0'));
j++;
}
if(s.top()==a){
s.pop();
q.push(y+char(a+'0'));
}
else{
cout<<"NO";return 0;
}
}
if(!s.empty()){
cout<<"NO";return 0;
}
while(!q.empty()){
cout<<q.front()<<endl;
q.pop();
}
return 0;
}</pre>
这道题暂未补解析。