菜鳥看源碼之ArrayDeque

先扯點别的：今天上海風不小，現在窗外依然是狂風嗚咽，不禁讓人想起山科的風。

今天分析一下ArrayDeque的源碼

ArrayDeque的繼承關系圖

菜鳥看源碼之ArrayDeque

ArrayDeque

實作了

Deque

接口，内部使用一個可調整大小的數組來存放元素。數組沒有容量限制，必要的時候數組的容量會增加。

ArrayDeque

不是線程安全的。不允許添加

Null

元素。當

ArrayDeque

作為一個棧來使用的時候，

ArrayDeque

可能會比

Stack

快。當

ArrayDeque

作為隊列使用的時候，可能會比

LinkedList

速度要快。

看一下ArrayDeque中幾個成員變量

//儲存元素的數組，長度總是2的次幂，數組不允許飽和，在使用addX方法添加元素以後，如果數組飽和了，那麼就會立即擴容到原來長度的兩倍
transient Object[] elements;
//雙端隊列的頭部元素的下标
transient int head;
//标志：如果一個新元素要被添加到雙端隊列尾部(通過 addLast(E), add(E), or push(E))，那麼這個新元素在雙端隊列的下标就是tail
transient int tail;
//elements最小初始容量，如果構造函數指定初始容量下限小于8，那麼就選擇8作為初始容量
private static final int MIN_INITIAL_CAPACITY = ;

構造函數

public ArrayDeque() {
        elements = new Object[];
    }

//指定初始容量下限，最終初始容量是大于等于numElements并且是2的次幂的一個數，比如指定numElements=9，那麼初始容量最終會是16
public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

//使用一個集合初始化隊列
public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

我們指定隊列的初始容量為8，然後來看看常用的方法

addFirst(E e) 把元素插入到隊列的前面

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

可以看到元素是不允許為null的，初始的時候

head

和

tail

都是0，elements.length=8。

ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i = ; i < ; i++) {
            deque.addFirst(i);
        }

添加第一個元素，表達式

head = (head - 1) & (elements.length - 1)

就等價于

(-1&7)=7

,是以

elements[7]=0

。

中間插一句,關于按位與（&）和按位或（|）操作不清楚的可以看一看原碼, 反碼, 補碼詳解

插入以後 head=7,不等于tail，不需要擴容

添加第二個元素，表達式

head = (head - 1) & (elements.length - 1)

就等價于

(6&7)=6

,是以

elements[6]=1

。當我們添加完第8個元素時，

elements=[7,6,5,4,3,2,1,0]

,這時，head=0,head=tail,這時候需要擴容

doubleCapacity()

，這個方法的作用就是把

elements

長度增加兩倍，然後使用

System.arraycopy()

方法重新放置元素，我們在後面會進行詳細分析。

addLast(E e) 把元素插入到隊列的尾部

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

ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i = ; i < ; i++) {
            deque.addLast(i);
        }

這個方法和

addFirst(E e)

正好是相反的，添加完8個元素以後，

elements=[0,1,2,3,4,5,6,7]

offerFirst(E e) 内部調用addFirst(e)方法實作，不再贅述

public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

offerLast(E e) 内部調用addLast(e)方法實作，不再贅述

public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

pollFirst() 查詢第一個元素

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 + ) & (elements.length - );
        return result;
    }

當隊列為空的時候，傳回null。不為空時，删除并傳回head下标上的元素，然後把head向後移動一個位置。

* pollLast() 查詢最後一個元素

public E pollLast() {
        int t = (tail - ) & (elements.length - );
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

當隊列為空的時候，傳回null。不為空時，删除并傳回最後一個元素，然後把tail向前移動一個位置。

removeFirst() 内部調用pollFirst(),如果元素為null，則抛出異常

public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

removeLast() 内部調用pollLast(),如果元素為null，則抛出異常

public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

下面幾個方法比較簡單一起說了

//傳回隊列第一個元素，但是不删除，如果為null，怎抛出異常
public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

//傳回隊列最後一個元素，但是不删除，如果為null，怎抛出異常
    public E getLast() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[(tail - ) & (elements.length - )];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }
//傳回隊列第一個元素，但是不删除，傳回值可以為null
    @SuppressWarnings("unchecked")
    public E peekFirst() {
        // elements[head] is null if deque empty
        return (E) elements[head];
    }
//傳回隊列最後一個元素，但是不删除，傳回值可以為null
    @SuppressWarnings("unchecked")
    public E peekLast() {
        return (E) elements[(tail - ) & (elements.length - )];
    }

removeFirstOccurrence(Object o) 删除隊列中第一個和指定元素相等的元素，從head到tail周遊。如果指定元素為null，或者删除失敗傳回false，删除成功傳回true。

public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - ;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                //調用delete删除,delete方法通過移動elelemts中的元素，來覆寫要删除位置上的元素，并對移動元素做了相關優化，并相應的改變head和tail
                delete(i);
                return true;
            }
            i = (i + ) & mask;
        }
        return false;
    }

removeLastOccurrence(Object o) 删除隊列中最後一個和指定元素相等的元素

