デキューの前面を削除する問題（ダブルエンドキュー）

Question

左に追加する、右に追加する、左に削除する、右に削除するというオプション付きのDequeをjavaで作成する作業があります。

私は追加権限をコーディングしていますが、正常に削除する方法はありますが、左に追加して左の作業を削除する際に問題があります。

私はどこか大規模に間違っていると思います。私は配列を使用して両端キューを作成しようとしています

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
at java.util.Arrays.copyOf(Arrays.java:3332) 
at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:137) 
at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:121) 
at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:421) 
at java.lang.StringBuffer.append(StringBuffer.java:265) 
at datastructuresass1.DendQueue.toString(DendQueue.java:107) 
at datastructuresass1.main.main(main.java:21) 
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) 
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) 
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) 
at java.lang.reflect.Method.invoke(Method.java:497) 
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147) 

：私はちょうどアドオンは、左の変数の周りに交換し、動作しませんでしたし、ちょうど次を思い付くだろうな計算を逆にしようとしています。以下は、右の追加と左のメソッドを追加するための私のコードです：

は（働いている）右

public void addRight(T o) { 
     right = (right + 1) % arr.length; 
     arr[right] = o; 

     // if the array is full copy it to a larger one 
     if ((right + 1) % arr.length == left) { 
      T[] newarr = (T[]) new Object[arr.length * 2]; 
      int i; 
      for (i = 0; i < arr.length; i++) 
       newarr[i] = arr[(left + i) % arr.length]; 
      arr = newarr; 
      left = 0; 
      right = i - 1; 

      System.out.println("Array size increased to " + 
      arr.length); 
     } 

を追加

public void addLeft(T o){ 

     left = (left + 1) % arr.length; 
     arr[left] = o; 

     // if the array is full copy it to a larger one 
     if ((left + 1) % arr.length == right) { 
      T[] newarr = (T[]) new Object[arr.length * 2]; 
      int i; 
      for (i = 0; i < arr.length; i++) 
       newarr[i] = arr[(right - i) % arr.length]; 
      arr = newarr; 
      left = i - 1; 
      right = 0; 

      System.out.println("Array size increased to " + 
      arr.length); 
     } 

（動作しない）左を追加し、誰かが説明することができますなぜこのaddLeftメソッドが動作していないのですか？これをしばらく私が困惑させてしまったのは、大きな助けになるでしょう！前もって感謝します。

Answer 1

配列を使った作業は非常に効率が悪く、リンクリストを試してみるのはずっと簡単です！ そして、オブジェクトの追加と削除のためにすべてのメモリコピーを必要としないので、キューの方が適切です（はるかに高速です）。それは

LinkedListのは、標準のJavaライブラリの一部でありaddfirstとaddlastなどのためのメソッドがあります。https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

は、彼があるよりも、それはあなたが、配列を使用するように、教師力場合

をどのように働くかのためhttps://en.wikipedia.org/wiki/Linked_list#Doubly_linked_listを参照してくださいナット：D

Answer 2

変数を入れ替えるだけでは不十分です。

left計算が間違っているように見えます：left = (left + 1) % arr.length;。増分するのではなく、減少させるべきです。 rightとは異なり、モジュラス（%）演算子を使用して0に折り返します。しかしleftは単純なifの条件で行う必要があります。

if (left - 1 < 0)   //if left is going less than zero, 
    left = arr.length - 1; //wrap it back to the end of the array 
else 
    left = left - 1;  //else do normal decrement 
arr[left] = o; 

// if the array is full copy it to a larger one 
// if left is at the begining & right's at the ending, then we're full 
if ((left == 0 && right == arr.length - 1) 
    // or if decrementing leftwards reaches right, we're full 
    || left - 1 == right) { 

配列のコピーループでは、右または左を追加して配列をいっぱいにしても、コピーロジックは変わりません。 leftからrightまでのすべての要素を0から2nまでの新しい配列にコピーするだけです。したがって、配列のコピーロジック内の変数を交換する必要はありません。あなたはaddRight()のロジックを再利用することができます。

うまくいけば、それは正しい方向に進むのに役立ちます。完全なコード+そのエラーを引き起こしたテストケースを提供するまで、直面したエラーを再現することはできません。

まだ気付かれていない場合は、循環配列hereを使用するDequeの実装があります。あなたは&を理解することができます。なぜあなたが間違っていたかを理解してください。&また、左右の音よりも混乱することなく、前後の音に追加することができます。:)