The Deque API

Deque（通常发音为“deck”）是双端队列的不规则首字母缩写。双端队列是具有动态大小的序列容器，可以在两端（其前端或后端）扩展或收缩。

具体而言，任何 deque 实现都必须具有以下操作：

  • public void addFirst(T item) ：将某个类型的 T 项目添加到 deque 的前面。你可以假设这 item 从来都不是 null .
  • public void addLast(T item) ：将类型的 T 项目添加到 deque 的背面。你可以假设这 item 从来都不是 null .
  • public boolean isEmpty() ：如果 deque 为空，则返回， false 否则返回 true 。
  • public int size() ：返回 deque 中的项数。
  • public void printDeque() ：从头到尾打印 deque 中的项目，用空格分隔。打印完所有项目后，打印出新行。
  • public T removeFirst() ：删除并返回 deque 前面的项目。如果不存在此类项，则返回 null 。
  • public T removeLast() ：删除并返回 deque 背面的项目。如果不存在此类项，则返回 null 。
  • public T get(int index) ：获取给定索引处的项，其中 0 是前面，1 是下一个项，依此类推。如果不存在此类项，则返回 null 。不得改动deque！

此外，我们还希望我们的两个 Deque 实现这两个特殊方法：

  • public Iterator<T> iterator() ：我们将要创建的 Deque 对象是可迭代的（即 Iterable<T> ），因此我们必须提供此方法来返回迭代器。
  • public boolean equals(Object o) ：返回参数 o 是否等于 Deque。 o 如果它是 Deque，并且如果它以相同的顺序包含相同的内容（由泛型 T equals 方法支配）则被认为是相等的。（添加 2/12：您需要为此使用 instance of 关键字。阅读here了解更多信息）

添加 2/12：您不应该实现接口 Deque ，而应该只实现 Iterable 两个实现 LinkedListDeque 和 ArrayDeque .如果您执行前者，我们的自动评分器将为您提供 API 错误。

您将在第 11 讲 （2/12） 中了解 an Iterator 是什么，所以现在不要担心。这个项目旨在随着您从讲座和讨论中学到更多东西而一点一点地完成，这是练习您在本课程中学到的所有东西的绝佳机会。

您的类应该接受任何泛型类型（而不仅仅是整数）。有关创建和使用泛型数据结构的信息，请参阅 lecture 5。请务必密切注意最后一张幻灯片中关于泛型的经验法则。

在此项目中，您将为 Deque 接口提供两种实现：一种由链表提供支持，另一种由调整大小数组提供支持

项目任务

Linked List Deque

作为第一个 deque 实现，您将构建基于 LinkedListDeque 链表的类。

您的操作受以下规则的约束：

  • add 并且 remove 操作不得涉及任何循环或递归。单个此类操作必须花费“恒定时间”，即执行时间不应取决于 deque 的大小。这意味着您不能使用遍历 deque 的所有/大多数元素的循环。
  • get 必须使用迭代，而不是递归。
  • size 必须花费恒定的时间。
  • LinkedListDeque 循环使用 for-each 循环所需的时间应与项目数成正比。
  • 不要保留对不再在 deque 中的项目的引用。程序在任何给定时间使用的内存量必须与项数成正比。例如，如果将 10,000 个项目添加到 deque，然后删除 9,999 个项目，则生成的内存使用量应等于 1 个项目的 deque，而不是 10,000。请记住，Java 垃圾收集器将在且仅当没有指向该对象的指针时为我们“删除”内容。

实现上面“Deque API”部分中列出的所有方法。

此外，您还需要实现：

  • public LinkedListDeque() ：创建一个空的链表取消。
  • public T getRecursive(int index) ：与 get 相同，但使用递归。

虽然这听起来很简单，但有许多设计问题需要考虑，您可能会发现实现比您预期的更具挑战性。请务必查阅有关双向链表的讲座，特别是关于哨兵节点的幻灯片：两个哨兵拓 two sentinel topology扑和圆形哨兵拓扑circular sentinel topology。我更喜欢循环方法。

