面试题22:栈的压入、弹出序列

题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入序列,序列4,5,3,2,1,是该压栈序列对应的一个弹出序列。但4,3,5,1,2就不可能是该压栈序列的弹出序列。


分析

栈是一种“后进先出”(LIFO)的数据结构,所以元素的出进顺序都是有相对关系的。对应于题目中的例子,当入栈序列为1,2,3,4,5时,经过如下操作便可得到4,5,3,2,1的出栈序列:push(1),push(2),push(3),push(4),pop(4),push(5),pop(5),pop(3),pop(2),pop(1)。而对于4,3,5,1,2的出栈序列,尝试过程如下:push(1),push(2),push(3),push(4),pop(4),pop(3),push(5),pop(5),此时栈顶元素应该为2,而当前出栈序列中对应的元素为1,所以不可能是该栈的一个出栈序列。

经过以上分析,总结思想如下:

设置两个指针pIn和pOut,分别指向入栈和出栈序列的第一个元素。若_pIn!=_pOut,则将pIn指向的元素入栈,pIn++,知道两个元素相等时,将pIn指向的元素入栈并出栈,pOut++,继续重复以上过程即可。

代码如下:

<pre class="prettyprint linenums prettyprinted">

  1. <span class="kwd">bool</span><span class="pln"> </span><span class="typ">IsPopOrder</span><span class="pun">(</span><span class="kwd">const</span><span class="pln"> vector</span><span class="str">&lt;int&gt;</span><span class="pun">&amp;</span><span class="pln"> pPush</span><span class="pun">,</span><span class="kwd">const</span><span class="pln"> vector</span><span class="str">&lt;int&gt;</span><span class="pun">&amp;</span><span class="pln"> pPop</span><span class="pun">)</span>
  2. <span class="pun">{</span>
  3. <span class="pln"> </span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">,</span><span class="pln">j</span><span class="pun">;</span>
  4. <span class="pln"> </span><span class="kwd">int</span><span class="pln"> length</span><span class="pun">=</span><span class="pln">pPush</span><span class="pun">.</span><span class="pln">size</span><span class="pun">();</span>
  5. <span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">length</span><span class="pun">==</span><span class="lit">0</span><span class="pun">)</span>
  6. <span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">true</span><span class="pun">;</span>
  7. <span class="pln"> stack</span><span class="str">&lt;char&gt;</span><span class="pln"> s</span><span class="pun">;</span>
  8. <span class="pln"> s</span><span class="pun">.</span><span class="pln">push</span><span class="pun">(</span><span class="pln">pPush</span><span class="pun">[</span><span class="lit">0</span><span class="pun">]);</span>
  9. <span class="pln"> i</span><span class="pun">=</span><span class="lit">1</span><span class="pun">,</span><span class="pln">j</span><span class="pun">=</span><span class="lit">0</span><span class="pun">;</span>
  10. <span class="pln"> </span><span class="kwd">while</span><span class="pun">(</span><span class="pln">i</span><span class="pun">&lt;=</span><span class="pln">length </span><span class="pun">&amp;&amp;</span><span class="pln"> j</span><span class="pun">&lt;</span><span class="pln">length</span><span class="pun">)</span>
  11. <span class="pln"> </span><span class="pun">{</span>
  12. <span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">top</span><span class="pun">()!=</span><span class="pln">pPop</span><span class="pun">[</span><span class="pln">j</span><span class="pun">]</span><span class="pln"> </span><span class="pun">&amp;&amp;</span><span class="pln"> i</span><span class="pun">==</span><span class="pln">length</span><span class="pun">)</span>
  13. <span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">false</span><span class="pun">;</span>
  14. <span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">top</span><span class="pun">()!=</span><span class="pln">pPop</span><span class="pun">[</span><span class="pln">j</span><span class="pun">])</span>
  15. <span class="pln"> </span><span class="pun">{</span>
  16. <span class="pln"> s</span><span class="pun">.</span><span class="pln">push</span><span class="pun">(</span><span class="pln">pPush</span><span class="pun">[</span><span class="pln">i</span><span class="pun">++]);</span>
  17. <span class="pln"> </span><span class="pun">}</span>
  18. <span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">top</span><span class="pun">()==</span><span class="pln">pPop</span><span class="pun">[</span><span class="pln">j</span><span class="pun">])</span>
  19. <span class="pln"> </span><span class="pun">{</span>
  20. <span class="pln"> s</span><span class="pun">.</span><span class="pln">pop</span><span class="pun">();</span>
  21. <span class="pln"> j</span><span class="pun">++;</span>
  22. <span class="pln"> </span><span class="pun">}</span>
  23. <span class="pln"> </span><span class="pun">}</span>
  24. <span class="pln"> </span><span class="kwd">if</span><span class="pun">(</span><span class="pln">s</span><span class="pun">.</span><span class="pln">empty</span><span class="pun">())</span>
  25. <span class="pln"> </span><span class="pun">{</span>
  26. <span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">true</span><span class="pun">;</span>
  27. <span class="pln"> </span><span class="pun">}</span>
  28. <span class="pln"> </span><span class="kwd">else</span>
  29. <span class="pln"> </span><span class="pun">{</span>
  30. <span class="pln"> </span><span class="kwd">return</span><span class="pln"> </span><span class="kwd">false</span><span class="pun">;</span>
  31. <span class="pln"> </span><span class="pun">}</span>
  32. <span class="pun">}</span></pre>

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>