3

循環配列を使用してキューを実装していますが、メソッドの実装でスタックしていresize()ます (配列がいっぱいの場合)。

メソッド内enqueue()で、配列のサイズがその長さと等しいかどうかを確認し、それがいっぱいかどうかを取得します。ここで、例外をスローする代わりに、配列のサイズを変更しようとしています。

問題は、考慮すべき2つのケースがあるということです

  1. フロント <= リア
  2. リヤ＜フロント

古い配列の要素を新しい大きな配列にコピーする最良の方法はどれですか?

次のようなforループを使用して考えました：

newArray = new Array[oldArray.length*2];

if (front <= rear) {
    for (int i = front; i < rear; i++) {
        newArray[i] = oldArray[i];
    } 
} else {
    for (int i = front; i < newArray.length; i++) {
        newArray[i] = oldArray[i];
    }

    for (int j = rear; j < front; j++) {
        // i'm using the variable i, the order is maintained
        newArray[i] = oldArray[j];
        i++;
    }
}

次にoldArray= newArray、戻りnewArray、サイズ変更が完了しました

これを行うために使用された for の量がわからないので、値を失うのではないかと心配しています。

これを行うためのより良い方法があるかどうか誰かに教えてもらえますか?

4

4 に答える 4

5

少数の要素を超える配列をコピーするには、System.arraycopy（）を使用します。これは通常、ネイティブコードとして実装されているためです。たとえば、SunのVMは手動でコード化されたアセンブラーを使用します。

フロント>リア

データは連続しているため、新しいアレイの同じ場所に残すことができます。

System.arraycopy(oldArray, front, newArray, front, front-rear);

フロント<=リア

データは連続していないため、両方のブロックを新しいアレイの先頭にコピーします。

// copy [rear to end]
System.arraycopy(oldArray, rear, newArray, 0, oldArray.length-rear);
// copy [0 to front]
System.arraycopy(oldArray, 0, newArray, oldArray.length-rear, front);
front = oldArray.length-(rear-front);
rear = 0;
于 2011-04-17T17:27:34.570 に答える
2

あなたの答えとさまざまな解決策に感謝します！:)

System.arraycopy() メソッドを使用するのが最も簡単で効率的な解決策ですが、私はその使用を避け、自分で解決策を実装する必要がありました。

したがって、誰かが System.arraycopy() を使用せずにキュー実装で循環配列を resize() したい場合、これが私の最終的な解決策です:

private void resize() {

    E[] aux = (E[]) new Object[Q.length * 2]; // new array

    int i = 0; // use this to control new array positions
    int j = f; // use this to control old array positions

    boolean rearReached = false;

    while (!rearReached) {

        rearReached = j % Q.length == r; // is true if we've reached the rear

        aux[i] = Q[j % Q.length];

        i++;
        j++;

    }

    f = 0;
    r = Q.length - 1;
    Q = aux;

}

ご覧のとおり、「循環」を利用して、% 演算子を使用して古い配列の位置を新しい配列にマッピングしました。

結果として得られる配列には、新しい配列の先頭に、2 倍の容量とすべての要素 (明らかに元の順序が維持されます) が含まれます。

テストしましたが、正常に動作しました。そのコードに不都合があるかどうかを教えてください。

よろしく

于 2011-04-19T22:20:24.243 に答える
0

配列がいっぱいの場合はfront == rear - 1、 、 またはrear == 0and front == length -1(またはその逆、あなたの命名法はわかりません) のいずれかです。2 番目のケースでは、配列全体を 1 ステップでコピーできます。(より一般的な) 最初のケースでは、コピーする 2 つのブロック (0 .. フロントとリア .. 長さ 1) があります。

于 2011-04-17T17:56:44.417 に答える
0

移動する配列要素のブロックと、それらが新しい配列内のどこに移動するかを考えてください。次に、 System.arraycopy を使用してそれを行います。フロント < リアの場合は 1 回、リア < フロントの場合は 2 回、arraycopy を呼び出す必要があります。

于 2011-04-17T17:24:03.727 に答える