Analisis kod sumber Java ArrayQueue.

Pelaksanaan dalaman ArrayQueue

Sebelum bercakap tentang pelaksanaan dalaman ArrayQueue, mari kita lihat contoh penggunaan 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); // 这个参数只能为0 表示删除队列当中第一个元素，也就是队头元素
    System.out.println(queue);
    queue.remove(0);
    System.out.println(queue);
}
// 输出结果
[1, 2, 3, 4]
[2, 3, 4]
[3, 4]

Pertama sekali, ArrayQueue dilaksanakan secara dalaman oleh tatasusunan kitaran, yang mungkin memastikan bahawa kerumitan masa menambah dan memadam data adalah sama, tidak seperti kerumitan masa ArrayList memadamkan data. Terdapat dua data integer ArrayQueue dan head di dalam tail, yang digunakan terutamanya untuk menunjuk ke kepala dan ekor baris gilir >

Oleh kerana ia adalah keadaan awal, nilai

dan

kedua-duanya sama dengan 0, menunjuk kepada data pertama dalam tatasusunan. Sekarang kita menambah 5 keping data ke head, maka susun atur memorinya akan seperti yang ditunjukkan di bawah: tailArrayQueue

Sekarang kita memadam 4 keping data, kemudian angka di atas pergi melalui 4 Selepas operasi pemadaman, susun atur data dalaman

adalah seperti berikut:

ArrayQueue

Dalam keadaan di atas, kami terus menambah 8 data, maka susun atur adalah seperti berikut:

Kita tahu bahawa apabila menambah data dalam gambar di atas, bukan sahaja ruang dalam separuh kedua tatasusunan digunakan, tetapi juga ruang yang tidak digunakan dalam separuh masa pertama boleh diteruskan, iaitu dalam

Proses kitar semula dilaksanakan secara dalaman.

ArrayQueueAnalisis kod sumber ArrayQueue

Pembina

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];
}

Kod pembina di atas agak mudah difahami Ia digunakan terutamanya untuk tatasusunan berdasarkan panjang ruang tatasusunan dimasukkan oleh pengguna, tetapi ia adalah khusus Apabila memohon tatasusunan, satu lagi ruang akan digunakan.

tambah fungsi

public boolean add(T o) {
    queue[tail] = o;
    // 循环使用数组
    int newtail = (tail + 1) % capacity;
    if (newtail == head)
        throw new IndexOutOfBoundsException("Queue full");
    tail = newtail;
    return true; // we did add something
}

Kod di atas agak mudah difahami bahawa

boleh menggelungkan untuk menambah data Ini juga dinyatakan di atas dalam kod.

ArrayQueuefungsi alih keluar

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;
}

Seperti yang dapat dilihat daripada kod di atas, kita mesti lulus parameter 0 dalam fungsi

, jika tidak pengecualian akan dilemparkan. Dalam fungsi ini, kami hanya akan memadamkan data pada kedudukan subskrip

semasa, dan kemudian melakukan operasi kitaran menambah 1 pada nilai remove. Parameter fungsi headheadget

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];
}

menunjukkan bahawa data

diperolehi getdata ke-1 bukan idata dalam kedudukan tatasusunan, tetapi Ia adalah data kedudukan i jauh dari i Mengetahui perkara ini, kod di atas mudah difahami. headifungsi ubah saiz

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;
}

Dalam fungsi

, mula-mula memohon ruang tatasusunan dengan panjang baharu, kemudian salin data tatasusunan asal ke tatasusunan baharu satu demi satu bahawa dalam salinan ini Semasa proses,

dan resize dikemas kini sekali lagi, dan ia bukan salinan tatasusunan mudah, kerana head mungkin tidak lagi 0 dalam operasi sebelumnya, jadi salinan baharu memerlukan kami mengambil ia daripada tatasusunan lama satu demi satu dan masukkan ke dalam tatasusunan baharu. Gambar berikut dapat melihat dengan jelas proses ini: tailhead

Atas ialah kandungan terperinci Analisis kod sumber Java ArrayQueue.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!