5f80de28514b0bc51dc944e1a7129ac

e38a8427e6351cf3a2733e4708df329

答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package deque;
import java.util.Iterator;

public class LinkedListDeque<T> {

    public class Node {
        private T item;
        private Node next;
        public Node prev;
        Node(T i, Node p, Node n) {
            item = i;
            prev = p;
            next = n;
        }
    }

    private int size;
    private final Node sentinel;
    public LinkedListDeque() {
        sentinel = new Node(null ,null, null);
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
        size = 0;
    }

    public LinkedListDeque(T i) {
        sentinel = new Node(i, null, null);
        sentinel.next = new Node(i, sentinel, sentinel);
        sentinel.prev = sentinel.next;
        size = 1;
    }

    /** Adds an item of type T to the front of the deque.
     * You can assume that item is never null. */
    public void addFirst(T item) {
        sentinel.next = new Node(item, sentinel, sentinel.next);
        size += 1;
    }

    /** Adds an item of type T to the back of the deque.
     * You can assume that item is never null. */
    public void addLast(T item) {
        sentinel.prev = new Node(item, sentinel.prev, sentinel);
        sentinel.prev.prev.next = sentinel.prev;
        size += 1;
    }

    /** Returns true if deque is empty, false otherwise. */
    public boolean isEmpty() {
        return size() <= 0;
    }

    /** Returns the number of items in the deque. */
    public int size() {
        return size;
    }

    /** Prints the items in the deque from first to last, separated by a space.
     * Once all the items have been printed, print out a new line. */
    public void printDeque() {
        int i = size();
        Node p = sentinel;
        while (i > 0) {
            System.out.print(p.next.item);
            System.out.print(" ");
            p = p.next;
            i--;
        }
    }

    /** Removes and returns the item at the front of the deque.
     * If no such item exists, returns null. */
    public T removeFirst() {
        if (size <= 0) {
            return null;
        }
        size--;
        T item = sentinel.next.item;
        sentinel.next.next.prev = sentinel.next.prev;
        sentinel.next = sentinel.next.next;
        if (size == 0) {
            return item;
        }
        return item;
    }

    /** Removes and returns the item at the back of the deque.
     * If no such item exists, returns null. */
    public T removeLast() {
        if (size <= 0) {
            return null;
        }
        size--;
        T item = sentinel.prev.item;
        sentinel.prev.prev.next = sentinel;
        sentinel.prev = sentinel.prev.prev;
        if (size == 0) {
            return item;
        }
        return item;
    }

    /** Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth.
     * If no such item exists, returns null. Must not alter the deque! */
    public T get(int index) {
        if (index > size()) {
            return null;
        }
        Node p = sentinel;
        while (index > 0) {
            p = p.next;
            index--;
        }
        return p.item;
    }

    private T getRecursivehelper(int index, Node s) {
        if (index == 0) {
            return s.item;
        } else {
            return getRecursivehelper(index - 1, s.next);
        }
    }
    /** Same as get, but uses recursion. */
    public T getRecursive(int index) {
        return getRecursivehelper(index, sentinel.next);
    }
}

Array Deque

对于此实现，您的操作受以下规则的约束：

  • add 并且 remove 必须花费恒定的时间，除非在调整大小操作期间。
  • get 并且 size 必须花费恒定的时间。
  • 数组的起始大小应为 8。
  • 程序在任何给定时间使用的内存量必须与项数成正比。例如，如果将 10,000 个项目添加到 deque，然后删除 9,999 个项目，则不应仍使用长度为 10,000ish 的数组。对于长度为 16 或更大的数组，使用系数应始终至少为 25%。这意味着，在执行将数组中的元素数控制在数组长度的 25% 以下的删除操作之前，应减小数组的大小。对于较小的阵列，使用系数可以任意降低。

实现上面“Deque API”部分中列出的所有方法。

此外，您还需要实现：

  • public ArrayDeque() ：创建一个空数组 deque。

