已经为此工作了一段时间,我想我终于破解了它,它适用于我所有的测试,但我感觉会有一些琐碎的问题。这是一个高度简化的双面队列(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;
}
}