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

Question

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

代码如下:

 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 code> == 11 槽，但将 for 循环从 0 遍历到 deque.length (即 0)在第二个方法调用时为 10。循环的最后一遍最终为:

tempArray[11] = ...

超过了 tempArray 的末尾，该数组只有 11 个槽([0] 到 [10]).

<小时/>

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