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

在談ArrayQueue的內(nèi)部實(shí)現(xiàn)之前我們先來(lái)看一個(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ù)雜度都是 O ( 1 ) O(1) O(1)，不像ArrayList刪除數(shù)據(jù)的時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)。在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)過(guò)4次刪除操作之后，ArrayQueue內(nèi)部數(shù)據(jù)布局如下：

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

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

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ù)用戶(hù)輸入的數(shù)組空間長(zhǎng)度去申請(qǐng)數(shù)組，不過(guò)他具體在申請(qǐng)數(shù)組的時(shí)候會(huì)多申請(qǐng)一個(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
}

上面的代碼也相對(duì)比較容易看懂，在上文當(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)中首先申請(qǐng)新長(zhǎng)度的數(shù)組空間，然后將原數(shù)組的數(shù)據(jù)一個(gè)一個(gè)的拷貝到新的數(shù)組當(dāng)中，注意在這個(gè)拷貝的過(guò)程當(dāng)中，重新更新了head與tail，而且并不是簡(jiǎn)單的數(shù)組拷貝，因?yàn)樵谥暗牟僮鳟?dāng)中head可能已經(jīng)不是了0，因此新的拷貝需要我們一個(gè)一個(gè)的從就數(shù)組拿出來(lái)，讓后放到新數(shù)組當(dāng)中。下圖可以很直觀的看出這個(gè)過(guò)程：

總結(jié)

在本篇文章當(dāng)中主要給大家介紹了ArrayQueue的內(nèi)部實(shí)現(xiàn)過(guò)程和原理，并且看了ArrayQueue的源代碼，有圖的輔助整個(gè)閱讀的過(guò)程應(yīng)該是比較清晰的，ArrayQueue也是一個(gè)比較簡(jiǎn)單的容器，JDK對(duì)他的實(shí)現(xiàn)也比較簡(jiǎn)單。

到此這篇關(guān)于Java源碼刨析之ArrayQueue的文章就介紹到這了,更多相關(guān)Java ArrayQueue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論