集合_Queue&Deque&LinkedList&ArrayDeque&PriorityQueue详解

偏执的太偏执、 2024-03-30 11:34 48阅读 0赞

## 1、 Queue与Deque的区别 ##

> 1）引言：  
> 在研究java集合源码的时候，发现了一个很少用但是很有趣的点：Queue以及Deque；  
> 平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道Queue的作用，于是就直接官方文档好了。

> 2）Queue和Deque：  
> Deque是Queue的子接口；  
> 从源码中可以得知：Queue以及Deque都是继承于Collection，Deque是Queue的子接口。  
> public interface Deque extends Queue \{\}

> Queue——单端队列；Deque——双端队列；  
> 从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端队列，就是可以在首和尾都进行插入或删除元素。  
> 而Queue的解释中，Queue就是简单的FIFO（先进先出）队列。所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。

> Queue常用子类——PriorityQueue；Deque常用子类——LinkedList以及ArrayDeque；  
> Queue有一个直接子类PriorityQueue。  
> 而Deque中直接子类有两个：LinkedList以及ArrayDeque。

> 1.  PriorityQueue：  
>     我觉得重点就在圈定的两个单词：无边界的，优先级的堆。  
>     从源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。

## 2 PriorityQueue源码解读 ##

> top k算法的经典实现是大顶堆和小顶堆，而在JAVA中可以用PriorityQueue实现小顶堆，话不多说，直接上代码

public static List<Integer> getTopMapNum(int[] arr, int k) {
        
        Queue<Integer> priorityQueue = new PriorityQueue();
        List<Integer> topKList = new ArrayList<>();
        if (arr == null || k > arr.length || k <= 0) {
        
            return topKList;
        }
        for (int i : arr) {
        
            if (priorityQueue.size() < k) {
        
                priorityQueue.add(i);
            } else {
        
                if (priorityQueue.peek() < i) {
        
                    priorityQueue.poll();
                    priorityQueue.add(i);
                }
            }
        }
    
        while (k-- > 0) {
        
            topKList.add(priorityQueue.poll());
        }
        return topKList;
    }

> 作为程序员，只知道简单的如何实现是不够的，最好能够深入源码，下面我们就来聊一聊PriorityQueue  
> PriorityQueue是优先队列，作用是保证每次取出的元素都是队列中权值最小的，这里涉及到了大小关系，元素大小的评判可以通过元素自身的自然顺序（使用默认的比较器），也可以通过构造时传入的比较器。

> Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

![在这里插入图片描述][40dfed5572c24a1583d8735401f7d367.png]

![在这里插入图片描述][a0ec3e3698e14d52be094407519d503e.png]

> 上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

> leftNo = parentNo*2+1  
> rightNo = parentNo*2+2  
> parentNo = (nodeNo-1)/2

> 通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。  
> PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

> 方法解析（JDK 1.8）  
> add()和offer  
> add()方法内部是调用的offer()，所以两个方法没啥区别，都是向队列中插入元素

![在这里插入图片描述][df9b26898f4740a2af8e612011f51662.png]  
![在这里插入图片描述][9e9eadf0734249eca020f216a58146eb.png]

> 新加入的元素可能会破坏小顶堆的性质，所以需要进行调整

/**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     *队列调整的次数
     */
    transient int modCount = 0; // non-private to simplify nested class access
    /**
     * The number of elements in the priority queue.
     *队列中元素的个数
     */
    private int size = 0;
    public boolean add(E e) {
        
        //add方法内部调用的offer方法
        return offer(e);
    }
    public boolean offer(E e) {
        
        if (e == null)
            throw new NullPointerException();
       //队列调整的次数
        modCount++;
        int i = size;
        //如果队列元素个数大于等于队列的长度，则需要进行扩容
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        //如果是第一个元素，直接插入即可
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);//如果不是第一个元素，则需要进行调整
        return true;
    }
    /**
     * Increases the capacity of the array.
     *队列扩容
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        
        //原始队列容量
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        //如果原始队列容量没有超过64，则翻倍扩容，否则扩容50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        //如果扩容后的队列大小超过了最大队列大小，则需要进行特殊处理
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    /**
     * Inserts item x at position k, maintaining heap invariant by
     * promoting x up the tree until it is greater than or equal to
     * its parent, or is the root.
     *
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *
     * @param k the position to fill
     * @param x the item to insert
     * 元素添加
     */
    private void siftUp(int k, E x) {
        
        //使用构造方法传进来的比较器
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);//使用默认的比较器
    }
    private void siftUpComparable(int k, E x) {
        
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
        
            //获取父节点的下标
            int parent = (k - 1) >>> 1;
            //父节点的元素值
            Object e = queue[parent];
            //如果新插入的元素比父节点的元素值大，循环结束，新插入节点直接插入最后即可
            if (key.compareTo((E) e) >= 0)
                break;
            //否则需要把父节点元素值放到新插入节点的下标（可以理解为父节点与新插入元素调换位置）
            queue[k] = e;
            //重复进行，知道父节点比子节点小
            k = parent;
        }
        //新插入元素放入排序后的下标
        queue[k] = key;
    }

