我已经在这上面工作了一段时间了,我想我终于破解了它,它对我所有的测试都有效,但我感觉会有一些微不足道的问题。这是一个高度简化的双边队列(deque)版本,每次添加一个值时,都会生成一个临时数组来存储所有值,然后再追加新值。我相信这是最容易解释的。如果有人能再检查一遍我是正确的,并且这里没有明显的错误,我将非常感谢。非常感谢大家!:)
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-1];
}
public boolean isEmpty() {
return end == 0;
}
public int size() {
return deque.length;
}
public boolean isFull() {
return end == capacity;
}
public void insertFirst(EltType inserted) {
if (!isEmpty()) {
EltType[] tempArray;
capacity+=1;
tempArray = (EltType[]) new Object[capacity];
for(int i=0;i<end;i++){
tempArray[i+1] = deque[i];
}
deque=tempArray;
}
deque[0] = inserted;
end++;
}
public void insertLast(EltType last) {
if (isFull()){
EltType[] tempArray;
capacity+=1;
tempArray = (EltType[]) new Object[capacity];
for (int i=0;i<end;i++) {
tempArray[i] = deque[i];
}
// System.out.print(deque[end]);
}
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;
EltType returned = deque[end-1];
tempArray = (EltType[]) new Object[capacity];
for (int i=0;i<capacity;i++) {
tempArray[i] = deque[i];
}
deque = tempArray;
end--;
return returned;
}
}发布于 2011-02-09 03:29:05
下面是一些评论:
T或E作为类型参数的名称,而不是将常量CAPACITY重命名为DEFAULT_CAPACITY,并使其返回一个值,即使双端队列在逻辑上是emptylast(),的,removeFirst()也会返回一个值,如果end为0<E>H119,则end将抛出适当的异常。将容量与大小分开没有意义,除非您使用它来避免每次都创建新的数组。如果您总是要在任何更改时扩展/收缩数组,只需使用数组本身-您可以根据数组的长度来判断大小,removeFirst capacity而不是endSystem.arraycopy作为复制数组的更简单方法,您在<代码>D32中没有分配给deque -因此您在注释中看到异常。<代码>H233<代码>F234我不确定我是否看到了仅仅使用ArrayList<T>的好处……拥有单独的Deque实现的主要目的是使添加头部和尾部的成本更低……在这里我们两者都没有!
..。当然也可以使用ArrayDeque或LinkedList :)
发布于 2011-02-09 03:29:30
我建议
https://stackoverflow.com/questions/4937326
复制相似问题