首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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&lt;bits/stdc++.h&gt; using namespace std; int main() {   int n;   cin&gt;&gt;n;   int a[100001],t=1,i;   int l1[100001],l2[100001],l=0;   stack &lt;int&gt; s;   for(i=1;i&lt;=n;i++)     cin&gt;&gt;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 &amp;&amp; t-1==n &amp;&amp; i-1==n) break;     if(s.size()&gt;0 &amp;&amp; t-1==n &amp;&amp; i-1&lt;n)     {       cout&lt;&lt;"NO";       return 0;     }   }   for(i=1;i&lt;=l;i++)   {     if(l1[i]==1) cout&lt;&lt;"POP ";     else cout&lt;&lt;"PUSH ";     cout&lt;&lt;l2[i]&lt;&lt;endl;   }   return 0; }</pre><pre class="brush:cpp;toolbar:false"> //解法2 #include &lt;bits/stdc++.h&gt; using namespace std; int main() { queue&lt;string&gt; q; stack&lt;int&gt; s; string x="PUSH ",y="POP "; int n; cin&gt;&gt;n; for(int i=1,j=1,a;i&lt;=n;i++){ cin&gt;&gt;a; if(a&gt;n){ cout&lt;&lt;"NO";return 0; } if(s.empty()){ s.push(j); q.push(x+char(j+'0')); j++; } while(s.top()&lt;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&lt;&lt;"NO";return 0; } } if(!s.empty()){ cout&lt;&lt;"NO";return 0; } while(!q.empty()){ cout&lt;&lt;q.front()&lt;&lt;endl; q.pop(); } return 0; }</pre>
这道题暂未补解析。