移除出队前端的问题（双端队列）

我的任务是在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

移除出队前端的问题（双端队列）

回答

相关问题