您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java ArrayQueue源碼分析”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“Java ArrayQueue源碼分析”吧!
在談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); } // 輸出結果 [1, 2, 3, 4] [2, 3, 4] [3, 4]
首先ArrayQueue
內(nèi)部是由循環(huán)數(shù)組實現(xiàn)的,可能保證增加和刪除數(shù)據(jù)的時間復雜度都是,不像ArrayList
刪除數(shù)據(jù)的時間復雜度為。在ArrayQueue
內(nèi)部有兩個整型數(shù)據(jù)head
和tail
,這兩個的作用主要是指向隊列的頭部和尾部,它的初始狀態(tài)在內(nèi)存當中的布局如下圖所示:
因為是初始狀態(tài)head
和tail
的值都等于0,指向數(shù)組當中第一個數(shù)據(jù)。現(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)使用的過程。
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]; }
上面的構造函數(shù)的代碼比較容易理解,主要就是根據(jù)用戶輸入的數(shù)組空間長度去申請數(shù)組,不過他具體在申請數(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)。
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操作。
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ù),了解這一點,上面的代碼是很容易理解的。
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ù)組當中。下圖可以很直觀的看出這個過程:
到此,相信大家對“Java ArrayQueue源碼分析”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關內(nèi)容可以進入相關頻道進行查詢,關注我們,繼續(xù)學習!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。