在开始很重要的集合Map的学习之前，我们先学习一下集合Queue，主要介绍一下集合Queue的几个重要的实现类。虽然它的内容不多，但它牵涉到了极其重要的数据结构：队列。所以这次主要针对队列这种数据结构的使用来介绍Queue中的实现类。
队列
队列与栈是相对的一种数据结构。只允许在一端进行插入操作，而在另一端进行删除操作的线性表。栈的特点是后进先出，而队列的特点是先进先出。队列的用处很大，但大多都是在其他的数据结构中，比如，树的按层遍历，图的广度优先搜索等都需要使用队列做为辅助数据结构。
单向队列
单向队列比较简单，只能向队尾添加元素，从队头删除元素。比如最典型的排队买票例子，新来的人只能在队列后面，排到最前边的人才可以买票，买完了以后，离开队伍。这个过程是一个非常典型的队列。
定义队列的接口：public interface Queue { public boolean add(Object elem); // 将一个元素放到队尾，如果成功，返回true public Object remove(); // 将一个元素从队头删除，如果成功，返回true}复制代码 一个队列只要能入队，和出队就可以了。这个队列的接口就定义好了，具体的实现有很多种办法，例如，可以使用数组做存储，可以使用链表做存储。
其实大家页可以看一下JDK源码，在java.util.Queue中，可以看到队列的定义。只是它是泛型的。基本上，Queue.java中定义的接口都是进队，出队。只是行为有所不同。例如，remove如果失败，会抛出异常，而poll失败则返回null,但它俩其实都是从队头删除元素。双向队列
如果一个队列的头和尾都支持元素入队，出队，那么这种队列就称为双向队列，英文是Deque。大家可以通过java.util.Deque来查看Deque的接口定义，这里节选一部分：
public interface Dequeextends Queue { /** * Inserts the specified element at the front of this deque if it is * possible to do so immediately without violating capacity restrictions, * throwing an {@code IllegalStateException} if no space is currently * available. When using a capacity-restricted deque, it is generally * preferable to use method {@link #offerFirst}. * * @param e the element to add * @throws IllegalStateException if the element cannot be added at this * time due to capacity restrictions * @throws ClassCastException if the class of the specified element * prevents it from being added to this deque * @throws NullPointerException if the specified element is null and this * deque does not permit null elements * @throws IllegalArgumentException if some property of the specified * element prevents it from being added to this deque */ void addFirst(E e); void addLast(E e); E removeFirst(); E removeLast();}复制代码
最重要的也就是这4个，一大段英文，没啥意思，其实就是说，addFirst是向队头添加元素，如果不满足条件就会抛异常，然后定义了各种情况下抛出的异常类型。
只要记住队列是先进先出的数据结构就好了，今天不必要把这些东西都掌握，一步步来。Queue
Queue也继承自Collection，用来存放等待处理的集合，这种场景一般用于缓冲、并发访问。我们先看一下官方的定义和类结构：
/** * A collection designed for holding elements prior to processing. * Besides basic {@link java.util.Collection Collection} operations, * queues provide additional insertion, extraction, and inspection * operations. Each of these methods exists in two forms: one throws * an exception if the operation fails, the other returns a special * value (either {@code null} or {@code false}, depending on the * operation). The latter form of the insert operation is designed * specifically for use with capacity-restricted {@code Queue} * implementations; in most implementations, insert operations cannot * fail. */复制代码 意思大体说Queue是用于在处理之前保存元素的集合。 除了基本的集合操作，队列提供了额外的插入、提取和检查操作。 每个方法都有两种形式:一种是在操作失败时抛出一个异常，另一个则返回一个特殊值(根据操作的不同)(返回null或false)。 插入操作的后一种形式是专门为有容量限制的队列实现而设计的; 在大多数实现中，插入操作不会失败。
public interface Queueextends Collection { //插入（抛出异常） boolean add(E e); //插入（返回特殊值） boolean offer(E e); //移除（抛出异常） E remove(); //移除（返回特殊值） E poll(); //检查（抛出异常） E element(); //检查（返回特殊值） E peek();}复制代码
可以看出Queue接口没有什么神秘面纱，都不需要揭开。不存在花里胡哨，就只有这6个方法。额外的添加、删除、查询操作。
值得一提的是，Queue是个接口，它提供的add，offer方法初衷是希望子类能够禁止添加元素为null，这样可以避免在查询时返回null究竟是正确还是错误。实际上大多数Queue的实现类的确响应了Queue接口的规定，比如ArrayBlockingQueue，PriorityBlockingQueue等等。 但还是有一些实现类没有这样要求，比如LinkedList。 虽然 LinkedList 没有禁止添加 null，但是一般情况下 Queue 的实现类都不允许添加 null 元素，为啥呢？因为poll(),peek()方法在异常的时候会返回 null，你添加了null 以后，当获取时不好分辨究竟是否正确返回。PriorityQueue
PriorityQueue又叫做优先级队列，保存队列元素的顺序不是按照及加入队列的顺序，而是按照队列元素的大小进行重新排序。因此当调用peek()或pool()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列的最小元素。
我们刚刚才说到队列的特点是先进先出，为什么这里就按照大小顺序排序了呢？我们还是先看一下它的介绍，直接翻译过来：基于优先级堆的无界的优先级队列。PriorityQueue的元素根据自然排序进行排序，或者按队列构建时提供的 Comparator进行排序，具体取决于使用的构造方法。优先队列不允许 null 元素。通过自然排序的PriorityQueue不允许插入不可比较的对象。该队列的头是根据指定排序的最小元素。如果多个元素都是最小值，则头部是其中的一个元素——任意选取一个。队列检索操作poll、remove、peek和element访问队列头部的元素。优先队列是无界的，但有一个内部容量，用于管理用于存储队列中元素的数组的大小。基本上它的大小至少和队列大小一样大。当元素被添加到优先队列时，它的容量会自动增长。增长策略的细节没有指定。复制代码
一句话概括，PriorityQueue使用了一个高效的数据结构：堆。底层是使用数组保存数据。还会进行排序，优先将元素的最小值存到队头。
PriorityQueue的排序方式
PriorityQueue中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化时指定的排序方式进行排序。关于自然排序与Comparator（比较器）可以参考我的上一篇文章的讲解。所以这里的用法就不复述了。
需要注意的是，当PriorityQueue中没有指定的Comparator时，加入PriorityQueue的元素必须实现了Comparable接口（元素是可以进行比较的），否则会导致 ClassCastException。PriorityQueue本质
PriorityQueue 本质也是一个动态数组，在这一方面与ArrayList是一致的。看一下它的构造方法：
public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }public PriorityQueue(Comparator comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); }public PriorityQueue(int initialCapacity, Comparator comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }复制代码 - PriorityQueue调用默认的构造方法时，使用默认的初始容量（
DEFAULT_IITIAL_CAPACITY = 11）创建一个PriorityQueue，并根据其自然顺序来排序其元素（使用加入其中的集合元素实现的Comparable）。 - 当使用指定容量的构造方法时，使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用加入其中的集合元素实现的Comparable）
- 当使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。当添加元素到集合时，会先检查数组是否还有余量，有余量则把新元素加入集合，没余量则调用 grow()方法增加容量，然后调用siftUp将新加入的元素排序插入对应位置。 除了这些，还要注意的是： 1.PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类。 2.不允许插入 null 元素。 3.PriorityQueue实现插入方法（offer、poll、remove() 和 add 方法） 的时间复杂度是O(log(n)) ；实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ；实现检索方法（peek、element 和 size）的时间复杂度是O(1)。所以在遍历时，若不需要删除元素，则以peek的方式遍历每个元素。 4.方法iterator()中提供的迭代器并不保证以有序的方式遍历PriorityQueue中的元素。
Deque
Deque接口是Queue接口子接口。它代表一个双端队列。Deque接口在Queue接口的基础上增加了一些针对双端添加和删除元素的方法。LinkedList也实现了Deque接口，所以也可以被当作双端队列使用。也可以看前面的 来理解Deque接口。
先瞄一眼类结构：public interface Dequeextends Queue { //从头部插入（抛异常） void addFirst(E e); //从尾部插入（抛异常） void addLast(E e); //从头部插入（特殊值） boolean offerFirst(E e); //从尾部插入（特殊值） boolean offerLast(E e); //从头部移除（抛异常） E removeFirst(); //从尾部移除（抛异常） E removeLast(); //从头部移除（特殊值） E pollFirst(); //从尾部移除（特殊值） E pollLast(); //从头部查询（抛异常） E getFirst(); //从尾部查询（抛异常） E getLast(); //从头部查询（特殊值） E peekFirst(); //从尾部查询（特殊值） E peekLast(); //（从头到尾遍历列表时，移除列表中第一次出现的指定元素） boolean removeFirstOccurrence(Object o); //（从头到尾遍历列表时，移除列表中最后一次出现的指定元素） boolean removeLastOccurrence(Object o); //都没啥难度，不解释了 boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); void push(E e); E pop(); boolean remove(Object o); boolean contains(Object o); public int size(); Iterator iterator(); Iterator descendingIterator();}复制代码
从上面的方法可以看出，Deque不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类中还包含了pop(出栈)、push(入栈)两个方法。其他基本就是方法名后面加上“First”和“Last”表明在哪端操作。
ArrayDeque
重头戏来了，顾名思义，ArrayDeque使用数组实现的Deque;底层是数组，也是可以指定它的capacity,当然也可以不指定，默认长度是16，根据添加的元素个数，动态扩容。
循环队列
值得重点介绍的是，ArrayDeque是一个循环队列。它的实现比较高效，它的思路是这样：引入两个游标，head 和 tail，如果向队列里，插入一个元素，就把 tail 向后移动。如果从队列中删除一个元素，就把head向后移动。我们看一下示意图：
扩容
所有的集合类都会面临一个问题，那就是如果容器中的空间不够了怎么办。这就涉及到扩容的问题。在前面我们已经说了，我们要保证数组的长度都是2的整数次幂，那么扩容的时候也很简单，直接把原来的数组长度乘以2就可以了。申请一个长度为原数组两倍的数组，然后把数据拷贝进去就OK了。我们看一下具体代码：
private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; 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 = a; head = 0; tail = n; }复制代码 代码没啥难度，先把长度扩一倍，（n<<1），再把数据拷到目标位置。只要把这两个arraycopy方法看懂问题不大。
总个小结
- 当 Deque 当做 Queue队列使用时（FIFO），添加元素是添加到队尾，删除时删除的是头部元素
- Deque 也能当Stack栈用（LIFO）。这时入栈、出栈元素都是在 双端队列的头部进行。插一嘴：Stack过于古老，并且实现地非常不好，因此现在基本已经不用了，可以直接用Deque来代替Stack进行栈操作。
- ArrayDeque不是线程安全的。 当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。
- 最后，送上一个笑话。栈和队列有什么区别？吃多了拉就是队列，吃多了吐就是栈。冬幕节快乐~