剑指offer21-栈的压入，弹出序列

一：

第一种方法-辅助栈 Judge4，我自己用的也是辅助栈，但是没这个答案精简。

第二种方法-ArrayList，也是相同的思路，只不过将辅助栈改为arrayList，本质一样。

最后一种方法Judge5，报错，因为我想将int[]，直接转为ArrayList<Integet>，失败。

有两个方法：

1. 

org.apache.commons.lang3.ArrayUtils.toObject(int[]) 方法 先转成Integer数组

再使用 java.util.Arrays.asList(Integer...) 转成list

int[] src = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Integer[] is = ArrayUtils.toObject(src);
List<Integer> asList = Arrays.asList(is);

2.for循环，一个一个转。

这里涉及自动装箱拆箱的概念。下一篇解释。 

 二：error： array required, but ArrayList<String> found

arraylist获取某索引的元素的方法是arr.get(index)，而不是arr[index]。

这里涉及arrays，arraylist的区别。下一篇解释。

参考：https://stackoverflow.com/questions/20067956/array-required-but-arrayliststring-found

import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if(pushA.length==0||popA.length==0){
          return false;
      }
        //法1：
        //顺序问题:两个数组，一个栈，根据pushA进行压栈，根据popA进行弹出。
        //栈顶元素与popA进行比对，相同则下一个循环，不同如果索引没过则下一个循环或进行压栈，否则输出false
        //return Judge1(pushA,popA);
        //return Judge2(pushA,popA);
         return Judge3(pushA,popA);
        //return Judge4(pushA,popA);
        //return Judge5(pushA,popA);
    }

     //用栈-精简版。压入栈后判断顶层是不是匹配，若同则连续出栈
    //当pushA全部压入栈后，如果无法按照popA的方式出栈，则判断为false
    public boolean Judge4(int [] pushA,int [] popA){
        Stack<Integer> stack=new Stack<Integer>();
        for(int i=0,j=0;i<pushA.length;){
            stack.push(pushA[i++]);
            while(j<popA.length&&stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    
    //如果不想用栈，可以用arraylist，毕竟ArrayList（容量可变数组）相当于对数组的最后一位进行操作，
    //唯一问题，arr的length是不是实时改变？容量是什么？是size不是length，实时改变
    //stack.pop=arr.remove(length-1);stack.push=arr.add(val);stack.peek=arr[length-1]
    public boolean Judge5(int[] pushA,int[] popA){
        ArrayList<Integer> arr=new ArrayList<Integer>();
        for(int i=0,j=0;i<pushA.length;){
            arr.add(pushA[i++]);
            while(j<popA.length&&arr.get(arr.size()-1)==popA[j]){
                arr.remove(arr.size()-1);
                j++;
            }
        }
        return arr.isEmpty();
    }

    //3层if-else
    public boolean Judge1(int [] pushA,int[] popA){
        int i,j;
        i=j=0;
        Stack<Integer> stack=new Stack<Integer>();
        while(i<pushA.length||j<popA.length){
            if(stack.empty()){
                stack.push(pushA[i++]);
            }
            if(stack.peek()==popA[j]){
                stack.pop();
                j+=1;
            }else{
                if(i<pushA.length){
                    if(popA[j]==pushA[i]){
                        i+=1;
                        j+=1;
                    }else{
                        stack.push(pushA[i++]);
                    }
                }else{
                    return false;
                }
            }
        }
        if(i==pushA.length&&j==popA.length)
            return true;
        return false;
    }
    //两层if-else
    public boolean Judge2(int[] pushA,int[] popA){
        Stack<Integer> stack=new Stack<Integer>();
        stack.push(pushA[0]);
        int i=1;
        int j=0;
        while(!stack.empty()){
                if(stack.peek()!=popA[j]){
                    if(i<pushA.length)
                        stack.push(pushA[i++]);
                    else
                        return false;
                }
                else{
                    stack.pop();
                    j++;
                }
            }
        return true;
    }
    
    //不用栈，两个index，一个指向indexT=pushA[popA[i]]，一个指向ndexN=pushA[popA[i+1]]，
    //如果indexN<indexT，则indexN==indexT-1;
    public boolean Judge3(int [] push,int [] popA){
        int indexT=0;
        int indexN=0;
        ArrayList<Integer> pushA=Arrays.asList(push);
        int j=0;
        while(j<popA.length-1){
            indexT=pushA.indexOf(popA[j]);
            indexN=pushA.indexOf(popA[j+1]);
            if(indexN==indexT-1||indexN>indexT){
                pushA.remove(indexT);
                ++j;
            }else{
                    return false;
                }
            }
            if(pushA.get(0)==popA[j])
                pushA.remove(0);
        return pushA.isEmpty();
        }
    
}