2.4 如何根据入栈序列判断可能的出栈序列

【出自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序列继续入栈。

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}是一个合理的出栈序列。

实现代码如下：

程序的运行结果为

算法性能分析：

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