算法题之栈的压入、弹出序列

题目来源

www.acwing.com/problem/content/40/

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

注意

若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

样例

输入：[1,2,3,4,5]
      [4,5,3,2,1]

输出：true

思路

以1，2，3，4，5为例，题中所说入栈顺序是指，**如果现在3入栈那么在3入栈之前1，2一定已经入栈(但不一定仍在栈中)**；

我们先模拟两个出栈顺序，找出不同点与规律。

例如出栈顺序可为1，2，3，4，5，那么出入栈的操作为：1先入栈然后出栈，2入栈然后出栈（这时栈为空），3入栈然后出栈，4入栈然后出栈，4入栈然后出栈；如果出栈顺序为1，2，3，5，4，那么出入栈的操作为：1先入栈然后出栈，2入栈然后出栈，3入栈然后出栈，4入栈，5入栈然后出栈，4出栈；

一个出栈顺序是1，2，3，4，5，而另一个是1，2，3，5，4.通过对比过程我们可以知道一个是4入栈后出栈，一个是4入栈后但没有出栈而是继续入栈。所以，对于同一个元素入栈后，有两种操作选择，继续入栈和出栈。这时我们可以画一颗二叉树，每一条路就是我们可以选择的方案。题中并没有让我们求所有方案，只给我们一种方案去判断，所以我们只需要根据出栈顺序去模拟该进行的是入栈还是出栈操作就行了。简单来说就是给你了路标，你跟着走，走通了就是正确的路标走不通就是错误的路标。接下来继续看例子，入栈顺序仍是1，2，3，4，5

第一条路：入栈顺序1，2，3，4，5，出栈顺序1，2，5，4，3

模拟过程：首先1入栈，入栈后有两条路可以选，出栈或者继续入栈，这时看地图(给的出栈顺序)第一个元素是1，说明我们要选择的路是1出栈；然后继续2入栈，看地图(出栈顺序)第二个元素是2，说明我们要选择的路是2出栈；然后继续3入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路不是出栈而是继续入栈（这时栈中有元素3）；然后继续4入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路不是出栈而是继续入栈（这时栈中有元素3，4）；然后继续5入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路是出栈刚刚入栈的5，出栈后栈中还有元素3，4，看地图(出栈顺序)第四个元素是4，所以我们再出栈，出栈后栈中还有元素3，看地图(出栈顺序)第五个元素是3，所以我们再出栈.最后模拟完毕，路走通了。

第二条路：入栈顺序1，2，3，4，5，出栈顺序1，2，5，3，4

模拟过程：首先1入栈，入栈后有两条路可以选，出栈或者继续入栈，这时看地图(给的出栈顺序)第一个元素是1，说明我们要选择的路是1出栈；然后继续2入栈，看地图(出栈顺序)第二个元素是2，说明我们要选择的路是2出栈；然后继续3入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路不是出栈而是继续入栈（这时栈中有元素3）；然后继续4入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路不是出栈而是继续入栈（这时栈中有元素3，4）；然后继续5入栈，看地图(出栈顺序)第三个元素是5，说明我们要选择的路是出栈刚刚入栈的5，出栈后栈中还有元素3，4，看地图(出栈顺序)第四个元素是3，所以我们不能再出栈，需要入栈但是1，2，3，4，5都已经入栈了没有元素了，所以路走不通。

AC代码

class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        //如果长度不一样直接return false
        if(pushV.length != popV.length){
            return false;
        }
        //如果输入输出栈为空则直接return true
        if(pushV.length == 0 && popV.length == 0){
            return true;
        }
        Stack<Integer> s=new Stack<>();
        int j = 0;  //定义j指向popV数组，存储判断到了哪个元素
        //循环入栈，如果栈顶元素与出栈数组popV的所指向的元素相等则出栈该元素，如果栈不为空则继续尝试出栈操作。无法出栈则继续循环入栈直到无法入栈
        for(int i = 0;i<pushV.length;i++){
            s.push(pushV[i]);
            while(!s.isEmpty()&&s.peek() == popV[j]){
                j++;
                s.pop();
            }
        }
        //最后模拟的栈中应该为空，如果为空则出栈顺序符合，反之不符合
        if(s.isEmpty()){
            return true;
        }
        return false;
    }
}