深入剖析Java ArrayQueue(JDK)的源碼
前言
在本篇文章當(dāng)中主要給大家介紹一個(gè)比較簡單的JDK
為我們提供的容器ArrayQueue
,這個(gè)容器主要是用數(shù)組實(shí)現(xiàn)的一個(gè)單向隊(duì)列,整體的結(jié)構(gòu)相對其他容器來說就比較簡單了。
ArrayQueue內(nèi)部實(shí)現(xiàn)
在談ArrayQueue
的內(nèi)部實(shí)現(xiàn)之前我們先來看一個(gè)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);?//?這個(gè)參數(shù)只能為0?表示刪除隊(duì)列當(dāng)中第一個(gè)元素,也就是隊(duì)頭元素 ????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ù)組實(shí)現(xiàn)的,可能保證增加和刪除數(shù)據(jù)的時(shí)間復(fù)雜度都是,不像ArrayList
刪除數(shù)據(jù)的時(shí)間復(fù)雜度為。在ArrayQueue
內(nèi)部有兩個(gè)整型數(shù)據(jù)head
和tail
,這兩個(gè)的作用主要是指向隊(duì)列的頭部和尾部,它的初始狀態(tài)在內(nèi)存當(dāng)中的布局如下圖所示:
因?yàn)槭浅跏紶顟B(tài)head
和tail
的值都等于0,指向數(shù)組當(dāng)中第一個(gè)數(shù)據(jù)?,F(xiàn)在我們向ArrayQueue
內(nèi)部加入5個(gè)數(shù)據(jù),那么他的內(nèi)存布局將如下圖所示:
現(xiàn)在我們刪除4個(gè)數(shù)據(jù),那么上圖經(jīng)過4次刪除操作之后,ArrayQueue
內(nèi)部數(shù)據(jù)布局如下:
在上面的狀態(tài)下,我們繼續(xù)加入8個(gè)數(shù)據(jù),那么布局情況如下:
我們知道上圖在加入數(shù)據(jù)的時(shí)候不僅將數(shù)組后半部分的空間使用完了,而且可以繼續(xù)使用前半部分沒有使用過的空間,也就是說在ArrayQueue
內(nèi)部實(shí)現(xiàn)了一個(gè)循環(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ù)組的時(shí)候會(huì)多申請一個(gè)空間。
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 }
上面的代碼也相對比較容易看懂,在上文當(dāng)中我們已經(jīng)提到了ArrayQueue
可以循環(huán)將數(shù)據(jù)加入到數(shù)組當(dāng)中去,這一點(diǎn)在上面的代碼當(dāng)中也有所體現(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; }
從上面的代碼當(dāng)中可以看出,在remove
函數(shù)當(dāng)中我們必須傳遞參數(shù)0,否則會(huì)拋出異常。而在這個(gè)函數(shù)當(dāng)中我們只會(huì)刪除當(dāng)前head
下標(biāo)所在位置的數(shù)據(jù),然后將head
的值進(jìn)行循環(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
個(gè)數(shù)據(jù),這個(gè)第i
個(gè)數(shù)據(jù)并不是數(shù)組位置的第i
個(gè)數(shù)據(jù),而是距離head
位置為i
的位置的數(shù)據(jù),了解這一點(diǎn),上面的代碼是很容易理解的。
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ù)當(dāng)中首先申請新長度的數(shù)組空間,然后將原數(shù)組的數(shù)據(jù)一個(gè)一個(gè)的拷貝到新的數(shù)組當(dāng)中,注意在這個(gè)拷貝的過程當(dāng)中,重新更新了head
與tail
,而且并不是簡單的數(shù)組拷貝,因?yàn)樵谥暗牟僮鳟?dāng)中head
可能已經(jīng)不是了0,因此新的拷貝需要我們一個(gè)一個(gè)的從舊數(shù)組拿出來,然后放到新數(shù)組當(dāng)中。下圖可以很直觀的看出這個(gè)過程:
總結(jié)
在本篇文章當(dāng)中主要給大家介紹了ArrayQueue
的內(nèi)部實(shí)現(xiàn)過程和原理,并且看了ArrayQueue
的源代碼,有圖的輔助整個(gè)閱讀的過程應(yīng)該是比較清晰的,ArrayQueue
也是一個(gè)比較簡單的容器,JDK
對他的實(shí)現(xiàn)也比較簡單。
到此這篇關(guān)于深入剖析Java ArrayQueue(JDK)的源碼的文章就介紹到這了,更多相關(guān)Java ArrayQueue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot實(shí)現(xiàn)無感刷新Token的項(xiàng)目實(shí)踐
token刷新是前端安全中必要的一部分,本文就來介紹一下SpringBoot實(shí)現(xiàn)無感刷新Token的項(xiàng)目實(shí)踐,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03Spring中的FactoryBean與BeanFactory詳細(xì)解析
這篇文章主要介紹了Spring中的FactoryBean與BeanFactory詳細(xì)解析,在Spring框架中,FactoryBean和BeanFactory是兩個(gè)關(guān)鍵的接口,用于創(chuàng)建和管理對象實(shí)例,它們在Spring的IoC(Inversion of Control,控制反轉(zhuǎn))容器中發(fā)揮著重要的作用,需要的朋友可以參考下2023-11-11Eclipse操作SVN時(shí)中斷鎖定,文件的解鎖方法
這篇文章主要介紹了Eclipse操作SVN時(shí)中斷鎖定,文件的解鎖方法,需要的朋友可以參考下2014-08-08