【剑指Offer 22】栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

解法1：

代码如下：

package demo;

import java.util.Stack;

public class Test22 {
    /**
     * @param push
     *            入栈序列
     * @param pop
     *            出栈序列
     * @return true：出栈序列是入栈序列的一个弹出顺序
     */
    public static boolean isPopOrder(int[] push, int[] pop) {
        // 判断出栈序列是不是入栈序列的一个弹出顺序，默认为false
        boolean isPossible = false;
        if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
            // 辅助栈：存放入栈时的数据
            Stack<Integer> stack = new Stack<>();
            // 记录下一个要处理的入栈元素的位置
            int nextPush = 0;
            // 记录下一个要处理的出栈元素的位置
            int nextPop = 0;
            // 如果出栈元素没有处理完，就继续进行处理
            while (nextPop < pop.length) {
                // 如果栈为空，或者栈顶元素与当前处理的出栈元素不相同，一直进行操作
                while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
                    // 如果入栈元素已经全部入栈了，就退出内层循环
                    if (nextPush >= push.length) {
                        break;
                    }
                    // 还有入栈元素可以入栈
                    stack.push(push[nextPush]);
                    nextPush++;
                }
                /*
                 * 此次有2种情况： 
                 * 1.在栈顶上找到了一个与出栈元素相等的元素 
                 * 2.在栈顶上没有找到一个与出栈元素相等的元素，而且入栈元素已经全部入栈了
                 */
                // 2.
                if (stack.peek() != pop[nextPop]) {
                    break;
                }
                // 第1种情况，就将出栈的栈顶元素弹出
                stack.pop();
                // 指向下一个要处理的出栈元素的位置
                nextPop++;
            }
            /*
             * 此处有2种情况： 
             * 1. 外层while循环在第2种情况下退出，此时stack必不为空 
             * 2. 所有的出栈元素都被正确匹配，此时stack为空
             */
            if (stack.isEmpty()) {
                isPossible = true;
            }
        }
        return isPossible;
    }

    public static void main(String[] args) {
        int[] push = { 1, 2, 3, 4, 5 };
        int[] pop1 = { 4, 5, 3, 2, 1 };
        int[] pop2 = { 3, 5, 4, 2, 1 };
        int[] pop3 = { 4, 3, 5, 1, 2 };
        int[] pop4 = { 3, 5, 4, 1, 2 };
        System.out.println(isPopOrder(push, pop1));
        System.out.println(isPopOrder(push, pop2));
        System.out.println(isPopOrder(push, pop3));
        System.out.println(isPopOrder(push, pop4));
        int[] push5 = { 1 };
        int[] pop5 = { 1 };
        System.out.println(isPopOrder(push5, pop5));
        System.out.println(isPopOrder(null, null));
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46691083