> poll 类似，poll 从上往下进行，然后将左右进行比较，将小的一个和 父节点交换

## 3 LinkedList以及ArrayDeque： ##

> 从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。  
> 而我们还能看到，ArrayDeque作为队列时的效率比LinkedList要高。  
> 而在栈的使用场景下，无疑具有尾结点，不需判空的LinkedList更为高效。  
> 演示ArrayDeque作为队列以及LinkedList作为栈的使用：

private static void usingAsQueue() {
        
            Deque<Integer> queue=new ArrayDeque<>();
            System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
            queue.addLast(12);   //添加元素
            System.out.println(queue.peekFirst());   //获取队列首部元素
            System.out.println(queue.pollFirst());   //获取并移除栈顶元素
     }
     
    private static void usingAsStack() {
        
            //作为栈使用
            Deque<Integer> stack=new LinkedList<>();
            System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
            stack.addFirst(12);//添加元素
            System.out.println(stack.peekFirst());   //获取栈顶元素
            System.out.println(stack.pollFirst());   //获取并移除栈顶元素
        }

> 小提示：  
> 在Deque中，获取并移除元素的方法有两个，分别是removeXxx以及peekXxx。  
> 存在元素时，两者的处理都是一样的。  
> 但是当Deque内为空时，removeXxx会直接抛出NoSuchElementException，  
> 而peekXxx则会返回null。  
> 所以无论在实际开发或者算法时，推荐使用peekXxx方法。  
> 其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列，以及LinkedList作为栈使用，会是更好的选择。

> 注意：  
> ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack。ArrayDeque 也可以作为队列来使用，效率相较于基于双向链表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持为 null 的元素。  
> 之后，再说为什么建议使用ArrayDeque而不是LinkedList:  
> 链表比数组花费更多空间  
> 链表的随机访问性质比数组差（虽然这个对栈来说问题不大）  
> 链表的每次插入和删除都涉及到一个节点对象的创建和弃用，非常低效和浪费空间，而动态数组几乎是0花费的(数组充满时重新拷贝除外)  
> 链表是非连续的，访问时候不能充分利用cpu cache  
> 个人觉得第三点最重要

> 所以无论是栈还是队列，JDK都是建议使用ArrayDeque而不是LinkedList实现，ArrayDeque比较复杂的一点就是需要指定初始大小，当然你不指定也行。但是它的效率确实是比LinkedList高的

> 小结：  
> PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。  
> ArrayDeque可以作为栈或队列使用，但是栈的效率不如LinkedList高，通常作为队列使用。  
> LinkedList可以作为栈或队列使用，但是队列的效率不如ArrayQueue高，通常作为栈使用。

> Queue和Deque的方法区别：  
> 在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。  
> 而由于双端队列的定义，Deque可以作为栈或者队列使用；  
> 而Queue只能作为队列或者依赖于子类的实现作为堆使用。  
> 方法上的区别如下：  
> ![请添加图片描述][8d012c98ef704b798dbde49b81cb8240.png]  
> add offer add 底层调用offer 无区别  
> remove 无元素 抛出异常 poll 返回null 删除元素  
> peek element 不删除元素 ，element 无元素 抛出异常，peek 返回null

