入栈序列判断可能的出栈序列

【出自TX面试题】

难度系数：★★★☆☆ 被考察系数：★★★★★

题目描述：

输入两个整数序列，其中一个序列表示栈的push（入）顺序，判断另一个序列有没有可能是对应的pop（出）顺序。

分析与解答：

假如输入的push序列是1、2、3、4、5，那么3、2、5、4、1就有可能是一个pop序列，但5、3、4、1、2就不可能是它的一个pop序列。

主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：

（1）把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动到第二个元素。

（2）如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。(www.xing528.com)

（3）如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop序列。下图给出一个合理的pop序列的判断过程。

在上图中，（1）～（3）三步，由于栈顶元素不等于pop序列第一个元素3，因此，1，2，3依次入栈，当3入栈后，栈顶元素等于pop序列的第一个元素3，因此，第（4）步执行3出栈，接下来指向第二个pop序列2，且栈顶元素等于pop序列的当前元素，因此，第（5）步执行2出栈；接着由于栈顶元素4不等于当前pop序列5，因此，接下来（6）和（7）两步分别执行4和5入栈；接着由于栈顶元素5等于pop序列的当前值，因此，第（8）步执行5出栈，接下来（9）和（10）两步栈顶元素都等于当前pop序列的元素，因此，都执行出栈操作。最后由于栈为空，同时pop序列都完成了遍历，因此，{3，2，5，4，1}是一个合理的出栈序列。

实现代码如下：

程序的运行结果如下：

32541是12345的一个pop序列

算法性能分析：

这种方法在处理一个合理的pop序列的时候需要操作的次数最多，即把push序列进行一次压栈和出栈操作，操作次数为2N，因此，时间复杂度为O（N），此外，这种方法使用了额外的栈空间，因此，空间复杂度为O（N）。