Java ArrayQueue ソース コードを分析します。

ArrayQueue の内部実装

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 内には 2 つの整数データ head と tail があります。これら 2 つの機能は主にキューの先頭と末尾、およびその初期値を指すことです。メモリ内のレイアウトは以下のようになります:

headとtailの値は両方とも初期状態では 0 に等しく、配列内の最初のデータを指します。 ArrayQueue に 5 つのデータを追加すると、そのメモリ レイアウトは次のようになります。

次に、4 つのデータを削除し、その後、上の図で 4 つの削除操作を行った後、

ArrayQueue の内部データ レイアウトは次のようになります。

上記の状態で、8 を追加し続けます。

上図でデータを追加すると、配列の後半のスペースが使用されるだけでなく、ただし、前半の未使用領域も引き続き使用できます。つまり、リサイクル プロセスが

ArrayQueue 内に実装されています。

ArrayQueue ソース コード分析

Constructor

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

上記のコンストラクター コードは比較的理解しやすく、主に、によって入力された配列空間の長さに基づいて配列に適用されます。配列を申請すると、さらに 1 つのスペースが申請されます。

add function

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 function

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 function

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 番目のデータが取得されることを示し、ith data is not 配列位置の 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 が再度更新されますが、前の操作では head が使用されていたため、これは単純な配列のコピーではありません。は 0 ではなくなる可能性があるため、新しいコピーを作成するには、古い配列から 1 つずつ取り出して、新しい配列に入れる必要があります。次の図は、このプロセスを明確に示しています:

以上がJava ArrayQueue ソース コードを分析します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。