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 回答