移除出隊前端的問題（雙端隊列）

我的任務是在java中創建一個Deque，使用選項添加左邊，添加右邊，刪除左邊並刪除右邊。移除出隊前端的問題（雙端隊列）

我已經編寫了添加權限，併成功地刪除了正確的方法，但我有問題試圖讓左側添加和刪除左側工作。

我覺得我已經大大地錯了某個地方。我剛纔想換輪變量左側添加和倒車，沒有工作，而且只會拿出以下的計算：

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

添加右鍵（這是工作）

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

請能有人解釋對我來說爲什麼這個addLeft方法不起作用。這將是一個很大的幫助，因爲我一直在這個難住！提前致謝。

來源

2017-08-15 RJB97

使用數組效率非常低，請嘗試使用鏈表，非常簡單！對於一個隊列來說更合適（更快），因爲它不需要所有的內存複製來添加和刪除對象。它有addfirst僅和addlast僅等方法

LinkedList的是標準的Java庫的一部分：https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

看到https://en.wikipedia.org/wiki/Linked_list#Doubly_linked_list它是如何工作

如果老師強迫你使用一個數組，比他堅果：D

來源

2017-08-15 14:22:18 bluevoid

交換變量是不夠的。

看起來像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()中的邏輯。

希望這有助於獲得正確的方向。我將無法重現您所面臨的錯誤，直到您提供完整的代碼+觸發該錯誤的測試用例。

如果你還沒有意識到，有一個使用圓形陣列Deque的實現。你可以學習&明白你爲什麼錯了&。此外，增加前/後聲音比右/左更容易混淆。:)

來源

2017-08-15 14:56:11 Vineet

移除出隊前端的問題（雙端隊列）

回答

相關問題