1

私は、Deque ライブラリを使用せずに ArrayDeque の前 (左) に追加するメソッドを作成することを任されています。que に追加されていませんが、空の que で出てくるメソッドを思いつきました。これが私のaddLeftメソッドです：

public T[] addLeft(T item){
    T[] copyarr = (T[]) new Object[arr.length+1];

    if(isEmpty()){
        copyarr[frontPos] = item;

    }else{
        copyarr[frontPos] = item;
        frontPos--;
        for(int i = 1; i<copyarr.length; i++){
            copyarr[i] = arr[i];
        }
    }
    arr = copyarr;
    return arr;
}

ivが使用しているテストコードは次のとおりです。

public class DequeueTest {

public static void main(String[] args) {
    Dequeue test = new Dequeue();
    test.addLeft(3);
    test.addLeft(4);
    System.out.println(test.toString());
}
}

私が間違っている場所はありますか？

4

1 に答える 1

1

「Dequeライブラリを使用しないArrayDeque」を明確にできますか? JDK からArrayDequeを使用したくないということですか?

配列のコピーステートメントで間違っています。

copyarr[i] = arr[i-1]

（インデックスがどのようにシフトされるかに注意してください）

毎回配列をコピーしているため、要素を前に追加するための実装には深刻な実行時コストがかかります。(コンピューター サイエンスのクラスから: ArrayLists は、必要に応じて配列サイズを 2 倍にすることで実行時の動作を取得し、すべての追加操作でサイズ変更コストのバランスを取ります。)

また、コメントで既に述べたように、インスピレーションを得るために ArrayDeque の実装を見てください。多分offerFirstそれは本当にあなたが必要としているものです。

Ferrybig のコメントに基づく追加:

ストレージ配列が実際の両端キューよりも大きくなるように、追加の変数で配列サイズを追跡することができます。これにより、ストレージ アレイのサイズが小さすぎる場合に 2 倍にすることができ、毎回コピーを作成する必要がなくなります。それでも、要素を (高いインデックスから低いインデックスへ) 移動し、最後に最初に新しい要素を配置する必要があります。

2 番目の最適化ステップ: 最初の位置を保存し、先頭に複数の挿入が予想される場合は、挿入のたびに要素を移動する必要がないように、いくらかのスペースを確保します。(繰り返しになりますが、ランタイムの複雑さのために空間を交換しています。)

于 2016-01-26T14:35:30.793 に答える