雙端隊列

雙端隊列是一個很有意思的話題。在講并發(fā)雙端隊列之前，我們需要介紹一個非并發(fā)的ArrayDequeue， 讓大家理解雙端隊列的一些原理。

• ArrayDeque不是線程安全的。
• ArrayDeque不可以存取null元素，因為系統(tǒng)根據(jù)某個位置是否為null來判斷元素的存在。
• 當(dāng)作為棧使用時，性能比Stack好；當(dāng)作為隊列使用時，性能比LinkedList好。

從 ArrayDeque 命名就能看出他的實現(xiàn)基于數(shù)組（LinkedList 是基于鏈表實現(xiàn)的雙端隊列），但是 ArrayDeque 的數(shù)組是一個可擴(kuò)容動態(tài)數(shù)組，每次隊列滿了就會進(jìn)行擴(kuò)容，除非擴(kuò)容至 int 邊界才會拋出異常，ArrayDeque 不允許元素為 null。ArrayDeque 的主要成員是一個 elements 數(shù)組和 int 的 head 與 tail 索引，head 是隊列的頭部元素索引，而 tail 是隊列下一個要添加的元素的索引，elements 的默認(rèn)容量是 16 且默認(rèn)容量必須是 2 的冪次，不足 2 的冪次會自動向上調(diào)整為 2 的冪次。

訪問隊列頭部元素但不刪除

• ArrayDeque 獲取隊列頭部元素的 element()\getFirst()\peek()\peekFirst() 操作，其都是調(diào)用 getFirst() 實現(xiàn)的，訪問隊列頭部元素但不刪除，即如下

    public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

• ArrayDeque 刪除隊列頭部元素的 remove()\removeFirst()\poll()\pollFirst() 操作，其都是調(diào)用 pollFirst() 實現(xiàn)的，移除隊列頭部元素且返回被移除的元素，即如下

    public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }

• ArrayDeque 添加元素到隊列尾部的操作可以發(fā)現(xiàn) add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是調(diào)用 addLast(E e) 實現(xiàn)的，即如下：

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

addLast 的實現(xiàn)原理

也就是那句 if 操作與雙倍擴(kuò)容到底是做了什么我們先看下不擴(kuò)容情況下 ArrayDeque 相關(guān)操作的圖解，如下：

正如上圖中最后的多次操作結(jié)果所示，如果此時我們再 add 操作一個元素到 tail 索引處則 tail+1 會變成 8 導(dǎo)致數(shù)組越界，理論上來說這時候應(yīng)該進(jìn)行擴(kuò)容操作了，但是由于下標(biāo)為 0、1、2、3 處沒有存儲元素，直接擴(kuò)容有些浪費（ArrayList 為了避免浪費是通過拷貝將刪除之后的元素整體前挪一位），所以為了高效利用數(shù)組中現(xiàn)有的剩余空間就有了 addLast(E e) 中的代碼 (tail = (tail + 1) & (elements.length - 1));

實質(zhì)類似上面 pollFirst() 里面 head 操作，即假設(shè) elements 默認(rèn)初始化長度是 8，則當(dāng)前 tail + 1（8=1000）按位與上數(shù)組長度減一（7=0111）的結(jié)果為十進(jìn)制的 0，所以下一個被 addLast(E e) 的元素實際會放在索引為 0 的位置，再下一個會放在索引為 1 的位置，如下圖：

問題

(tail = (tail + 1) & (elements.length - 1)) 這個哪里見過，是不是在LongAdder里線程probe找cell 那個邏輯？ 這句話實際上就是對element.length 取余

可以看到，隨著出隊入隊不斷操作，如果 tail 移動到 length-1 之后數(shù)組的第一個位置 0 處沒有元素則需要將 tail 指向 0，依次循環(huán)，當(dāng) tail 如果等于 head 時說明數(shù)組要滿了，接下來需要進(jìn)行數(shù)組擴(kuò)容，所以就有了上面 addLast(E e) 里面那個 if 判斷的邏輯去觸發(fā) doubleCapacity()。

因此這也就解釋了為什么 ArrayDeque 的初始容量必須是 2 的冪次（擴(kuò)容每次都是成倍的，所以自然也滿足 2 的冪次），因為只有容量為 2 的冪次時 ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二進(jìn)制最高位永遠(yuǎn)為 0，當(dāng) (tail + 1) 與其按位與操作時才能保證循環(huán)歸零置位。ArrayDeque 的 doubleCapacity() 擴(kuò)容操作的實現(xiàn)，如下：

    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;
    }

以上就是java雙端隊列之ArrayDequeue原理講解的詳細(xì)內(nèi)容，更多關(guān)于java雙端隊列ArrayDequeue的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論