找不到基于数组的双端队列的问题，但出现越界异常

Question

多年来我一直试图解决这个问题，但没有成功。我想我的代码一定有几个我看不到的问题。我之前用稍微复杂一点的方式实现了这个，并以更简单的形式编写它来帮助我下面一年级正在挣扎的朋友，但我最终让自己陷入了困境！

代码如下：

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

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

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

  public boolean isFull() {
   int curSize = size();
   return curSize >= capacity;
  }

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

  public void insertLast(EltType last) {
    if (isFull()){
          EltType[] tempArray;
      tempArray = (EltType[]) new Object[CAPACITY+1];
      for (int i=0;i<deque.length;i++) {
        tempArray[i] = deque[i]; 
      }
    }
    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;
        System.out.println(end);
    EltType returned = deque[end];

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

问题是，当我调用

abd.insertFirst( 3 );
abd.insertFirst( 3 );
abd.insertFirst( 3 );

它时，它返回一个错误。

java.lang.ArrayIndexOutOfBoundsException: 11
    at ArrayBasedDeque.insertFirst(ArrayBasedDeque.java:37)
    at TestABD.main(TestABD.java:7)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:271)

insertLast 方法也是如此。我无法弄清楚，希望 stackOverflow 的仔细观察可以帮助我。多谢 ！

Answer 1

tempArray = (EltType[]) new Object[capacity+1];
for (int i=0;i<deque.length;i++) {
  tempArray[i+1] = deque[i]; 
}
deque = tempArray; 

第一次方法调用后，deque 是一个长度为 11 的数组 (deque == tempArray == new Object[capacity+1 ] == new Object[11] 下次调用该方法时，为 capacity+1 = 分配 tempArray。 = 11 个槽，但将 for 循环从 0 遍历到 deque.length，即 0 到 >10 在第二个方法调用上，循环的最后一次结束是：

tempArray[11] = ...

它超过了 tempArray 的末尾，它只有 11 槽 (< code>[0] 到 [10]）。

---

简单的解决方法是让 for 循环从 0 到 capacity。 > 而不是从 0 到 deque.length，但我不确定这是否实现了您想要的实际行为。另一种方法是分配 tempArray = new Object。 [deque.length+1]，但是 capacity 并不真正意味着容量，它仍然可能无法从概念上反映您认为在这种情况下的“正确”行为。

Answer 2

我在 Java 方面没有太多经验，所以我可能在这里有所偏差，但是......当您调用 InsertFirst 时，尚未将任何值设置为容量。所以它默认为 0 或垃圾。不管怎样，当你打电话时
tempArray = (EltType[]) new Object[容量+1];
容量要么是 1，要么是……某个“随机”数字。这就是为什么会出现越界。我猜你是想使用容量？

Answer 3

这是该特定错误的答案。您没有更新实例变量 capacity，因此每次调用 insertFirst 时，临时数组实际上并没有增长。所以代码应该如下所示：

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

尽管如此，总体类还远远不正确。