您将需要以某种方式跟踪哪些数组索引包含 Deque 的正面和背面元素。我们强烈建议您在本练习中将数组视为循环数组。换言之，如果你的前面项位于零位置，而 u addFirst ，则新的前面应该循环回数组的末尾（因此 deque 中的新前面项将是基础数组中的最后一个项）。与非循环方法相比，这将导致更少的头痛。有关更多详细信息，请参阅项目 1 project 1 demo slides 演示幻灯片。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package deque;

public class ArrayDeque<T> {
    private T[] item;
    private int size;
    private int nextFirst;
    private int nextLast;

    public ArrayDeque() {
        item = (T []) new Object[8];
        size = 0;
        nextFirst = 1;
        nextLast = 2;
    }

    public ArrayDeque(ArrayDeque other) {
        item = (T []) new Object[8];
        System.arraycopy(other.item, 0, item, 0, size);
        size = other.size;
        nextFirst = other.nextFirst;
        nextLast = other.nextLast;
    }

    private int ForwardValue(int n) {
        n--;
        if (n < 0) {
            n = item.length - 1;
        }
        return n;
    }

    private int BackValue(int n) {
        n++;
        if (n >= item.length) {
            n = 0;
        }
        return n;
    }

    /** before performing a remove operation that will bring the number of elements in the array under 25% the length of the array, 
     * resize the size of the array down. */
    private void resize(int x) {
        T[] a = (T[]) new Object[x];
        if ((size < item.length / 4) && (size > 16)) {
            System.arraycopy(item, nextFirst+1, a, 0, size);
            nextFirst = -1;
            nextLast = size;
        } else {
            System.arraycopy(item, 0, a, 0, nextFirst+1);
            System.arraycopy(item, nextLast, a, a.length - item.length + nextFirst + 1, item.length - nextFirst -1);
            nextFirst = a.length - item.length + nextFirst;
        }
        item = a;
    }

    /** Adds an item of type T to the front of the deque.
     * You can assume that item is never null. */
    public void addFirst(T i) {
        if (size == item.length) {
            resize(size * 2);
            while (item[nextFirst] != null) {
                nextFirst = ForwardValue(nextFirst);
            }
        }
        item[nextFirst] = i;
        size++;
        nextFirst = ForwardValue(nextFirst);
    }

    /** Adds an item of type T to the back of the deque.
     * You can assume that item is never null. */
    public void addLast(T i) {
        if (size == item.length) {
            resize(size * 2);
            while (item[nextLast] != null) {
                nextLast = BackValue(nextLast);
            }
        }
        item[nextLast] = i;
        size++;
        nextLast = BackValue(nextLast);
    }

    /** Returns true if deque is empty, false otherwise. */
    public boolean isEmpty() {
        return size <= 0;

    }

    /** Returns the number of items in the deque. */
    public int size() {
        return size;
    }

    /** Prints the items in the deque from first to last, separated by a space.
     * Once all the items have been printed, print out a new line. */
    public void printDeque() {
        for (int i = 0; i < size; i++) {
            System.out.println(item[(nextFirst + i + 1) % item.length]);
        }
    }

    /** Removes and returns the item at the front of the deque.
     * If no such item exists, returns null. */
    public T removeFirst() {
        if (size <= 0) {
            return null;
        }
        if ((size < item.length / 4) && (size > 16)) {
            resize(item.length / 4);
        }
        T curValue = item[BackValue(nextFirst)];
        item[BackValue(nextFirst)] = null;
        nextFirst = BackValue(nextFirst);
        size--;
        return curValue;
    }

    /** Removes and returns the item at the back of the deque.
     * If no such item exists, returns null. */
    public T removeLast() {
        if (size <= 0) {
            return null;
        }
        if ((size < item.length / 4) && (size > 16)) {
            resize(item.length / 4);
        }

        T curValue = item[ForwardValue(nextLast)];
        item[ForwardValue(nextLast)] = null;
        nextLast = ForwardValue(nextLast);
        size--;
        return curValue;
    }

    /** Gets the ith item in the list (0 is the front). */
    public T get(int i) {
        if (i >= size()) {
            return null;
        }
        return item[(nextFirst + i + 1) % item.length];
    }
}

