0

しばらくこれに取り組んできましたが、ついにクラックしたと思います。すべてのテストで機能していますが、いくつかの問題があると感じています。これは、値が追加されるたびに一時配列が作成されてすべての値が格納され、次に新しい値が追加される、両面キュー (deque) の非常に単純化されたバージョンです。このように説明するのが最も簡単だと思います。誰かが私が正しく、ここに明らかな問題がないことを再確認していただければ、非常に感謝しています. どうもありがとうございました！:)

    public class ArrayBasedDeque<EltType> implements Deque<EltType> {

  private final int CAPACITY = 10;
  private int capacity;
  private int end;
  private EltType deque[];  

  public ArrayBasedDeque() {
    this.capacity = CAPACITY;
    deque = (EltType[]) (new Object[capacity]);  
  }
  public EltType first() {
    return  deque[0];
  }
  public EltType last() {
    return deque[end-1];
  }

  public boolean isEmpty() {
    return end == 0;
  }

  public int size() {
   return deque.length;
  }

  public boolean isFull() {
   return end == capacity;
  }
  public void insertFirst(EltType inserted) {
    if (!isEmpty()) {
    EltType[] tempArray;
    capacity+=1;
    tempArray = (EltType[]) new Object[capacity];
    for(int i=0;i<end;i++){
    tempArray[i+1] = deque[i]; 
    }
    deque=tempArray;
    }
    deque[0] = inserted;
    end++;
    }

  public void insertLast(EltType last) {
    if (isFull()){
          EltType[] tempArray;
          capacity+=1;
      tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<end;i++) {
        tempArray[i] = deque[i]; 
      }
//      System.out.print(deque[end]);
    }
    deque[end] = last;   
    end++;
  }

  public EltType removeFirst() {
    EltType[] tempArray;
    EltType returned = deque[0];
    tempArray = (EltType[]) new Object[capacity];
      for (int i=1;i<capacity;i++) {
        tempArray[i-1] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }

  public EltType removeLast() {
    EltType[] tempArray;
    EltType returned = deque[end-1];

    tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<capacity;i++) {
        tempArray[i] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }




}
4

2 に答える 2

3

いくつかのコメント:

  • ではなく、型パラメーターの名前としてTorを使用します。EEltType
  • 定数の名前を に変更し、CAPACITY静的DEFAULT_CAPACITYにします。
  • first()両端キューが論理的に空であっても値を返します
  • last()でremoveLast()あり、 0removeFirst()の場合は適切な例外をスローする必要がありますend
  • 毎回新しい配列を作成することを避けるためにそれを使用していない限り、サイズとは別に容量を設定しても意味がありません。変更時に常に配列を拡大/縮小する場合は、配列を単独で使用してください-配列の長さからサイズを知ることができます
  • でremoveFirst、removeLastあなたのループバウンドはcapacity代わりにend
  • System.arraycopy配列をコピーする簡単な方法として使用
  • dequeへの割り当てがありませinsertLastん。したがって、コメントに表示されている例外です。

ただ使用するよりもこれを使用する利点があるかどうかはわかりません...別の実装ArrayList<T>を行う主なポイントは、ヘッドとテールの両方に追加を安価にすることです...ここではどちらもありません!Deque

...またはもちろん、 or を使用してArrayDequeくださいLinkedList:)

于 2011-02-08T19:29:04.697 に答える
0

私は提案します

  • エントリを追加または削除するたびに新しい Object[] を作成しないでください。
  • 手動コピーの代わりに System.arrayCopy() を使用します。
  • 最後までコピーするだけで、容量までコピーする必要はありません。
  • リング バッファを使用して、要素を移動する必要をなくすことができます (コピーは必要ありません)。
  • Drop Based は ArrayDeque という名前から派生し、ArrayList、ArrayBlockingQueue などとの一貫性が向上しました。
于 2011-02-08T19:29:29.913 に答える