Project1B - ArrayDeque 61B

这个项目中，我们需要用数组实现循环双端队列

初始化

创建类文件，并修改类声明以让该类是Deque61B接口的一个实现，且支持泛型

package deque;

import java.util.List;

public class ArrayDeque61B<T> implements Deque61B<T> {
    @Override
    public void addFirst(T x) {
        
    }

    @Override
    public void addLast(T x) {

    }

    @Override
    public List<T> toList() {
        return List.of();
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public T removeFirst() {
        return null;
    }

    @Override
    public T removeLast() {
        return null;
    }

    @Override
    public T get(int index) {
        return null;
    }

    @Override
    public T getRecursive(int index) {
        return null;
    }
}

构造函数

使用到的成员有

size：确定数组目前容量
capacity：确定数组最大容量
items：使用java内置数组存储数据
nextFirst：指向队首（第一个空位置）
nextLast：指向队尾（最后一个空位置）

public ArrayDeque61B(){
    size = 0;
    capacity = 8;
    items = (T[])new Object[capacity];
    nextFirst = 0;
    nextLast = 0;
}

addFirst() & addLast()

@Override
public void addFirst(T x) {
    if (size==capacity){
        resize(size*2);
    }
    items[nextFirst] = x;
    size++;
    nextFirst = floorMod(nextFirst-1, capacity);
}

@Override
public void addLast(T x) {
    if (size==capacity){
        resize(size*2);
    }
    items[nextLast] = x;
    size++;
    nextLast = floorMod(nextLast+1, capacity);
}

这里在添加时要考虑循环，若到队头了要转到队尾加

另外，当队列满了需要手动扩容，一般可以扩到原来都两倍，防止过多调用

get()

按下标获得元素，若无效返回null

@Override
public T get(int index) {
    if (index<0||index>=size){
        return null;
    }
    int realIndex = floorMod(index+nextFirst+1, capacity);
    return items[realIndex];
}

这里注意，get获得的是相对下标，我们需要转换成真实下标（即元素不一定是从0开始的，需要添加nextFirst偏移量）

getRecursive()没有什么必要，可以直接抛出一个异常

@Override
public T getRecursive(int index) {
    throw new UnsupportedOperationException("No need to implement getRecursive for proj 1b");
}

toList()

@Override
public List<T> toList() {
    List<T> show = new ArrayList<>(size);
    int cnt = 0;
    for (int i = 0; i<size;i++){
        show.add(get(i));
    }
    return show;
}

结合get方法会更加方便

removeFirst() & removeLast()

@Override
public T removeFirst() {
    if (isEmpty()){
        return null;
    }
    nextFirst = floorMod(nextFirst+1,capacity);
    size--;
    return items[nextFirst];
}

@Override
public T removeLast() {
    if (isEmpty()){
        return null;
    }
    nextLast = floorMod(nextLast-1,capacity);
    size--;
    return items[nextLast];
}

不要忘记判空以及减小size

resize()

作为数组大小不够时的方案，一次扩容两倍使用

private void resize(int newCapacity){
    T[] a = (T[]) new Object[newCapacity];
    int cur = floorMod(nextFirst+1,capacity);
    for(int i = 0; i<size;i++){
        a[i] = items[cur];
        cur = floorMod(cur+1, capacity);
    }
    items = a;
    capacity = newCapacity;
    nextFirst = newCapacity -1;
    nextLast = size;

}

这里要将原数组复制到一个新容量的数组中使用

采用的方法是将原数组元素按从0开始的下标复制到新数组，再用新数组覆盖

同时调整nextFirst与nextLast

iterator()

实现迭代器，让我们的双端队列可以迭代

即在内部嵌套一个Iterator类的实现

@Override
public Iterator<T> iterator() {
    return new ArrayDequeIterator();
}

public class ArrayDequeIterator implements Iterator<T>{
    private int pos;
    ArrayDequeIterator(){
        pos = 0;
    }
    @Override
    public boolean hasNext() {
        return pos < size;
    }

    @Override
    public T next() {
        T returnItems = get(pos);
        pos++;
        return returnItems;
    }
}

注意：接口不允许提供覆盖Object方法的默认方法，故无法在接口中提供默认方法

equals()

重写equals方法，让该方法仅比较元素相等

@Override
public boolean equals(Object o){
    if (o instanceof ArrayDeque61B<?> uAD){
        if (this.size!=uAD.size){
            return false;
        }
        for (int i = 0; i<size;i++){
            if (!Objects.equals(this.get(i), uAD.get(i))){
                return false;
            }
        }
        return true;
    }
    return false;
}

若想在instanceof中使用泛型，需要使用<?>通配符

toString()

返回自定义的string输出表示双端队列

@Override
public String toString(){
    StringBuilder stringToReturn = new StringBuilder("[");
    for (T x: this){
        stringToReturn.append(x);
        stringToReturn.append(", ");
    }
    stringToReturn.delete(stringToReturn.length()-2,stringToReturn.length());
    stringToReturn.append("]");
    return stringToReturn.toString();
}

红魔咖啡馆

【CS61B】Project1B-ArrayDeque 61B