0

我一直试图弄清楚这个问题，但无济于事。我想我的代码一定有几个我看不到的问题。我之前使用稍微复杂一点的方式实现了这个，并以更简单的形式编写它来帮助我下面一年中正在苦苦挣扎的朋友，但我最终让自己陷入了困境！

代码如下：

 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 的仔细审视可以帮助我。非常感谢 ！

4

3 回答 3

4 
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]。下次调用该方法时，您分配tempArrayfor capacity+1==插槽，但在第二个方法上11遍历 for 循环 from 0to deque.lengthwhich is 0to10调用。循环的最后一遍最终是：

tempArray[11] = ...

它的末尾tempArray只有11插槽（[0]to [10]）。

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

于 2011-02-08T17:47:34.050 回答
0

我在 Java 方面没有太多经验，所以我可能会离开这里，但是……当您调用 InsertFirst 时，尚未将任何值设置为容量。所以它默认为 0 或垃圾。无论哪种方式，当您调用 tempArray = (EltType[]) new Object[capacity+1]; 容量将是 1 或......一些“随机”数字。因此，为什么要越界。我猜你打算使用 CAPACITY？

于 2011-02-08T17:46:06.580 回答
0

这是该特定错误的答案。您没有更新实例变量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++;
}

尽管如此，整体课程还远非正确。

于 2011-02-08T17:52:03.727 回答