Problem beim Entfernen der Warteschlange (doppelte Warteschlange)

Question

Ich habe die Aufgabe, eine Deque in Java zu erstellen, mit Optionen zum Hinzufügen von Links, Hinzufügen von Rechten, Entfernen von Links und Entfernen von Rechts.

Ich habe das Hinzufügen rechts und entfernen Sie die richtigen Methoden erfolgreich, aber ich habe Probleme beim Versuch, add links und entfernen links arbeiten.

Ich denke, ich bin irgendwo massiv falsch gegangen. Ich habe gerade versucht, um die Variablen Swapping für Add links und die Berechnungen umgekehrt, die nicht funktioniert haben und würde nur mit dem folgenden kommen:

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) 

Ich versuche, die deque Verwendung von Arrays zu erstellen. Unten ist mein Code für das Recht hinzufügen und links Methoden hinzufügen:

hinzufügen Links (die nicht funktioniert)

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

hinzufügen Right (Welche funktioniert)

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

Bitte könnte jemand erklären, zu mir, warum diese addLeft-Methode nicht funktioniert. Es wäre eine große Hilfe, da ich schon eine ganze Weile darauf gestoßen bin! Danke im Voraus.

Answer 1

Arbeiten mit einem Array ist sehr ineffizient, versuchen Sie eine verknüpfte Liste, viel einfacher! Und viel passender (viel schneller) für eine Warteschlange, da es nicht das gesamte Kopieren des Speichers zum Hinzufügen und Entfernen von Objekten benötigt. Es verfügt über Methoden für addFirst und addlast usw.

LinkedList Teil der Standard-Java-Bibliothek ist: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

siehe https://en.wikipedia.org/wiki/Linked_list#Doubly_linked_list für, wie es funktioniert

Wenn Ihr Lehrer zwingt Sie ein Array verwenden, als er ist Muttern: D

Answer 2

Das Austauschen der Variablen ist nicht ausreichend.

Sieht aus wie die left Berechnung scheint falsch: left = (left + 1) % arr.length;. Sie sollten nicht erhöhen, eher dekrementieren. Im Gegensatz zu right verwenden Sie den Operator modul (%), um zu 0 zurückzukehren. Aber left wird mit einfachen if Bedingungen auskommen müssen.

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) { 

In der Array Kopierschleife, unabhängig davon, ob das Hinzufügen der Array voll ist, wird die Kopiervorgang gemacht rechts oder links Logik gleich bleiben. Sie müssen nur alle Elemente von left nach right in das neue Array von 0 bis 2n kopieren. Es müssen also keine Variablen in der Array-Kopierlogik ausgetauscht werden. Sie können die Logik in addRight() erneut verwenden.

Hoffentlich hilft das, in die richtige Richtung zu kommen. Ich kann den Fehler, dem Sie gegenüberstanden, nicht reproduzieren, bis Sie den vollständigen Code und den Testfall, der diesen Fehler ausgelöst hat, bereitgestellt haben.

Wenn Sie nicht bereits wissen, gibt es eine Implementierung von Deque mit kreisförmigen Array here. Du könntest lernen & zu verstehen, wo & wieso du schief gegangen bist. Außerdem wird der Sound vorne/hinten weniger verwirrend als rechts/links.:)