本项目主要分为两部分，数据结构部分和应用部分。在数据结构部分，我分别使用双向循环链表和循环数组实现双端队列（Double Ended Queue，下简称Deque），并编写随机对比测试，检查两种实现的行为是否一致。在应用部分，我按照课程提供的算法和框架，使用双端队列完成吉他弦声音合成。此外，在Extra Credit（EC）中，我按照要求实现了一个简易autograder，通过与参考实现对比发现错误，并输出导致错误的操作序列。
2021年版本的CS61B，project指引还相对简陋，本项目的文档 "will provide relatively little scaffolding. In other words, we’ll say what you should do, but not how."
文档只给了Deque的api，因此，我需要从创建类开始，自行组织内部数据结构、成员变量、辅助方法及各个接口的实现，而不是在已经搭建好的代码框架中完成部分代码。LinkedListDeque和ArrayDeque的代码由我自己编写完成，见ArrayDeque.java和LinkedListDeque.java
在ArrayDeque中，我使用循环数组存储元素，通过nextFirst、nextLast和size维护队列状态。比较tricky的是元素可能跨越数组末尾，队列中的逻辑位置与数组下标并不直接对应（例如在几次的双端插入删除后，逻辑上的“第一个元素”需要靠nextFirst去定位），因此需要通过取模运算处理下标回绕，并将访问位置转换为实际数组下标。
此外，当ArrayDeque底层的数组满了时，扩容时将容量翻倍以实现单次插入的均摊时间复杂度为O(1)，当容量不少于16，且删除后使用率低于25%时，容量将缩小一半。这既避免了每次插入都重新分配数组，也能在大量删除后释放多余空间。
扩缩容时，原数组中的元素可能分布在数组两端，不能直接按照实际数组下标顺序复制。我先找到逻辑上的“第一个元素”，然后按队列顺序将元素搬移到新数组，再重新设置nextFirst和nextLast，保证扩缩容前后的元素顺序一致。
我认为LinkedListDeque中有两点可以体现我的编程能力，第一是双向循环链表的实现，包含基本的addFirst、removeLast、get等操作，插入和删除时，需要正确维护相邻节点的前后引用，并处理空队列、单元素队列等情况。在此基础上，我还实现了iterator和equals方法，支持逐个遍历元素，以及按元素内容和顺序比较不同的Deque实现。
第二是getRecursive方法，要求用递归的方式实现get功能，但是LinkedListDeque本身并不是递归的结构，不能直接在getRecursive里递归，我编写了一个接收当前节点和剩余步数的helper method。每次递归向后移动一个节点，并将剩余步数减一；剩余步数为零时返回当前元素，遇到哨兵节点则返回null，这个方法设为private并在getRecursive里调用，保持了对外接口的简洁。
我通过接口Deque<T>统一两种队列实现的操作。在声音合成部分，GuitarString.java中通过该接口使用队列，使声音合成算法不依赖底层采用数组还是链表，应用代码通过统一接口使用deque，无需了解内部细节.
在MaxArrayDeque中，我通过继承已经实现的ArrayDeque，仅增加查找最大元素的功能，并通过Comparator支持不同的比较规则，减少重复代码。
先通过测试检测问题，也可以顺便定位到需要debug的位置，本项目的LinkedListDequeTest.java就对 LinkedListDeque 和 ArrayDeque 进行了测试，其中最后的随机测试以及ArrayDeque部分的测试是我写的，随机对比测试让 ArrayDeque 和 LinkedListDeque 执行相同的随机操作，并比较队列大小及相关操作的返回值。
相比只检查几个手动构造的例子，随机测试能够检查更多操作组合，有助于发现连续操作后出现的错误。
此外，本项目的EC中，我实现了一个与参考实现对比发现错误的autograder，为了让测试失败后能获得具体的排查线索，我使用 StringBuilder 持续记录实际执行的操作及其参数，并将操作序列作为断言失败时的提示信息。这样不仅能够发现结果不一致，还能知道经过哪些操作后出现了错误。
下面举例做project过程中遇到的问题以及如何解决的
在测试LinkedListDeque时，测试失败，而且连实际得到的是什么都没有打印出来，对写的测试进行调试，发现创建LinkedListDeque时，并没有按照构造函数的要求让sentinel指向新建的Node，而是直接变成了null，在创建LinkedListDeque处打断点，step into后发现并未进入我写的构造函数，所以定位到构造函数出现问题，后来发现构造函数的signature写成了public void LinkedListDeque()，于是去掉void
去掉void后，在创建LinkedListDeque处打断点调试，先step over看构造函数是否成功修复，成功创建了sentinel，但是它指向的Node的 prev 和 next 都是null而没有指向自己，再次step into进入Node的构造函数，发现传入的 prev 和 next 都是null而不是sentinel，于是定位到构造函数的参数写错，发现原本写的是 sentinel = new Node(null, sentinel, sentinel); ，在创建Node时sentinel还没被赋值，所以默认是null，修改后问题解决。
在随机测试中，出现了"the return value of "deque.ArrayDeque.get(int)" is null"的报错，即对非空队列访问逻辑上的最后一个元素时，get 返回了 null，不符合预期。我通过断点检查发现，向空队列调用 addLast 后，元素实际存放在数组下标 0，而 get 根据 nextFirst 计算出的队首位置却是下标 1。
进一步检查发现，我将 nextFirst 和 nextLast 都初始化为 0，没有使初始状态符合“实际队首位于 nextFirst 后一个位置”的约定。将 nextFirst 初始化为 array.length - 1 后，get 计算出的队首位置与元素实际存储的位置一致
事实上，关于debug的知识我都是在学习CS61B的过程中学习的
- 写完代码后，写对应的测试，一般是比较简单的unit test，代码操作功能较多时可以写数量较多的随机测试
- 运行测试，如果失败，根据报错定位错误位置，或者了解是什么操作导致了失败，对错误位置打断点调试
- 如果无法定位，对测试代码从头开始调试，遇到方法时，先预期结果，然后step over检查方法带来的变化是否符合预期（当然如果step over后和预期结果相同也未必说明该方法正确实现），如果跟预期结果不符，检查调用前传入的参数和相关变量是否正常，然后step into该方法进一步排查。例如上面的预期创建出sentinel → 实际为 null → 怀疑初始化没有执行 → 跟踪构造过程 → 发现没进入预期中的构造函数 → 发现方法声明错误
- 遇到难定位的问题，向ai提问，利用ai进行排查
- 修改后再次运行测试，如果依然不通过，定位新的问题，也有可能原代码不止一个错误，重复上述过程
关于我在这门课目前学习到的debug知识，可见记录的lab2和lab3中的debug及测试的笔记