我已经为此工作了一段时间了,我想我终于解决了它,它适用于我的所有测试,但我有一种感觉,会有一些棘手的问题。这是双边队列(双端队列)的高度简化版本,每次添加值时,都会创建一个临时数组来存储所有值,然后附加新值。我相信这样解释是最简单的。如果有人可以仔细检查我的正确性并且这里没有任何明显的错误,我将非常感激。非常感谢大家! :)
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;
}
}
最佳答案
一些评论:
- 我会使用
T
或E
作为类型参数的名称,而不是EltType
- 我会重命名常量
CAPACITY
至DEFAULT_CAPACITY
,并使其静态。 -
first()
即使双端队列逻辑上为空也会返回一个值 -
last()
,removeLast()
和removeFirst()
如果end
则应抛出适当的异常是 0 - 将容量与大小分开是没有意义的,除非您使用它来避免每次创建新数组。如果您总是要在任何更改时扩展/缩小数组,只需单独使用该数组 - 您可以仅根据数组的长度来判断其大小
- 在
removeFirst
和removeLast
你的循环界限是capacity
而不是end
- 使用
System.arraycopy
作为复制数组的更简单方法 - 您还没有分配给
deque
在insertLast
- 因此您在评论中看到了异常。
我不确定我是否看到这样做比仅使用 ArrayList<T>
有什么好处。不过...拥有单独的 Deque
的要点实现将是使添加到头部和尾部变得便宜......这里我们两者都没有!
...或者当然只是使用ArrayDeque
或LinkedList
:)
关于java - 有人可以给我一个双端队列的代码吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4937326/