剑指 Offer 31. 栈的压入、弹出序列（946. 验证栈序列）

//剑指 Offer 31. 栈的压入、弹出序列
public class Offer {
    public static void main(String[] args) {
        int[] pushed = new int[]{1,2,3,4,5};
        int[] popped = new int[]{4,5,3,2,1};

        System.out.println(Method1(pushed,popped));
    }

    //思路一：说白了就是模拟栈的过程
    //用链表来代替存储
    public static boolean Method1(int[] pushed, int[] popped){
        LinkedList<Integer> stack = new LinkedList<>();
        int idx = 0;
        //模拟入栈，且入栈后要判断是否需要出栈
        for (int num : pushed) {
            stack.add(num);
            // 对于push入栈的每一个元素，都检查对应的poped数组中是否有可以弹出的元素，有重复的一次性全部弹出
            while (!stack.isEmpty() && stack.getLast() == popped[idx]) {
                stack.removeLast();
                idx++;
            }
        }
        return stack.isEmpty();
    }
}