Analysieren Sie den Java ArrayQueue-Quellcode.

Interne Implementierung von ArrayQueue

Bevor wir über die interne Implementierung von ArrayQueue sprechen, schauen wir uns zunächst ein Anwendungsbeispiel von ArrayQueue an: ArrayQueue的内部实现之前我们先来看一个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]

首先ArrayQueue内部是由循环数组实现的，可能保证增加和删除数据的时间复杂度都是，不像ArrayList删除数据的时间复杂度为。在ArrayQueue内部有两个整型数据head和tail，这两个的作用主要是指向队列的头部和尾部，它的初始状态在内存当中的布局如下图所示：

因为是初始状态head和tail的值都等于0，指向数组当中第一个数据。现在我们向ArrayQueue内部加入5个数据，那么他的内存布局将如下图所示：

现在我们删除4个数据，那么上图经过4次删除操作之后，ArrayQueue内部数据布局如下：

在上面的状态下，我们继续加入8个数据，那么布局情况如下：

我们知道上图在加入数据的时候不仅将数组后半部分的空间使用完了，而且可以继续使用前半部分没有使用过的空间，也就是说在ArrayQueue内部实现了一个循环使用的过程。

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

上面的构造函数的代码比较容易理解，主要就是根据用户输入的数组空间长度去申请数组，不过他具体在申请数组的时候会多申请一个空间。

add函数

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可以循环将数据加入到数组当中去，这一点在上面的代码当中也有所体现。

remove函数

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函数当中我们必须传递参数0，否则会抛出异常。而在这个函数当中我们只会删除当前head下标所在位置的数据，然后将head的值进行循环加1操作。

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

get函数的参数表示得到第i个数据，这个第i个数据并不是数组位置的第i个数据，而是距离head位置为i的位置的数据，了解这一点，上面的代码是很容易理解的。

resize函数

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函数当中首先申请新长度的数组空间，然后将原数组的数据一个一个的拷贝到新的数组当中，注意在这个拷贝的过程当中，重新更新了head与tail，而且并不是简单的数组拷贝，因为在之前的操作当中headrrreee

Zuallererst: ArrayQueue wird intern durch ein zyklisches Array implementiert, was sicherstellen kann, dass die zeitliche Komplexität des Hinzufügens und Löschens von Daten gleich ist, im Gegensatz zur zeitlichen Komplexität von ArrayList beim Löschen von Daten. Es gibt zwei ganzzahlige Daten head und tail innerhalb von ArrayQueue. Die Funktionen dieser beiden bestehen hauptsächlich darin, auf den Kopf und das Ende der Warteschlange zu verweisen. Das Layout des Anfangszustands im Speicher ist wie folgt:

🎜Weil die Werte von head und tail im Anfangszustand beide gleich 0 sind und auf die ersten Daten im Array verweisen. Jetzt fügen wir 5 Daten zu ArrayQueue hinzu, dann sieht das Speicherlayout wie folgt aus: 🎜🎜🎜🎜Jetzt löschen wir 4 Daten, und nach 4 Löschvorgängen im obigen Bild sieht das interne Datenlayout von ArrayQueue wie folgt aus ：🎜🎜🎜🎜Im obigen Zustand Wir fügen weiterhin 8 Daten hinzu, dann ist das Layout wie folgt: 🎜🎜🎜🎜Wir wissen, dass beim Hinzufügen von Daten im obigen Bild nicht nur der Platz in der zweiten Hälfte des Arrays verbraucht wird, sondern auch der ungenutzte Platz in der ersten Hälfte weiterhin genutzt werden kann Das heißt, innerhalb von ArrayQueue wird ein Recyclingprozess implementiert. 🎜🎜ArrayQueue-Quellcode-Analyse🎜

Konstruktor

rrreee🎜Der Code des oben genannten Konstruktors ist relativ einfach zu verstehen. Er gilt jedoch hauptsächlich für ein Array, das auf der vom Benutzer eingegebenen Länge des Array-Speicherplatzes basiert. Bei der Bewerbung um einen Platz wird es konkreter. 🎜

Funktion hinzufügen

rrreee🎜Der obige Code ist relativ einfach zu verstehen. Wir haben oben erwähnt, dass ArrayQueue dem Array Daten in einer Schleife hinzufügen kann obiger Code. 🎜

remove-Funktion

rrreee🎜Wie aus dem obigen Code ersichtlich ist, müssen wir den Parameter 0 in der remove-Funktion übergeben, sonst wird eine Ausnahme ausgelöst. In dieser Funktion löschen wir nur die Daten an der aktuellen head-Indexposition und führen dann eine zyklische Erhöhung um 1 für den Wert von head durch. 🎜

get-Funktion

rrreee🎜Die Parameter der get-Funktion geben an, dass die i-ten Daten abgerufen werden, und der ite Daten sind nicht Es handelt sich nicht um die iten Daten in der Array-Position, sondern um die Daten an der Position i von der Kopf-Position. Wenn Sie dies verstehen, ist der obige Code sehr leicht zu verstehen. 🎜

Resize-Funktion

rrreee🎜In der resize-Funktion beantragen Sie zunächst einen Array-Bereich mit neuer Länge und kopieren dann die Daten des ursprünglichen Arrays nacheinander in das neue Array Beachten Sie Folgendes: Während des Kopiervorgangs werden head und tail erneut aktualisiert, und es handelt sich nicht um eine einfache Array-Kopie, da dies bei head der Fall sein kann Es ist nicht 0, daher müssen wir es für die neue Kopie einzeln aus dem alten Array herausnehmen und dann in das neue Array einfügen. Das Bild unten zeigt diesen Vorgang deutlich: 🎜🎜🎜🎜

Das obige ist der detaillierte Inhalt vonAnalysieren Sie den Java ArrayQueue-Quellcode.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!