Kotlin 程序员面试算法：栈与队列相关题目解析

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 序列。

在上图中，（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} 是一个合理的出栈序列。

实现代码如下：

import java.util.Stack

fun isPopSerial(push: String?, pop: String?): Boolean {
    if (push == null || pop == null) return false
    val pushLen = push.length
    val popLen = pop.length
    if (pushLen != popLen) return false
    var pushIndex = 0
    var popIndex = 0
    val stack = Stack<Char>()
     (pushIndex < pushLen) {
        
        stack.push(push[pushIndex])
        pushIndex++
        
         (!stack.isEmpty() && stack.peek() == pop[popIndex]) {
            stack.pop()
            popIndex++
        }
    }
    
     stack.isEmpty() && popIndex == popLen
}

 {
     push = 
     pop = 
     (isPopSerial(push, pop)) println()
     println()
}