Collection子接口之Queue

Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。 Queue接口下面又一个子接口Deque，是双端队列， 在队列的两端均可以插入或删除元素。

ArrayDeque和LinkedList实现了Deque接口，PriorityQueue和LinkedList实现了Queue接口。下面主要介绍ArrayDeque和PriorityQueue两个类。

ArrayDeque

从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的(not thread-safe)，当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。

如上图所示，head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位。因为是循环数组，所以head不一定总等于0，tail也不一定总是比head大。

ProorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。 元素大小的评判可以通过元素本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器。

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

其特点总结如下：

• PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。

• PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。

• PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。

• PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

参考资料

1. https://pdai.tech/md/java/collection/java-collection-PriorityQueue.html
2. https://javaguide.cn/java/collection/java-collection-questions-01