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 つのデータを追加すると、そのメモリ レイアウトは次のようになります。

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

ログイン後にコピー

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 はループ内で配列にデータを追加できると上で述べました。これも反映されています上記のコードで。

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 を加算する循環操作を実行します。

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 番目のデータです。コードは理解しやすいです。

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 サイトの他の関連記事を参照してください。