Deque Interface(接口)

回想一下，我们通过以下方法定义了 Deque API 或行为：

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)

由于程序将依赖于此行为，因此提供什么 Deque 实现对它来说并不重要，或者 LinkedListDeque ， ArrayDeque 并且应该同时适用于两者。为了实现这一点，我们将使用接口的强大功能。

在包含上述所有方法的新 Deque.java 文件中创建一个接口。在 IntelliJ 中，使用“New → Java Class”。IntelliJ 会假设你想要一个类，所以一定要把 class 关键词换成 interface 。不要忘记声明 Deque 接口是包的一部分 deque ！

修改你的 LinkedListDeque 或 ArrayDeque ，以便它们通过添加到 implements Deque<T> 声明类存在的行来实现 Deque 接口。

1
2
public class ArrayDeque<T> implements Deque<T>
public class LinkedListDeque<T> implements Deque<T>

向覆盖方法的每个 Deque 方法添加 @Override 标记。

现在，在接口中 Deque ，给出 isEmpty() 一个 default 实现，如果 size() 是 0 ，则返回 true .由于 your LinkedListDeque 和 实现接口 Deque ，给定默认 isEmpty() 实现，您可以从之前实现的 LinkedListDeque 和 ArrayDeque ArrayDeque 中删除该方法。

现在，在实现 Deque 接口并从 LinkedListDeque 和 ArrayDeque 实现中删除 isEmpty() 方法后，代码将在完整的自动分级器上编译。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package deque;

public interface Deque<T> {

    void addFirst(T i);

    void addLast(T i);

    default boolean isEmpty() {
        return this.size() <= 0;
    }

    int size();

    void printDeque();

    T removeFirst();

    T removeLast();

    T get(int i);
}

Guitar Hero

在项目的这一部分中，我们将创建另一个包，用于使用我们刚刚制作的 deque 包生成合成乐器。我们将有机会使用我们的数据结构来实现一种算法，该算法允许我们模拟吉他弦的弹拨。

The GH2 Package

该 gh2 包只有一个主要组件，您将对其进行编辑：

我们为您提供了框架代码 GuitarString ，您将在其中使用在本项目第一部分中创建的 deque 包。

GuitarString

我们想要完成 GuitarString 文件，它应该使用包 deque 来复制拨弦的声音。我们将使用 Karplus-Strong 算法，该算法很容易通过 Deque .

The Karplus-Algorithm is simply the following three steps:
Karplus算法只是以下三个步骤：

  1. 用随机噪声（ double 值介于 -0.5 和 0.5 之间）替换 a Deque 中的每个项目。
  2. 去掉Deque 最前面的double值，并和Deque 下一个double （提示：使用 removeFirst() 和 get() )取平均值 然后 乘以能量衰减因子 0.996（我们称之为整个量 newDouble ）。然后，添加到 newDouble 到Deque的最后 .
  3. 播放您在步骤2中退出队列的double (newDouble)。回到步骤2(并不断重复)。

或者从视觉上看，如果如 Deque 顶部所示，我们将删除 0.2，将其与 0.4 合并形成 0.2988，添加 0.2988，然后播放 0.2。

karplus-strong

您可以使用该 StdAudio.play 方法播放值 double 。例如 StdAudio.play(0.333) ，会告诉扬声器的振膜将自己伸展到其总范围的 1/3， StdAudio.play(-0.9) 会告诉它几乎向后伸展它的小心脏，几乎尽可能远。扬声器振膜的运动会取代空气，如果你以很好的模式取代空气，这些干扰将被你的意识解释为令人愉悦，这要归功于数十亿年的进化。有关详细信息，请参阅此页面。如果你只是这样做 StdAudio.play(0.9) ，再也不玩任何东西，那么图像中显示的隔膜将只是静止不动地前进的 9/10。

完成 GuitarString.java ，以便实现 Karplus-Strong 算法的第 1 步和第 2 步。请注意，您必须在 GuitarString 构造函数中用零填充缓冲区 Deque 。第 3 步将由 GuitarString 类的客户端完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package gh2;
import deque.*;
// import deque.Deque;


