栈的压入、弹出序列

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null || popA == null || pushA.length ==0 ||popA.length ==0){
           return false;
        }
        int index =0;
        Stack<Integer> stacks = new Stack<>();
        stacks.push(pushA[index]);
        for(int i =0;i<popA.length;i++){
            if(stacks.peek() == popA[i]){
                stacks.pop();
            }else{
                while(stacks.peek() != popA[i]){
                    if(index !=pushA.length -1){
                        stacks.push(pushA[++index]);
                    }else{
                        return false;
                    }
                }
                stacks.pop();
            }
        }
        return true;
    }
}
public static void main(String[] args) {
    int[] pushed = {1,2,3,4,5};
    int[] popped = {4,5,3,2,1};
    System.out.println(validateStackSequences(pushed,popped));
}
public static boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null || pushed.length == 0 || popped.length == 0)
    {
        return false;
    }
    int index = 0;
    //作为弹出序列的一个索引
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i <pushed.length ; i++) {
        stack.push(pushed[i]);
        while (!stack.isEmpty() && stack.peek() ==popped[index]){
            // 当栈不为空且栈顶元素等于弹出序列元素时候，就弹出一个，同时让弹出序列后移一个
            stack.pop();
            index++;
        }
    }
    return stack.isEmpty();
}

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      Stack<Integer> stacks = new Stack<>();
        int index =0;
        stacks.push(pushA[index]);
        for(int i =0;i<popA.length;i++){
            if(popA[i] ==stacks.peek()) {
                stacks.pop();
            } else{
                while (stacks.peek() != popA[i]){
                    if(index == pushA.length-1){
                        return false;
                    }
                    stacks.push(pushA[++index]);
                }
                stacks.pop();
            }
        }
        return true;
    }
}