快捷導(dǎo)航

java雙端隊(duì)列之ArrayDequeue原理講解

更新時(shí)間：2023年06月27日 11:02:02 作者：程序員札記

這篇文章主要為大家介紹了java雙端隊(duì)列之ArrayDequeue原理講解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

雙端隊(duì)列

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

ArrayDeque不是線程安全的。
ArrayDeque不可以存取null元素，因?yàn)橄到y(tǒng)根據(jù)某個(gè)位置是否為null來(lái)判斷元素的存在。
當(dāng)作為棧使用時(shí)，性能比Stack好；當(dāng)作為隊(duì)列使用時(shí)，性能比LinkedList好。

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

訪問(wèn)隊(duì)列頭部元素但不刪除

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

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

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

    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 添加元素到隊(duì)列尾部的操作可以發(fā)現(xiàn) add(E e)\offer(E e)\offerLast(E e)\addLast(E e) 操作都是調(diào)用 addLast(E e) 實(shí)現(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 的實(shí)現(xiàn)原理

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

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

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

問(wèn)題

(tail = (tail + 1) & (elements.length - 1)) 這個(gè)哪里見(jiàn)過(guò)，是不是在LongAdder里線程probe找cell 那個(gè)邏輯？這句話實(shí)際上就是對(duì)element.length 取余

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

因此這也就解釋了為什么 ArrayDeque 的初始容量必須是 2 的冪次（擴(kuò)容每次都是成倍的，所以自然也滿足 2 的冪次），因?yàn)橹挥腥萘繛?2 的冪次時(shí) ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二進(jìn)制最高位永遠(yuǎn)為 0，當(dāng) (tail + 1) 與其按位與操作時(shí)才能保證循環(huán)歸零置位。ArrayDeque 的 doubleCapacity() 擴(kuò)容操作的實(shí)現(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;
    }