//Note: This file will not compile until you complete the Deque implementations
public class GuitarString {
    /** Constants. Do not change. In case you're curious, the keyword final
     * means the values cannot be changed at runtime. We'll discuss this and
     * other topics in lecture on Friday. */
    private static final int SR = 44100;      // Sampling Rate
    private static final double DECAY = .996; // energy decay factor

    /* Buffer for storing sound data. */

    private Deque<Double> buffer;

    /* Create a guitar string of the given frequency.  */
    public GuitarString(double frequency) {
        int capacity = (int) Math.round(SR / frequency);
        buffer = new ArrayDeque<Double>();
        for (int i = 0; i < capacity; i++) {
            buffer.addFirst(0.0);
        }
    }


    /* Pluck the guitar string by replacing the buffer with white noise. */
    public void pluck() {
        //       Make sure that your random numbers are different from each
        //       other. This does not mean that you need to check that the numbers
        //       are different from each other. It means you should repeatedly call
        //       Math.random() - 0.5 to generate new random numbers for each array index.
        double temp;
        Deque<Double> NewBuffer = new ArrayDeque<Double>();
        for (int i = 0; i < buffer.size(); i++) {
            double r = Math.random() - 0.5;
            temp = buffer.get(i);
            NewBuffer.addLast(temp - r);
        }
        buffer = NewBuffer;
    }

    /* Advance the simulation one time step by performing one iteration of
     * the Karplus-Strong algorithm.
     */
    public void tic() {
        double NewDouble;
        double temp = buffer.get(0);
        buffer.removeFirst();
        NewDouble = DECAY * 0.5 * (temp + buffer.get(0));
        buffer.addLast(NewDouble);
    }

    /* Return the double at the front of the buffer. */
    public double sample() {
        return buffer.get(0);
    }
}

GuitarHero

非作业，单纯好玩

考虑创建一个类似于 GuitarHeroLite 的程序 GuitarHero ，但支持 37Hz 到 110Hz 的半音阶上总共 880 个音符。使用以下 37 个键来表示键盘，从最低音符到最高音符：

1
String keyboard = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";

这种键盘排列模仿钢琴键盘：“白键”位于键盘的 qwerty 和 zxcv 行上，“黑键”位于键盘的 12345 和 asdf 行上。

字符串键盘的第 i 个字符对应于 image-20240129042827790 的频率，因此字符“q”为 110Hz，“i”为 220Hz，“v”为 440Hz，“”为 880Hz。甚至不要考虑包含 37 个单独的 GuitarString 变量或 37 路 if 语句！相反，创建一个包含 37 GuitarString 个对象的数组，并用于 keyboard.indexOf(key) 确定键入了哪个键。确保如果按下的键与您的 37 个音符之一不对应，您的程序不会崩溃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package gh2;
import deque.ArrayDeque;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.introcs.StdAudio;

public class GuitarHero {
    public static void main(String[] args) {
        final String keyboard = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";
        final int FREQ = 440;
        ArrayDeque<GuitarString> guitar = new ArrayDeque<>();
        int index = -1;
        while (true) {
            /* check if the user has typed a key; if so, process it */
            if (StdDraw.hasNextKeyTyped()) {
                char key = StdDraw.nextKeyTyped();
                int i = keyboard.indexOf(key);
                double freq = FREQ * Math.pow(2, (double) (i - 24) /12);
                guitar.addLast(new GuitarString(freq));
                if (guitar.size() > index) {
                    index++;
                }
                guitar.get(index).pluck();
                }
            double sample = 0.0;

            for (int j = 0; j < guitar.size(); j++) {
                sample += guitar.get(j).sample();
            }

            /* play the sample on standard audio */
            StdAudio.play(sample);

            /* advance the simulation of each guitar string by one step */
            for (int j = 0; j < guitar.size(); j++) {
                guitar.get(j).tic();
            }

        }
    }
}

Even More Fun 更有趣

