项目 1B: 数组双端队列 61B
截止日期：2月12日星期一，太平洋时间晚上11:59
常见问题
每个作业都会有一个常见问题解答链接在顶部。您也可以通过在URL末尾添加"/faq"来访问。Project 1B的常见问题解答位于 这里 。
请注意，此项目的提交令牌有限。更多详细信息请参阅 提交给自动评分器 。
介绍
在Project 1A中，我们构建了
LinkedListDeque61B
。现在我们将看到使用
后备数组
而不是链接节点的
Deque61B
接口的不同实现。
在Project 1B结束时，您将……
- 深入理解数据结构中后备数组的实现。
- 在使用测试和测试驱动开发来验证这些数据结构的正确性方面有更多经验。
查看 项目1B幻灯片 了解更多可视化的技巧。
查看 入门视频 了解规范概述。
我们将提供相对较少的脚手架支持。换句话说，我们会告诉你应该做什么，但不会告诉你怎么做。
本节假设你已经观看并完全消化了直到
ArrayList讲座（第7讲）的所有课程内容。
对于这个项目，你必须独立完成！请仔细阅读 协作与作弊政策 ，了解这具体意味着什么。特别是，不要在网上寻找解决方案。
（仍然）不言而喻，你在实现中不得使用任何内置的
java.util数据结构！整个重点就是构建你自己的版本！有几个地方你可以在测试之外使用特定的数据结构，我们会清楚地说明在哪里。
代码风格
与项目1A一样， 我们将强制执行代码风格 。你必须遵循 代码风格指南 ，否则你会在自动评分器上被扣分。
你可以也应该使用 CS 61B 插件在本地检查你的代码风格。 对于因未检查代码风格而导致的问题，我们不会取消提交次数限制。
获取框架文件
按照
作业工作流程指南
中的说明获取框架代码并在 IntelliJ 中打开。对于这个项目，我们将在
proj1b
目录中工作。
你会看到你的仓库中出现一个
proj1b
目录，其结构如下：
proj1b
├── src
│ └── Deque61B.java
└── tests
└── ArrayDeque61BTest.java
如果你遇到某种错误，请停下来，要么仔细阅读
git 常见问题
来解决，要么在办公时间或 Ed 上寻求帮助。与盲目猜测和尝试 git 命令相比，这样做可能会为你省去很多麻烦。如果你发现自己想使用 Google 推荐的命令，比如
force push
，
请不要这样做
。
不要使用强制推送，即使你在 Stack Overflow 上找到的帖子说要这样做！
你也可以观看 Hug 教授的 演示视频 了解如何开始，如果你遇到一些 git 问题，可以观看这个 视频 。
双端队列：抽象数据类型和API
如果你需要复习
Deque61B
，请参考
项目1A规范
和
Deque61B.java
文件。
创建文件
首先创建一个名为
ArrayDeque61B
的文件。该文件应该创建在
proj1b/src
目录中。要做到这一点，右键点击
src
目录，选择"新建 -> Java 类"，然后给它命名为
ArrayDeque61B
。
就像你在项目1A中做的那样，我们希望我们的
ArrayDeque61B
能够容纳几种不同的类型。要实现这一点，你应该编辑你的类声明，使其变为：
public class ArrayDeque61B<T>
回想一下讲座内容，我们使用
T
还是其他字符串（比如
ArrayDeque61B<Glerp>
）实际上并不重要。但是，为了与其他 Java 代码保持一致，我们建议使用
<T>
。
我们还想告诉 Java，每个
ArrayDeque61B
都是一个
Deque61B
，这样用户就可以编写像
Deque61B<String> lld1 = new ArrayDeque61B<>();
这样的代码。要实现这一点，请修改你的类声明，使其变为：
public class ArrayDeque61B<T> implements Deque61B<T>
完成这一步后，你可能会看到整个类声明下面有一条红色波浪线。这是因为你说你的类实现了一个接口，但你还没有实际实现任何接口方法。
将鼠标悬停在红线上，当 IntelliJ 弹出窗口出现时，点击"Implement methods"按钮。确保列表中的所有方法都被高亮显示，然后点击"OK"。现在，你的类应该充满了一堆空的方法声明。这些就是你在这个项目中需要实现的方法！
最后，你应该创建一个空的构造函数。要做到这一点，将以下代码添加到你的文件中，暂时将构造函数留空。
public ArrayDeque61B() {
}
注意：你也可以通过点击"Code"，然后点击"Generate"，再点击"Constructor"来生成构造函数，不过我更喜欢自己输入代码的方式。
现在你准备好开始了！
ArrayDeque61B
作为你的第二个双端队列实现，你将构建
ArrayDeque61B
类。这个双端队列
必须
使用 Java 数组作为后备数据结构。
如果你认为有必要，你可以在
ArrayDeque61B.java
中添加任何私有辅助类或方法。
构造函数
你需要以某种方式跟踪哪些数组索引保存着双端队列的头部和尾部元素。我们
强烈建议
你在这个练习中将数组视为循环的。换句话说，如果你的头部元素在位置
0
，而你执行
addFirst
，新的头部应该循环回到数组的末尾（因此双端队列中的新头部元素将是底层数组中的最后一个元素）。与非循环方法相比，这将大大减少令人头疼的问题。
查看 项目1B演示幻灯片 了解更多详情。特别要注意的是，虽然概念上的双端队列和数组包含相同的元素，但它们的顺序不同。
我们建议使用 Java 内置
Math
类中的
floorMod(int a, int b)
方法来帮助你设计循环方法。当 a 为负数时，
a % b
可能返回负数，而
floorMod(int a, int b)
总是返回非负数。实际上，这意味着输出将与除数具有相同的符号。以下是使用
floorMod(int a, int b)
方法的几个示例：
int value1 = Math.floorMod(16, 16); // value1 == 0
int value2 = Math.floorMod(-1, 16); // value2 == 15
int value3 = Math.floorMod(20, 16); // value3 == 4
你可以通过在文件顶部添加以下导入语句来使用
floorMod(int a, int b)
方法：
import java.lang.Math;
。
由于
超出本课程范围的原因
，你无法在 Java 中创建泛型数组（例如
new T[1000]
）。你需要使用语法
(T[]) new Object[1000]
来代替。
声明必要的实例变量，并实现构造函数。
后备数组的初始大小 必须 为
8。
addFirst
and
addLast
和之前一样，实现
addFirst
和
addLast
。这两个方法
不得
使用循环或递归。单个添加操作必须花费"常数时间"，也就是说，无论双端队列有多大（有一个例外），添加一个元素应该花费大致相同的时间。这意味着你不能使用遍历双端队列所有/大部分元素的循环。
扩容
我们建议你先完成其他方法，验证它们在不调整大小的情况下能正常工作，然后再回来处理调整大小的问题。
"常数时间"要求的例外情况是当数组填满时，你需要"调整大小"以获得足够的空间来添加元素。在这种情况下，你可以花费"线性时间"在添加元素之前调整数组大小。
正确地调整数组大小非常棘手，需要深入思考。试着手工画出各种方法。你可能需要相当长的时间才能想出正确的方法，我们鼓励你与同学或助教讨论大体思路。确保你的实际实现是 由你独立完成的 。
确保按几何因子调整大小。
我们 不 建议在循环实现中使用
arraycopy。它可以工作，但会导致实现比必要的复杂得多（也更难调试！）。相反，我们建议你提前思考如何实现
get，并以某种方式使用for循环。
实现
addFirst和addLast，并编写测试来验证它们是否正确。确保添加足够多的元素，以便你的后备数组进行调整大小！有关调整大小的更多信息，请查看 这些幻灯片 。
get
与
LinkedListDeque61B
不同，这个方法必须花费
常数时间
。
和之前一样，当索引无效（太大或为负数）时，
get
应该返回
null
。在这种情况下，你应该忽略
Deque61B.java
中的框架代码注释。
在你编写测试并验证它们失败之后 ，实现
get。
是Empty
and
size
这两个方法必须花费 常数时间 。也就是说，任一方法完成执行所需的时间不应该取决于双端队列中有多少元素。
为
是Empty和size方法 编写测试 ，并检查它们是否失败。然后，实现这些方法。
toList
toList
将继续用于测试你的
Deque61B
。
编写
toList
方法。方法的第一行应该类似于
List<T> returnList = new ArrayList<>()
。
这是你被允许使用 Java 数据结构的一个位置。
如果你使用
toList，后面的一些方法可能看起来很简单。 你不得在ArrayDeque61B内部调用toList；有一个测试会检查这一点。
提示 其他方法之一可能对实现这个方法有帮助。
实现
toList。这次没有给你测试，所以你需要自己编写！
剩下的就是测试和实现所有剩余的方法。在本项目的其余部分，我们将在高层次上描述我们建议的步骤。我们 强烈鼓励 你按照给出的顺序遵循剩余的步骤。特别是， 在实现方法功能之前先编写测试 。这被称为"测试驱动开发"，有助于确保你在做事之前知道你的方法应该做什么。
removeFirst
and
removeLast
最后，编写一些测试来测试
removeFirst
和
removeLast
的行为，并再次确保测试失败。
不要保留对已不在双端队列中的项目的引用。
removeFirst
和
removeLast
不得
使用循环或递归。与
addFirst
和
addLast
一样，这些操作必须花费"常数时间"。有关这意味着什么的更多信息，请参阅编写
addFirst
和
addLast
的部分。
缩容
你的程序在任何给定时间使用的内存量必须与项目数量成正比。例如，如果你向双端队列添加 10,000 个项目，然后移除 9,999 个项目，你不应该仍然使用一个可以容纳 10,000 个项目的数组。对于长度为 16 或更长的数组，你的使用率应始终至少为 25%。这意味着在执行移除操作之前，如果数组中的元素数量达到或低于数组长度的 25%，你应该将数组缩小。对于长度为 15 或更短的数组，你的使用率可以任意低。
我们再次 不 建议在循环实现中使用
arraycopy。如果你按照我们上面的建议使用for循环来扩容，那么缩容应该看起来与扩容 非常相似 （也许可以用一个辅助方法？）。
在你编写测试并验证它们失败之后 ，实现
removeFirst和removeLast。
为了获得预期的体验，请按顺序遵循这些步骤。如果你做了其他事情并向我们寻求帮助，我们会让你回到这些步骤。
getRecursive
虽然我们在这个项目中不再使用链表，但仍然需要实现这个方法以保持与我们接口的一致性。 从技术上讲，这个方法不应该在接口中，但它在这里是为了方便测试。你可以直接使用这个代码块：
@Override
public T getRecursive(int index) {
throw new UnsupportedOperationException("否 need to implement getRecursive for proj 1b");
}
"实现"
getRecursive
。
编写测试
请参阅 项目1A规范 来复习如何编写测试。与项目1A类似，你将根据项目1B的单元测试覆盖率进行评分。你可能会发现项目1A中的一些测试可以在这个项目中重用；不要害怕把它们复制过来！
建议
- 尝试先让固定大小的数组能够正常工作。这是一个熟悉内容的好起点。
- 当你对固定大小数组的解决方案有信心后，再尝试调整大小——考虑为其编写一个辅助方法！
-
不要
修改
Deque61B接口
提交到自动评分器
当你编写并通过了本地测试后，尝试提交到自动评分器。你可能会全部通过，也可能不会。
- 如果你没有通过任何覆盖率测试，这意味着你的本地测试没有覆盖到某些情况。自动评分器的测试名称和测试覆盖率组件会给你提示，告诉你缺少哪些情况。
- 如果你没有通过正确性测试，这意味着即使你的标志覆盖率足够，你的本地测试仍然没有覆盖到某些情况。这是 正常的 。覆盖率标志只是一个近似值！它们也没有描述所有需要测试的行为，也不能保证你断言了所有内容。 这里 是它们的列表！
- 如果你没有通过任何时间测试，这意味着你的实现没有满足上述时间约束。
- 你每24小时将有4个提交令牌。 对于因未添加/提交/推送代码、未运行风格检查等原因导致的失败，我们不会恢复令牌。
-
你可能会在自动评分器的响应中看到类似这样的消息：
WARNING: A terminally deprecated method in java.lang.System has been called。你可以安全地忽略任何标记为WARNING的行。
评分标准
与项目0类似，本项目分为多个独立部分，你必须 完全正确 地实现每个部分才能获得分数。
-
添加（25%）
：正确实现
addFirst、addLast和toList。 -
是Empty、size（5%） ：在添加方法正常工作的前提下，正确实现是Empty和size。 -
get（10%） ：正确实现get。 -
删除（30%）
：正确实现
removeFirst和removeLast。 - 内存（20%） ：正确实现大小调整，确保不会使用过多内存。
此外，还有一个 测试覆盖率（10%） 部分。我们会将你的测试运行在助教的解决方案上，检查测试了多少种场景和边界情况。这一部分你可以获得部分分数。 这里 是它们的列表！