【剑指offer-Java版】22栈的压入弹出序列

栈的压入弹出序列：给定两个序列，一个是压入顺序，判断另外一个是否是该压入顺序的一个弹出顺序

思路：纯粹的模拟栈的压入和弹出顺序
分别遍历压栈序列seq1和另一个序列seq2
比较当前栈顶元素和seq2的当前值
如果相等，那么弹出，seq2的指针下移
如果不等，那么依次压入seq1中的元素直到遇到栈顶等于当前seq2指针所知元素
如果上述遍历中将seq1中所有数据都压入栈之后，仍未找到seq2当前元素，那么失败
如果遍历完，两个序列的指针都到达末尾，那么成功

    public class _Q22 {

    public boolean IsPopOrder(int seq1[], int seq2[]){
        if(seq1 == null) return false;
        if(seq2 == null) return false;

        // 此处应该抛出异常提示调用者
        if(seq1.length != seq2.length) return false;

        boolean result = true;
        Stack<Integer> stack = new Stack<>();

        int seq1Index = 0;
        stack.push(seq1[seq1Index++]);
        for (int i = 0; i < seq2.length;) {
            if (seq2[i] == stack.peek()) {
                i++;
                stack.pop();
            } else {
                if (seq1Index < seq1.length) {
                    stack.push(seq1[seq1Index++]);
                }else{
                    result = false;
                    break;
                }
            }
        }

        return result;
    }
    }

测试代码：

    public class _Q22Test extends TestCase {

    _Q22 popOrder = new _Q22();

    public void test(){
        int seq1[] = {1, 2, 3, 4, 5};
        int seq2[] = {4, 5, 3, 2, 1};

        int seq3[] = {4, 3, 5, 1, 2};
        int seq4[] = {5};

        System.out.println(popOrder.IsPopOrder(seq1, seq2));
        System.out.println(popOrder.IsPopOrder(seq1, seq3));
        System.out.println(popOrder.IsPopOrder(seq4, seq4));
        System.out.println(popOrder.IsPopOrder(null, null));
    }
    }