剑指offer-问题22

谁借莪１个温暖的怀抱￠ 2022-05-11 11:20 162阅读 0赞

package offer;
    
    import java.util.Stack;
    
    /**
     * offer interview 22
     */
    public class Test22 {
    
        //method 1
        public static boolean isPopOrder(int[] push ,int[] pop){
            if (push == null
                    || pop == null
                    || pop.length == 0
                    || push.length == 0
                    || push.length != pop.length){
                return false;
            }
    
            Stack<Integer> stack = new Stack<>();
            int pushIndex = 0;
            int popIndex = 0;
    
            while (popIndex < pop.length){
                while (pushIndex < push.length
                        && (stack.isEmpty()
                            || stack.peek() != pop[popIndex])){
                    stack.push(push[pushIndex]);
                    pushIndex++;
                }
    
                if (stack.peek() == pop[popIndex]){
                    stack.pop();
                    popIndex++;
                }else{
                    return false;
                }
    
            }
            //return stack.isEmpty();
            return true;
        }
    
        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 = {2};
            System.out.println(isPopOrder(push5,pop5));
    
            int[] push6 = {1};
            int[] pop6 = {1};
            System.out.println(isPopOrder(push6,pop6));
    
            int[] push7 = {1};
            int[] pop7 = {};
            System.out.println(isPopOrder(push7,pop7));
    
            int[] push8 = {};
            int[] pop8 = {1};
            System.out.println(isPopOrder(push8,pop8));
    
            int[] push9 = {};
            int[] pop9 = {};
            System.out.println(isPopOrder(push9,pop9));
    
    
        }
    
    }