快捷導(dǎo)航

深入剖析Java ArrayQueue(JDK)的源碼

更新時間：2022年08月16日 08:05:51 作者：一無是處的研究僧

本篇文章主要給大家介紹一個比較簡單的JDK為我們提供的容器ArrayQueue，這個容器主要是用數(shù)組實現(xiàn)的一個單向隊列，整體的結(jié)構(gòu)相對其他容器來說就比較簡單了，感興趣的可以了解一下

前言

在本篇文章當中主要給大家介紹一個比較簡單的JDK為我們提供的容器ArrayQueue，這個容器主要是用數(shù)組實現(xiàn)的一個單向隊列，整體的結(jié)構(gòu)相對其他容器來說就比較簡單了。

ArrayQueue內(nèi)部實現(xiàn)

在談ArrayQueue的內(nèi)部實現(xiàn)之前我們先來看一個ArrayQueue的使用例子：

public?void?testQueue()?{
????ArrayQueue<Integer>?queue?=?new?ArrayQueue<>(10);
????queue.add(1);
????queue.add(2);
????queue.add(3);
????queue.add(4);
????System.out.println(queue);
????queue.remove(0);?//?這個參數(shù)只能為0?表示刪除隊列當中第一個元素，也就是隊頭元素
????System.out.println(queue);
????queue.remove(0);
????System.out.println(queue);
}
//?輸出結(jié)果
[1,?2,?3,?4]
[2,?3,?4]
[3,?4]

首先ArrayQueue內(nèi)部是由循環(huán)數(shù)組實現(xiàn)的，可能保證增加和刪除數(shù)據(jù)的時間復(fù)雜度都是，不像ArrayList刪除數(shù)據(jù)的時間復(fù)雜度為。在ArrayQueue內(nèi)部有兩個整型數(shù)據(jù)head和tail，這兩個的作用主要是指向隊列的頭部和尾部，它的初始狀態(tài)在內(nèi)存當中的布局如下圖所示：

因為是初始狀態(tài)head和tail的值都等于0，指向數(shù)組當中第一個數(shù)據(jù)?，F(xiàn)在我們向ArrayQueue內(nèi)部加入5個數(shù)據(jù)，那么他的內(nèi)存布局將如下圖所示：

現(xiàn)在我們刪除4個數(shù)據(jù)，那么上圖經(jīng)過4次刪除操作之后，ArrayQueue內(nèi)部數(shù)據(jù)布局如下：

在上面的狀態(tài)下，我們繼續(xù)加入8個數(shù)據(jù)，那么布局情況如下：

我們知道上圖在加入數(shù)據(jù)的時候不僅將數(shù)組后半部分的空間使用完了，而且可以繼續(xù)使用前半部分沒有使用過的空間，也就是說在ArrayQueue內(nèi)部實現(xiàn)了一個循環(huán)使用的過程。

ArrayQueue源碼剖析

構(gòu)造函數(shù)

public?ArrayQueue(int?capacity)?{
????this.capacity?=?capacity?+?1;
????this.queue?=?newArray(capacity?+?1);
????this.head?=?0;
????this.tail?=?0;
}

@SuppressWarnings("unchecked")
private?T[]?newArray(int?size)?{
????return?(T[])?new?Object[size];
}

上面的構(gòu)造函數(shù)的代碼比較容易理解，主要就是根據(jù)用戶輸入的數(shù)組空間長度去申請數(shù)組，不過他具體在申請數(shù)組的時候會多申請一個空間。

add函數(shù)

public?boolean?add(T?o)?{
????queue[tail]?=?o;
????//?循環(huán)使用數(shù)組
????int?newtail?=?(tail?+?1)?%?capacity;
????if?(newtail?==?head)
????????throw?new?IndexOutOfBoundsException("Queue?full");
????tail?=?newtail;
????return?true;?//?we?did?add?something
}

上面的代碼也相對比較容易看懂，在上文當中我們已經(jīng)提到了ArrayQueue可以循環(huán)將數(shù)據(jù)加入到數(shù)組當中去，這一點在上面的代碼當中也有所體現(xiàn)。

remove函數(shù)

public?T?remove(int?i)?{
????if?(i?!=?0)
????????throw?new?IllegalArgumentException("Can?only?remove?head?of?queue");
????if?(head?==?tail)
????????throw?new?IndexOutOfBoundsException("Queue?empty");
????T?removed?=?queue[head];
????queue[head]?=?null;
????head?=?(head?+?1)?%?capacity;
????return?removed;
}

從上面的代碼當中可以看出，在remove函數(shù)當中我們必須傳遞參數(shù)0，否則會拋出異常。而在這個函數(shù)當中我們只會刪除當前head下標所在位置的數(shù)據(jù)，然后將head的值進行循環(huán)加1操作。

get函數(shù)

public?T?get(int?i)?{
????int?size?=?size();
????if?(i?<?0?||?i?>=?size)?{
????????final?String?msg?=?"Index?"?+?i?+?",?queue?size?"?+?size;
????????throw?new?IndexOutOfBoundsException(msg);
????}
????int?index?=?(head?+?i)?%?capacity;
????return?queue[index];
}

get函數(shù)的參數(shù)表示得到第i個數(shù)據(jù)，這個第i個數(shù)據(jù)并不是數(shù)組位置的第i個數(shù)據(jù)，而是距離head位置為i的位置的數(shù)據(jù)，了解這一點，上面的代碼是很容易理解的。

resize函數(shù)

public?void?resize(int?newcapacity)?{
????int?size?=?size();
????if?(newcapacity?<?size)
????????throw?new?IndexOutOfBoundsException("Resizing?would?lose?data");
????newcapacity++;
????if?(newcapacity?==?this.capacity)
????????return;
????T[]?newqueue?=?newArray(newcapacity);
????for?(int?i?=?0;?i?<?size;?i++)
????????newqueue[i]?=?get(i);
????this.capacity?=?newcapacity;
????this.queue?=?newqueue;
????this.head?=?0;
????this.tail?=?size;
}

在resize函數(shù)當中首先申請新長度的數(shù)組空間，然后將原數(shù)組的數(shù)據(jù)一個一個的拷貝到新的數(shù)組當中，注意在這個拷貝的過程當中，重新更新了head與tail，而且并不是簡單的數(shù)組拷貝，因為在之前的操作當中head可能已經(jīng)不是了0，因此新的拷貝需要我們一個一個的從舊數(shù)組拿出來，然后放到新數(shù)組當中。下圖可以很直觀的看出這個過程：