剑指Offer第二十一题：栈的压入丶弹出序列

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

解答：
思路：遍历输出序列，若等于当前栈顶元素则弹出，若不等于则循环压入输入序列中的数直到找到输入序列中相等的数结束。若已经全部压入仍然没有找到相等的值则失败。输出序列遍历完毕后，查看栈中是否还有元素，如果还有元素则失败。

public class Q_21 {

Stack<Integer> stack = new Stack<>();
int index = 0;
public boolean IsPopOrder(int[] pushA, int[] popA) {
    for (int i = 0; i < popA.length; i++) {//遍历输出序列
        if (!stack.isEmpty() && stack.peek() == popA[i]) {//查看栈顶元素是否等于pop[i]
            stack.pop();
        } else {
            if (index >= pushA.length) {
                return false;
            }
            while (index < pushA.length) {//遍历输入序列
                if (pushA[index] == popA[i]) {
                    index++;
                    break;
                } else {
                    stack.push(pushA[index]);
                    index++;
                }
            }

        }
    }

    return stack.isEmpty();
}
public static void main(String[] args) {
    int[] pushA = {1, 2, 3, 4, 5};
    int[] popA = {4, 5, 3, 2, 1};
    int[] popB = {4, 5, 3, 1, 2};
    int[] testA = {1};
    int[] testB = {2};
    System.out.println(new Q_21().IsPopOrder(testA, testB));
}

}