题解 | #栈的压入、弹出序列#

递归思路(java)：
1.用两个指针指向最新的可入栈元素和目前想要从栈获取的元素；
2.每次尝试获取目标元素，成功则出栈并更新目标元素继续获取，失败则纳入可入栈元素并继续尝试获取当前目标元素
3.目标元素全部获取，则返回true

import java.util.Stack;
//判断出栈序列是否合法
public class Solution {
    static int p1=0,p2=0;//p1指向最新的可入栈元素，p2指向想要从栈中获取的元素
    static Stack<Integer> s=new Stack();
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        return fun(pushA,popA);
    }
    public boolean fun(int[] PA,int[] PB){
        //如果栈为空，但还有想要取得的元素，则将p1所指入栈，并尝试获取p2所指
        if(s.size()==0 && p2<=PB.length-1){
            s.push(PA[p1]);
            p1++;
            System.out.println("入栈:"+s.peek()+" "+s);
            return fun(PA,PB);
        }
        //如果可以取得该元素 即p2所指
        if(PB[p2]==s.peek()){
            int ss=s.peek();
            s.pop();
            System.out.println("出栈:"+ss+" "+s.toString());
            //如果后面还有待取元素,尝试获取
            if(p2<=PB.length-2){
                p2++;
                return fun(PA,PB);
            }
            //如果当前是最后一个元素，结束，合法
            if(p2==PB.length-1){
                return true;
            }
        }
        //如果无法取得该元素
        if(PB[p2]!=s.peek()){
            //如果已经没有可取元素，直接返回非法
            if(p1==PA.length)return false;
            s.push(PA[p1]);
            System.out.println("入栈:"+s.peek()+" "+s);
            p1++;
            return fun(PA,PB);
        }
        return false;
    }
}