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

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

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

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

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

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

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

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!