> LinkedList与ArrayDeque在栈与队列中的使用  
> LinkedList  
> 增加：  
> add(E e)：在链表后添加一个元素； 通用方法  
> addLast(E e)：在链表尾部添加一个元素； 特有方法  
> offer(E e)：在链表尾部插入一个元素  
> offerLast(E e)：JDK1.6版本之后，在尾部添加； 特有方法

> 特点：add 与 addLast 一个有返回值 boolean，一个无  
> offer 与 add 与 offerLast 一样

> addFirst(E e)：在链表头部插入一个元素； 特有方法  
> offerFirst(E e)：JDK1.6版本之后，在头部添加； 特有方法

> 特点：offerFirst 有返回值 addFirst无  
> add(int index, E element)：在指定位置插入一个元素。

> 删除：  
> remove() ：移除链表中第一个元素; 通用方法  
> removeFirst() 移除第一个元素  
> pollFirst()：删除头； 特有方法  
> ==pop()：和removeFirst方法一致，删除头。 ==  
> ==poll()：查询并移除第一个元素 特有方法 ==

> 特点：remove 抛异常，poll 返回null pop 与 removeFirst remove一致  
> remove(E e)：移除指定元素； 通用方法  
> removeFirst(E e)：删除头，获取元素并删除； 特有方法  
> removeLast(E e)：删除尾； 特有方法

> pollLast()：删除尾； 特有方法  
> 查：  
> poll()：查询并移除第一个元素 特有方法  
> pollFirst()：查询并删除头； 特有方法  
> getFirst()：获取第一个元素； 特有方法  
> peek()：获取第一个元素，但是不移除； 特有方法  
> peekFirst()：获取第一个元素，但是不移除；

> 特点：poll 弹出数据，无数据返回null ：getFirst 无数据 抛出异常, peek 返回数据，无数据返回null  
> getLast()：获取最后一个元素； 特有方法  
> peekLast()：获取最后一个元素，但是不移除；  
> pollLast()：删除尾； 特有方法  
> get(int index)：按照下标获取元素； 通用方法

> ArrayDeque  
> 特点：  
> ArrayDeque实现了Deque接口。可当作栈来用，效率高于stack。也可当作队列来用，效率高于LinkedList。  
> 底层用可变数组实现，无容量限制。  
> ArrayDeque是不安全的。

> 增加:  
> addFirst(E e)在数组前面添加元素  
> addLast(E e)在数组后面添加元素  
> offerFirst(E e)在数组前面添加元素，并返回是否添加成功  
> offerLast(E e)在数组后添加元素，并返回是否添加成功  
> push(E e)：与addFirst方法一致  
> offer(E e)：在链表尾部插入一个元素

> 删除：  
> removeFirst()删除第一个元素，并返回删除元素的值，如果为null，将抛出异常  
> removeLast()删除最后一个元素，并返回删除元素的值，如果为null,将抛出异常  
> pollFirst()删除第一个元素，并返回删除元素的值，如果为null，将返回null  
> pollLast()删除最后一个元素，并返回删除元素的值，如果为null,将返回null  
> ==pop()：和removeFirst方法一致，删除头。 ==  
> poll()：查询并移除第一个元素 特有方法

> 查：  
> getFirst()获取第一个元素，如果为null，将抛出异常  
> getLast()获取最后一个元素，如果为null，将抛出异常  
> peek()：获取第一个元素，但是不移除； 特有方法

> 注意  
> add() 和 offer()的区别  
> 在容量已满的情况下，add() 方法会抛出IllegalStateException异常，offer() 方法只会返回 false  
> remove方法和poll方法都是删除队列的头元素，remove方法，队列为空的情况下将抛异常，而poll方法将返回null；  
> element和peek方法都是返回队列的头元素，但是不删除头元素，区别在与element方法在队列为空的情况下，将抛异常，而peek方法将返回null。

[40dfed5572c24a1583d8735401f7d367.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/566481e2ecc542589e5c5e4c396d43df.png
[a0ec3e3698e14d52be094407519d503e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ad868c4efc044a1286a9e822b4e28671.png
[df9b26898f4740a2af8e612011f51662.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/01d997fbc55d4b3fbbc9af15c20c2116.png
[9e9eadf0734249eca020f216a58146eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0cf3a310f3074fa0a38923b7828e92b4.png
[8d012c98ef704b798dbde49b81cb8240.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2d94d8f9578541f28a6f34e1e95ecd63.png