public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - ;
        int i = (tail - ) & mask;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i - ) & mask;
        }
        return false;
    }

*分析一下 doubleCapacity() 增加elements容量為原來的兩倍，重新放置元素

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 << ;
        if (newCapacity < )
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, , r);
        System.arraycopy(elements, , a, r, p);
        elements = a;
        head = ;
        tail = n;
    }

這個方法中為什麼

System.arraycopy()

方法為什麼要調用兩次呢，下面來分析一下。

首先這個方法調用的地方有兩個，addFirst()和addLast()

第一種情況：隻使用addFirst()方法添加元素，當我們添加完了第8個元素，此時

elements=[7,6,5,4,3,2,1,0]

,需要進行擴容了

此時

head = tail=0;

p=0;

n=8;

r=8;

首先把數組容量增加兩倍，然後

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=0

拷貝到a中，一共拷貝

r=8

個元素，a從下标為0開始放置元素

//第二次拷貝因為

p=0

，是以并不會改變a。

System.arraycopy(elements, 0, a, r, p);

最後讓elements指向a。拷貝完成後

elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,null]

head=0,tail=8

;

再用addFirst()方法添加一個元素8，結果

elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,8]

再用addFirst()方法添加一個元素9，結果

elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,9,8]

當我們繼續添加元素

elements=[7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8]

，此時數組滿了又需要擴容了

此時

head == tail=8;

p=8;

n=16;

r=8;

首先把數組容量增加兩倍，然後

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=8

拷貝到a中，一共拷貝

r=8

個元素，a從下标為0開始放置元素

拷貝完成後

a=[15,14,13,12,11,10,9,8,...]

//第二次拷貝

p=8

，會把elements中的元素從下标

拷貝到a中，一共拷貝

p=8

個元素，a從下标

r=8

開始放置元素

System.arraycopy(elements, 0, a, r, p);

最後讓elements指向a。拷貝完成後

a=[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,...]

head=0,tail=16

;

插一句,到這裡隐隐感覺到寫這個代碼的人真是厲害，佩服！

第二種情況：隻使用addLast()方法添加元素，當我們添加完了第8個元素，此時

elements=[0,1,2,3,4,5,6,7]

,需要進行擴容了

此時

head = tail=0;

p=0;

n=8;

r=8;

首先把數組容量增加兩倍，然後

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=0

拷貝到a中，一共拷貝

r=8

個元素，a從下标為0開始放置元素

//第二次拷貝因為

p=0

，是以并不會改變a。

System.arraycopy(elements, 0, a, r, p);

最後讓elements指向a。拷貝完成後

elements=[0,1,2,3,4,5,6,7,null,null,null,null,null,null,null,null]

head=0,tail=8

;

再用addLast()方法添加一個元素8，結果

elements=[0,1,2,3,4,5,6,7,8,null,null,null,null,null,null,null]

再用addLast()方法添加個一個元素9，結果

elements=[0,1,2,3,4,5,6,7,8,9,null,null,null,null,null,null]

當我們繼續添加元素

elements=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

，此時數組滿了又需要擴容了

此時

head = tail=0;

p=0;

n=16;

r=16;

首先把數組容量增加兩倍，然後

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=0

拷貝到a中，一共拷貝

r=16

個元素，a從下标為0開始放置元素

//第二次拷貝因為

p=0

，是以并不會改變a。

System.arraycopy(elements, 0, a, r, p);

最後讓elements指向a。拷貝完成後

elements=[0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...]

head=0,tail=16

;

插一句,到這裡深深感覺到寫這個代碼的人真是厲害，佩服！

再分析一種情況

使用addFirst()方法添加元素，當我們添加完了第7個元素，此時

elements=[null,6,5,4,3,2,1,0]

,然後使用addLast()方法添加一個元素7，

此時

elements=[7,6,5,4,3,2,1,0]

然後數組滿了需要擴容

此時

head = tail=1;

p=1;

n=8;

r=7;

數組容量增加兩倍

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=1

拷貝到a中，一共拷貝

r=7

個元素，a從下标為0開始放置元素，拷貝

完成後

a=[6,5,4,3,2,1,0,...]

第二次拷貝

System.arraycopy(elements, 0, a, r, p);

會把elements中的元素從下标0拷貝到a中，一共拷貝

p=1

個元素，a從下标為

r=7

開始放置元素，拷貝完成後

a=[6,5,4,3,2,1,0,7，...]

此時

elements=[6,5,4,3,2,1,0,7，...]

head = 0``tail=8

如果此時繼續用然後使用addLast()添加8個元素

element=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15]

，此時數組飽和，擴容

head = tail=0;

p=0;

n=16;

r=16;

數組容量增加兩倍

System.arraycopy(elements, p, a, 0, r);

會把elements中的元素從下标

p=0

拷貝到a中，一共拷貝

r=16

個元素，a從下标為0開始放置元素，拷貝

完成後

a=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...]

第二次拷貝p=0,a不會改變。

最後

elements=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...]

head = 0``tail=16

結尾：今天是美好的一天，明天也将會使美好的一天。

菜鳥看源碼之ArrayDeque

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method