Queue 集合

Queue 用于模拟 队列(先进先出) 这种数据结构。新元素 插入(offer) 到队列的尾部，访问元素(poll) 会返回队列头部的元素，队列不允许随机访问队列中的元素。

Queue 接口中定义了如下几个方法：

void add(Object e)：将指定元素加入此队列的尾部。
Object element()：获取队列头部的元素，但是不删除该元素。
boolean offer(Object e)：将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比 add(Object e) 方法更好。
Object peek()：获取队列头部的元素，但是不删除该元素。如果队列为空，则返回 null。
Object poll()：获取队列头部的元素，并删除元素。如果队列为空，则返回null。
Object remove()：获取队列头部的元素，并删除元素。

Queue 接口有一个 PriorityQueue 实现类。

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

PriorityQueue 实现类

PriorityQueue 是一个比较标准的队列实现类，保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的从小到大进行重新排序。因此当调用 peek() 或 poll() 方法取出队列中元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。

从以上定义看，PriorityQueue 已经违反了队列的最基本规则：先进先出。

PriorityQueue 不允许插入 null 元素，它还需要对队列元素进行排序，且有两种排序方式：

自然排序：采用自然排序的 PriorityQueue 集合中的元素必须实现了 Comparable 接口，而且应该是同一个类的多个实例，否则会引发 ClassCastException 异常。
定制排序：创建 PriorityQueue 队列时，传入一个 Comparator 对象，该对象负责对队列中的所有元素进行排序。

Deque 接口与 ArrayDeque 实现类

Deque 接口是 Queue 接口的子接口，它代表一个双端队列，允许从队列两端操作队列的元素：

可以看出，Deque 不仅可以当成双端队列使用，还可以被当作栈来使用，因为该类里还包括了 pop(出栈)、push(入栈) 两个方法。

ArrayDeque

Deque 接口提供了一个典型的实现类：ArrayDeque，它是一个基于数组实现的双端队列。创建 Deque 时可指定一个 numElements 参数，用于指定 Object[] 数组的长度。默认底层数组的长度为16。

ArrayDeque stack = new ArrayDeque();
//依次将三个元素 push 入 "栈"，区别于 add/offer 入 "队列"
stack.push("疯狂 Java 讲义");
stack.push("轻量级 Java EE 企业应用实战");
stack.push("疯狂 Android 讲义");
//输出：[ 疯狂 Android 讲义，轻量级 Java EE 企业应用实战，疯狂 Java 讲义]
System.out.println(stack);

当程序中需要使用 “栈” 时，推荐使用 ArrayDeque。

LinkedList 实现类

LinkedList 类是 List 接口的实现类，同时还实现了 Deque 接口，因此可以作为 List集合使用，根据索引来随机访问集合中元素；同时还可以作为栈、队列使用。

LinkedList 与 ArrayList、ArrayDeque 的实现机制完全不同，ArrayList、ArrayDeque 内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而 LinkedList 内部以链表的形式来保存集合元素，因此随机访问集合元素性能较差，但在插入、删除元素时性能出色。