Java中的集合（三）继承Collection的Queue接口
一、Queue介绍
Queue接口继承自Collection接口，是Java中定义的一种队列数据结构，元素是有序的（按插入顺序排序），先进先出（FIFO）原则。不支持随机访问数据，新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
队列：是计算机中的一种数据结构，保存在其中的数据具有“先进先出（FIFO,First In First Out）”的特性，新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
在Java中，队列分为2种形式，一种是单队列，一种是循环队列；
通常，都是使用数组来实现队列，假定数组的长度为5，也就是队列的长度为5；
（一）、单队列：
1、创建一个长度为5的空数组，定义两个属性front、rear，分别代表着头指针和尾指针。
2、向数组中插入数据
3、移除头部元素：元素1、元素2
4、再向数组中插入数据，此时rear指向一个不存在的下标
此时，数组就会出现“假溢出”的现象，尾指针指向了一个不存在的下标，如果要解决这种情况，一般有两种方法：
1、无限扩充数组容量；
2、使用循环队列。
（二）、循环队列
当尾指针指向了一个不存在的下标时，即超过数组大小时，此时我们判断数组头部是否有空余的空间，如果有就把尾指针指向头部空余的空间，如下图：
循环队列就是将单队列的头尾相连，形成一个圆形，这样就不会出现下标溢出的现象（distruptor实现）。
二、Queue类图
1、Queue接口继承自Collection接口；
2、Queue接口分别有Deque子接口和AbstractQueue抽象类；
3、Deque子接口分别有LinkedList类和ArrayDeque类；
4、AbstractQueue抽象类有PriorityQueue实现类
三、Deque（Double-ended queue）接口
Deque接口是Queue接口的子接口，创建了双端队列结构，灵活性更强，可以前向或后向迭代，在队头队尾均可插入或删除元素的线性集合。它的两个主要实现类是ArrayDeque和LinkedList。
Deque接口支持容量固定的双端队列，也支持容量不固定的双端队列，一般情况下，双端队列的容量是不固定的。
（一）、特点
1、插入、删除、获取操作支持两种形式：快速失败和返回null或true/false；
2、既具有FIFO（First in, First out，先进先出）特性，又具有LIFO（Last in, First out，后进先出）特性；
3、不推荐插入null，因为null作为返回值表示队列为空；
4、未定义基于元素的equals和hashCode；
5、不支持索引访问元素；
6、Deque不仅是双端队列，还可以当做栈来使用，因为该类定义了pop（出站）,push（入栈）等方法。
（二）、Deque接口与Queue接口、Stack的关系
从上面描述可以知道，Deque不仅可以当做双端队列使用，还可以当做栈来使用。
1、Deque当做双端队列使用时，Deque接口与Queue接口的关系
当 Deque 当做 Queue队列使用时（FIFO），添加元素是添加到队尾，删除时删除的是头部元素。从 Queue 接口继承的方法对应Deque 的方法如图所示：
2、Deque当做栈使用时，Deque接口与Stack的关系
当Deque 当做Stack栈用（LIFO）。这时入栈、出栈元素都是在 双端队列的头部 进行。Deque 中和Stack对应的方法如图所示：
注意：由于Stack比较古老，功能实现非常不友好，现在已经基本不适用程序开发，因此可以选择Deque接口代替Stack进行栈操作。
四、ArrayDeque实现类
Deque接口下分别有两个实现类，分别为ArrayDeque和LinkedList，LinkedList在本节暂不讲述，这节主要讲述ArrayDeque。
（一）、ArrayDeque：基于循环数组实现的线性双端队列，大小可变，不允许null。
1、底层是通过数组实现的，数组大小默认是16，可以指定长度，也可不指定，根据添加元素的个数，动态扩容数组容量。可以为了满足可以同时插入和删除元素，需要该数组必须是循环数组，也就是数组中的每一个点都可以看成是起点或者终点。
2、ArrayDeque是线程不安全的，在多线程环境下，需要手动同步；另外，ArrayDeque不允许插入null元素。
3、由于ArrayDeque是基于头尾指针来实现Deque的，所以不能直接访问第一个和最后一个元素，如果想要遍历元素，需要使用Iterator迭代器，可以使用正反迭代遍历元素。
4、ArrayDeque一般优于链表队列/双端队列，有限数量的垃圾产生（旧数组将被丢弃在扩展），建议使用deque，ArrayDeque优先。
（二）、ArrayDeque操作简图
假定数组的长度为6，也就是ArrayDeque队列的长度为6；
从上面图中可以看出：front总是指向数组中的第一个有效元素的位置，rear终是指向第一个可以可以插入元素的空间位置，所以front并一定等于0，且不总会比rear大，rear也不总是比front小。
（三）、ArrayDeque中，循环数组的实现
ArrayDeque维护了两个属性，分别指向头指针和尾指针：
transient int head; // 指向头指针
transient int tail; // 指向尾指针
假定数组的长度为10，也就是ArrayDeque队列的长度为10；
1、ArrayDeque刚创建时；
2、当向尾部插入时，直接在tail下标的位置插入元素，所以tail下标 + 1，head小标不变；
3、当从头部插入时，head下标 – 1，然后插入元素，tail下标为当前数组末尾元素的下标不变；
通过上面的步骤可以知道，将ArrayDeque看出成是一个首尾相接的圆形数组更好理解循环数组的含义。
通过addFrist（E e）代码，看看ArrayQueue是如何实现的：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
-
- 当加入元素时，先看是否为空（ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在）。然后head-1，插入元素。
- head = (head – 1) & (elements.length – 1)很好的解决了下标越界的问题。这段代码相当于取模，同时解决了head为负值的情况。因为elements.length必需是2的指数倍（代码中有具体操作），elements – 1就是二进制低位全1，跟head – 1相与之后就起到了取模的作用。如果head – 1为负数，其实只可能是-1，当为-1时，和elements.length – 1进行与操作，这时结果为elements.length – 1。其他情况则不变，等于它本身。
- 当插入元素后，在进行判断是否还有余量。因为tail总是指向下一个可插入的空位，也就意味着elements数组至少有一个空位，所以插入元素的时候不用考虑空间问题。
（四）、扩容函数doubleCapacity()
扩容函数doubleCapacity()的逻辑是：申请一个更大容量的数组，将原数组原样复制到新数组中。
从上图可以看出，复制分为两次进行：先复制head右边的元素，然后再复制head左边的元素。
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
elements = (E[])a;
head = 0;
tail = n;
}
（五）、小结
通过上面描述，我们便理解了ArrayDeque循环数组添加以及扩容的过程，另外需要注意的是：ArrayDeque不是线程安全的。 当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。
五、PriorityQueue实现类
（一）、PriorityQueue：底层基于数组实现的堆结构的优先队列。
PriorityQueue是AbstractQueue的子类，AbstractQueue又实现了Queue接口，所以PriorityQueue具有Queue接口的优先队列。
优先队列与普通队列不同，普通队列遵循“FIFO”的特性，获取元素时根据元素的插入顺序获取，优先队列获取元素时根据元素的优先级，获取优先级最高的数据。
（二）、PriorityQueue的排序方式
PriorityQueue保存队列元素时不是按照插入队列顺序进行排序，而是按照插入元素的大小进行排序的。因此当调用peek()、pop()方法时，不是取出最先插入的元素，而是取出队列当中最小元素。
1、排序的方式
PriorityQueue队列当中的元素是可以默认自然排序（数值型元素默认是最小的在队列头部，字符串则按字典序排序），或者通过Comparator（比较器）在队列实例化指定排序方式。
注意：当PriorityQueue中没有指定Comparator时，加入PriorityQueue的元素必须实现了Comparable接口（即元素是可比较的），否则会导致 ClassCastException。
（三）、PriorityQueue的本质
PriorityQueue本质是一个动态数组，默认实现由三种构造方法：
- public PriorityQueue() 调用无参构造方法时，使用默认的初始容量（
DEFAULT_INITIAL_CAPACITY=11）来创建PriorityQueue，并根据其自然顺序排序其中的元素（排序方式使用的是元素中实现的Comparable接口）； - public PriorityQueue(int initialCapacity) 调用指定容量构造方法时，使用initialCapacity定义初始容量创建PriorityQueue，并根据其自然顺序排序其中的元素（排序方式使用的是元素中实现的Comparable接口）；
- PriorityQueue(int initialCapacity,Comparator<? super E> comparator) 当使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。
从上面的三个构造函数可以得出：PriorityQueue内部维护了一个动态数组，
除此之外，还要注意：
-
- PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类。
- 不允许插入 null 元素。
- PriorityQueue实现插入方法（offer、poll、remove() 和 add 方法） 的时间复杂度是O(log(n)) ；实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ；实现检索方法（peek、element 和 size）的时间复杂度是O(1)。所以在遍历时，若不需要删除元素，则以peek的方式遍历每个元素。
- 方法iterator()中提供的迭代器并不保证以有序的方式遍历优PriorityQueue中的元素。
（四）、自然排序和Comparator比较器
1、Java中的两种比较器：Conparator和Comparable
Comparable和Comparator接口都是为了对类进行比较，众所周知，诸如int，double等基本数据类型，Java可以对他们进行比较，而对于对象即类的比较，需要人工定义比较用到的字段比较逻辑。可以把Comparable理解为内部比较器，而Comparator是外部比较器：
（1）、Comparable接口：内部比较器，实现了Comparable接口的类需要实现compareTo(T o)方法，传入一个外部参数进行比对；
当一个对象调用该compareTo(T o)方法与另一个对象比较时，例如o1.compareTo(o2)
- 如果该方法返回0，则表明两个对象相等；
- 如果该方法返回一个整数，则表明o1大于o2；
- 如果该方法返回一个负整数，则表明o1小于o2。
（2）、Conparator接口：外部比较器，实现了Comparator接口的方法需要实现compare(T o1，T o2)方法，对外部传入的两个类进行比较，从而让外部方法在比较时调用；
该compare(T o1，T o2)方法用于比较o1,o2的大小：
- 如果该方法返回正整数，则表明o1大于o2；
- 如果该方法返回0，则表明o1等于o2;
- 如果该方法返回负整数，则表明o1小于o2。
2、自然排序
自然排序是调用元素所属类的compareTo(T o)方法来比较元素之间的大小关系，然后将集合元素按升序排列，即把通过compareTo(T o)方法比较后比较大的的往后排。这种方式就是自然排序。
