Queue接口代表的是先进先出（FIFO）队列操作。

Deque接口代表是双向队列操作。

Stack接口是老旧的栈接口，可以用Deque接口实现，即双向队列可以很容易的实现栈的操作，即后进先出（LIFO）

Deuque有两种常见实现，ArrayDeque 和LinkedList ，另外Queue 还有一个单独的常见实现 优先级队列，PriorityQueue；

类图如下：

image.png

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() + " ");
        }
    }

END