前言

在这个项目中，我们将使用我们自己完成的双端队列来完成一个基本的吉他数据结构，在做此proj前，请确保先完成了lab3，里面有许多调试的技巧。

lab3 调试技巧

条件断点

在调试一些循环的时候，如果我们已经知道，比如下面这个循环

1
2
3


for (int i = 10; i >= 0; i--) {
    div(10, i);
}

当i = 0的时候，这个div函数就会引发除零异常。所以，我们就想跳过前面的几次循环，直接到i=0的时候去判断，这个时候应该怎么办呢？此时我们就可以右键这个断点，然后会弹出以下内容

还可以点击更多来查看一些更详细的信息，此时，我们可以输入 i == 0

这样，只有当满足这个条件的时候，断点才会触发，不满足时不会触发。

异常断点

有的时候，在某些条件下不会引发异常，随着输入或者运行时间的增加，此时可能会出现异常。这个时候我们就可以使用异常断点来进行调试。

当发生空指针异常的时候，就会触发这个异常断点，我们就可以去查看是哪些条件引起的。

总的来说，上面的这几种调试方法可以帮助我们跳过不必要的信息，从而快速到达出错的条件，方便我们调试。

proj1 双端队列

proj1的主要任务是自己实现一个双端队列，即可以在两头进行插入和删除操作的队列。这个队列要我们使用链表或数组完成，其主要实现的方法有：

1
2
3
4
5
6
7
8


public void addFirst(T item)
public void addLast(T item)
public boolean isEmpty()
public int size()
public void printDeque()
public T removeFirst()
public T removeLast()
public T get(int index) 

并且，要求addFirst、addLast、removeFirst和removeLast的时间复杂度是O(1)的，即不随队列中数据的增加而增加。

这就要求我们必须维护好两个指针，一个指向队首，一个指向队位。

基于链表的实现十分简单，指导中说可以使用双向循环链表或双向链表，我觉得还是双向链表更加简单一些，所以使用的是双向链表。

我们重点来看一下怎么用数组的方式去实现。

循环数组实现`Deque`

循环数组意思就是首位相接的数组，一般的数组，如果指针指向了末尾，而前面还有空间

1
2
3


{null, null, null, 1, 2, 3}
						 | 
						 指针在这里

当指针再移动时，就会出现索引越界。而循环数组却可以在利用前面的空间，即

rear = (rear + 1) % length

这样就可以安全移动了，所以，我们必须给移动指针封装一个安全的移动。

1
2
3


private int plueOne(int index) {
    return (index + 1) % length;
}

注意，向前移动，即 index - 1 可能会出现 -1的形式，所以我们要给index + length，不影响最后结果

1
2
3


private int minusOne(int index) {
    return (index - 1 + length) % length;
}

这样我们就可以进行实现了

注意区分 size 和 capacity，这两个是不同的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


private final int INIT_SIZE = 8;
    T[] elementData;
    private int front;
    private int rear;
    private int size;

    public ArrayDeque(){
        this.elementData = (T[]) new Object[INIT_SIZE];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

front指向的是当前队列的队首元素，而rear指向的是当前队列下一个可以插入的位置，记住这一点，实现添加和删除就很简单了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


@Override
public void addFirst(T item) {
    // 可能需要扩容
    if (size() >= capacity() * 3 / 4) {
        resize(capacity() * 2);
    }
    // 先移动，再插入
    front = minusOne(front);
    elementData[front] = item;
    size += 1;
}

实现队尾插入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    @Override
    public void addLast(T item) {
        // 可能需要扩容
        if (size() >= capacity() * 3 / 4) {
            resize(capacity() * 2);
        }
        // 先插入， 再移动
        elementData[rear] = item;
        rear = plusOne(rear);
        size++;
    }

除此之外，我们还应该封装一个get方法，也就是隐藏了数组的内部细节，get(0)就是返回队首的元素。

1
2
3
4
5


@Override
public T get(int index) {
    if (index < 0 || index >= size()) return null;
    return (T) this.elementData[(front + index) % capacity()];
}

当前队首front作为基准向后移动！

迭代器

在Deque中，还需要我们实现一个迭代器方法，需要实现Iterator<T>这个接口，并重写里面的hasNext和next方法，其实对于这种元素都是千篇一律的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


@Override
public Iterator<T> iterator() {
    return new Iterator<T>() {
        @Override
        public boolean hasNext() {
            return front != rear;
        }

        @Override
        public T next() {
            T val = elementData[front];
            front = plusOne(front);
            return val;
        }
    };
}

hasNext就是去判断当前是否还有元素，这个也好判断。next就是去返回当前值并向后迭代一次。

总结

总的内容也就是这些，其中用循环数组实现双端队列的方式比较巧妙，需要注意一些细节，再然后就是多多调试，仔细想一想。

前言

lab3 调试技巧

条件断点

异常断点

proj1 双端队列

循环数组实现Deque

迭代器

总结

循环数组实现`Deque`