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: tail
ArrayQueue
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.ArrayQueue
Analisis kod sumber ArrayQueue
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]; }
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 }
ArrayQueue
fungsi 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; }
semasa, dan kemudian melakukan operasi kitaran menambah 1 pada nilai remove
. Parameter fungsi head
head
get
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 get
data ke-1 bukan i
data dalam kedudukan tatasusunan, tetapi Ia adalah data kedudukan i
jauh dari i
Mengetahui perkara ini, kod di atas mudah difahami. head
i
fungsi 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; }
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: tail
head
Atas ialah kandungan terperinci Analisis kod sumber Java ArrayQueue.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!