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

Deque接口代表是雙向隊列操作。

Stack接口是老舊的棧接口，可以用Deque接口實現(xiàn)，即雙向隊列可以很容易的實現(xiàn)棧的操作，即后進先出（LIFO）

Deuque有兩種常見實現(xiàn)，ArrayDeque 和LinkedList ，另外Queue 還有一個單獨的常見實現(xiàn) 優(yōu)先級隊列，PriorityQueue；

類圖如下：

image.png

Queue

隊列非常簡單，只有六個操作要求

offer/peek/poll   //取元素如果不存在，返回null
add/remove/element //取元素如果不存在，或者remove的時候已經(jīng)為空,拋異常。

queue通常要求元素不為null，避免和peek poll 返回的null混淆。但是LinkedList作為實現(xiàn)，并沒有準守這個約定，但是使用者使用的時候應該自己加以注意。

Queue也沒有要求定義基于元素的hashCode和equals， 一般直接使用繼承于Object的實現(xiàn)，因為就算兩個Queue的元素都一樣，但是順序屬性也可能不一樣。

Deque

Deque是運行兩端進行隊列操作，有十二個常見的操作。即在Queue的六個操作的基礎上，區(qū)分成頭部操作和尾部操作。

另外Deque 繼承Queue，依然提供了Queue的六個操作。 這個六個操作選擇在Deque的頭部取元素，尾部放元素。

Deque 也提供了 pop/push 和peek 配合 實現(xiàn)棧的操作， 由于peek是Queue操作，是在頭部取元素，自然push和pop 也是對應為在頭部放 和 取元素。

另外還提供了removeFirstOccurrence 和removeLastOccurrence 刪除內(nèi)部元素。

Deque是不支持索引訪問的，只可以迭代。

ArrayDeque

ArrayDeque是用一個循環(huán)數(shù)組實現(xiàn)，需要兩個指針記錄頭和尾，最好有一個哨兵，不過JDK沒有使用哨兵。對于數(shù)組，head 和 tail 分別記錄當前頭部和尾部，默認數(shù)組大小是16，添加元素的時候不用擔心越界，因為每當數(shù)組要滿的時候，就進行會擴容操作。 擴容是直接把大小翻倍。

由于是循環(huán)隊列，tail 可能會循環(huán)繞到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;
    }

值得注意的是，一些循環(huán)遍歷的時候，都沒有使用計數(shù)法，而是判斷元素是否為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;
    }

這是因為這個數(shù)組永遠不會滿，因此結尾一定有null。雖然內(nèi)部有實現(xiàn)迭代器，可見JDK的優(yōu)化程度極高。

LinkedList

這個是雙向鏈表實現(xiàn)List，也不需要擴容，在頭尾指針上進行操作即可。

PriorityQueue

優(yōu)先級隊列，在添加元素的時候給元素指定順序，按照比較器或者Comparable進行排序。 這里很容易就聯(lián)想到SortedSet和SortedMap的實現(xiàn)，TreeMap和TreeSet，實際上二叉搜索樹 是可以實現(xiàn)一個優(yōu)先級隊列，如果是一個平衡性比較好的書，可以在找節(jié)點的時候復雜度降低。因此紅黑樹，AVL樹，伸展樹都是不錯的選擇。

然而，二叉堆是一個更好的選擇， 然而優(yōu)先級隊列還有更好的選擇，二叉堆實現(xiàn)。

默認是最小堆，也可以使用相反的，詳細見 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