Queue接口代表的是先进先出（FIFO）队列操作。
Deque接口代表是双向队列操作。
Stack接口是老旧的栈接口，可以用Deque接口实现，即双向队列可以很容易的实现栈的操作，即后进先出（LIFO）
Deuque有两种常见实现，ArrayDeque 和LinkedList ，另外Queue 还有一个单独的常见实现 优先级队列，PriorityQueue；
类图如下：
Queue
队列非常简单，只有六个操作要求
offer/peek/poll //取元素如果不存在，返回null
add/remove/element //取元素如果不存在，或者remove的时候已经为空,抛异常。
queue通常要求元素不为null，避免和peek poll 返回的null混淆。但是LinkedList作为实现，并没有准守这个约定，但是使用者使用的时候应该自己加以注意。
Queue也没有要求定义基于元素的hashCode和equals， 一般直接使用继承于Object的实现，因为就算两个Queue的元素都一样，但是顺序属性也可能不一样。
Deque
Deque是运行两端进行队列操作，有十二个常见的操作。即在Queue的六个操作的基础上，区分成头部操作和尾部操作。
另外Deque 继承Queue，依然提供了Queue的六个操作。 这个六个操作选择在Deque的头部取元素，尾部放元素。
Deque 也提供了 pop/push 和peek 配合 实现栈的操作， 由于peek是Queue操作，是在头部取元素，自然push和pop 也是对应为在头部放 和 取元素。
另外还提供了removeFirstOccurrence 和removeLastOccurrence 删除内部元素。
Deque是不支持索引访问的，只可以迭代。
ArrayDeque
ArrayDeque是用一个循环数组实现，需要两个指针记录头和尾，最好有一个哨兵，不过JDK没有使用哨兵。对于数组，head 和 tail 分别记录当前头部和尾部，默认数组大小是16，添加元素的时候不用担心越界，因为每当数组要满的时候，就进行会扩容操作。 扩容是直接把大小翻倍。
由于是循环队列，tail 可能会循环绕到head前面，最后等于head，因此要分段拷贝。
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;
}
值得注意的是，一些循环遍历的时候，都没有使用计数法，而是判断元素是否为null。
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
这是因为这个数组永远不会满，因此结尾一定有null。虽然内部有实现迭代器，可见JDK的优化程度极高。
LinkedList
这个是双向链表实现List，也不需要扩容，在头尾指针上进行操作即可。
PriorityQueue
优先级队列，在添加元素的时候给元素指定顺序，按照比较器或者Comparable进行排序。 这里很容易就联想到SortedSet和SortedMap的实现，TreeMap和TreeSet，实际上二叉搜索树 是可以实现一个优先级队列，如果是一个平衡性比较好的书，可以在找节点的时候复杂度降低。因此红黑树，AVL树，伸展树都是不错的选择。
然而，二叉堆是一个更好的选择， 然而优先级队列还有更好的选择，二叉堆实现。
默认是最小堆，也可以使用相反的，详细见 http://www.cs.cornell.edu/courses/cs312/2007sp/lectures/lec25.html
public static void main(String[] args) {
Random r = new Random(System.currentTimeMillis());
PriorityQueue<Integer> q1 = new PriorityQueue<>(Comparator.reverseOrder());
for (int i = 0; i < 20; i++) {
int val = r.nextInt(200);
q1.offer(val);
}
while (!q1.isEmpty()) {
System.out.print(q1.poll() + " ");
}
}