这部分作业没有评分，只是为了好玩。

  • Harp 字符串：在包中 gh2 创建一个 Harp 类。在将新值排入队列之前翻转新值的符号 tic() 会将声音从吉他式变为竖琴式。您可能希望使用衰减因子来提高真实感，并将缓冲区大小调整两倍，因为 tic() 自然共振频率会因变化而减半。
  • Drums：在包中 gh2 创建一个 Drum 类。在将新值排入队列之前，以 0.5 的概率翻转新值的符号 tic() 将产生鼓声。衰减系数为 1.0（无衰减）将产生更好的声音，您需要调整使用的频率集。
  • 吉他在 6 根物理弦之一上弹奏每个音符。为了模拟这种情况，您可以将 GuitarString 实例分成 6 组，当一个字符串被摘取时，将该组中的所有其他字符串清零。
  • 钢琴带有一个阻尼踏板，可用于使琴弦静止。您可以通过在按住某个键（例如 Shift）的迭代中更改衰减因子来实现此目的。
  • 虽然我们使用了平等的气质，但当音乐音程跟随正音调系统中的小部分时，耳朵会发现它更令人愉悦。例如，当音乐家使用铜管乐器演奏完美的五度和声时，频率之比为 3/2 = 1.5，而不是 27/12 ∼ 1.498。编写一个程序，其中每对连续的音符都只有语调。

Why It Works 为什么有效

使Karplus-Strong算法起作用的两个主要组件是环形缓冲区反馈机制和平均操作。

  • The ring buffer feedback mechanism. The ring buffer models the medium (a string tied down at both ends) in which the energy travels back and forth. The length of the ring buffer determines the fundamental frequency of the resulting sound. Sonically, the feedback mechanism reinforces only the fundamental frequency and its harmonics (frequencies at integer multiples of the fundamental). The energy decay factor (.996 in this case) models the slight dissipation in energy as the wave makes a round trip through the string.
    环形缓冲区反馈机制。环形缓冲器模拟能量来回传播的介质（两端系在一起的绳子）。环形缓冲器的长度决定了所产生声音的基频。在声音上，反馈机制仅增强基频及其谐波（基频整数倍的频率）。能量衰减因子（在本例中为 .996）模拟了波在弦上往返时能量的轻微耗散。
  • The averaging operation. The averaging operation serves as a gentle low-pass filter (which removes higher frequencies while allowing lower frequencies to pass, hence the name). Because it is in the path of the feedback, this has the effect of gradually attenuating the higher harmonics while keeping the lower ones, which corresponds closely with how a plucked guitar string sounds.
    平均操作。平均操作用作温和的低通滤波器（它去除较高频率，同时允许较低频率通过，因此得名）。因为它在反馈的路径中，所以具有逐渐衰减高次谐波同时保持低次谐波的效果，这与弹拨吉他弦的声音非常吻合。

总结:

通过项目一，我学到了以下东西:

  • 如何构造出一个Deque API
  • package的用法
  • 接口的创立
  • 数列的一个使用实例
  • 更高效的调试方法

困难复盘点:

Linked List Deque

这个部分比较困难的是add和remove方法，刚开始会错意了，以为环状列表中，最后一个不指向哨兵节点导致一开始尝试错误。

后面比较麻烦的是prev和next的指向问题，我借助了可视化+调试慢慢得完善好。

Array Deque

经常遇到NullPointerException或者OutIndex这些问题，于是使用了异常断点this instanceof NullPointerException+可视化工具来和条件断点和恢复按钮判断出出错点

最困难的地方莫过于resize方法分扩大列表和缩小列表这两种情况来讨论。我的解决方法是先建立一个新的列表然后借助System.arraycopy(src, srcPos, dest, destPos, length)来快速得复制，其中复制的参数我根据可视化的列表图像和nextFirst和item.length慢慢得摸索，最终完成。

其中扩大列表应该分有多种扩增方法，我最开始是直接在后面扩增开了，导致remove方法无法找到解决方法，最后选择在nextFirst和nextLast中间扩增开，这样子remove的时候，nextFirst的值会慢慢的增加，然后成功删除掉首尾的值。