JavaSE集合-Queue入门与详解

Queue用于模拟"队列"这种数据结构(先进先出 FIFO)。队列的头部保存着队列中存放时间最长的元素，队列的尾部保存着队列中存放时间最短的元素。新元素插入(offer)到队列的尾部，访问元素(poll)操作会返回队列头部的元素，队列不允许随机访问队列中的元素

【1】 PriorityQueue

PriorityQueue并不是一个比较标准的队列实现，PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序，这点从它的类名也可以看出来 。

PriorityQueue的应用之流式数据中计算第K个最大数：

public class KthLargest {

    final PriorityQueue<Integer> queue;
    final int k;

    public KthLargest(int k ,int[] a){
        this.k=k;
        queue = new PriorityQueue<>();
        for (int n:a) {
            add(n);
        }
    }

    public int add(int n){
        if (queue.size()<k){
            queue.offer(n);
        }else if(queue.peek()<n){
            queue.poll();
            queue.offer(n);
        }
        System.out.println(queue.peek());
        return queue.peek();
    }

    public static int KthLargest1(int k,int[]a){
        List<Integer> nums = new ArrayList<Integer>();
        for(int n:a){
            if(nums.size()<k){
                nums.add(n);
            }else if (nums.get(0)<n){
                nums.remove(0);
                nums.add(n);
            }
            nums.sort((o1, o2) -> o1.compareTo(o2));
            System.out.println("当前第 "+k+"大的数为 ："+nums.get(0)+nums);
        }
        return nums.get(0);
    }
    public static void main(String[] args){

        int[] nums=new int[]{0,1,4,3,5,7,0,5,9,5};
        int k=3;
        int i = KthLargest1(k, nums);
        KthLargest kthLargest = new KthLargest(k, nums);
    }
}

【2】Deque

Deque接口代表一个"双端队列"，双端队列可以同时从两端来添加、删除元素，因此Deque的实现类既可以当成队列使用、也可以当成栈使用。

【3】 ArrayDeque

是一个基于数组的双端队列，和ArrayList类似，它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素，当集合元素超出该数组的容量时，系统会在底层重新分配一个Object[]数组来存储集合元素。