Project 1B ArrayDeque61B

截止日期：2月12日，星期一，太平洋时间晚上11:59

常见问题解答

每个作业的顶部都有常见问题解答的链接。您也可以通过在 URL 末尾添加“/faq”来访问它。项目 1B 的常见问题解答位于此处。

请注意，此项目有提交令牌限制。请参阅提交到自动评分器了解更多详细信息。

介绍

在项目 1A 中，我们构建了 LinkedListDeque61B。现在我们将看到 Deque61B 接口的不同实现，该实现使用底层数组，而不是链接节点。

在项目 1B 结束时，您将...

• 了解数据结构中底层数组的实现。
• 在通过测试和测试驱动开发验证数据结构正确性方面获得更多经验。

info

查看 Project 1B 幻灯片，获取更多直观的提示。

info

查看 入门视频，了解规范概览。

我们将提供相对较少的脚手架。换句话说，我们会告诉你做什么，但不会告诉你怎么做。

info

本节假设您已经观看并完全理解了直到 ArrayList 讲座（第 7 讲）的讲座。

对于此项目，您必须单独工作！请仔细阅读[合作与作弊政策]，以了解其具体含义。特别是，不要在网上寻找解决方案。

danger

请勿在实现中使用任何内置的 java.util 数据结构。重点在于构建您自己的版本！在测试之外，您可以在少数地方使用特定的数据结构，我们会清楚地说明在哪里。

风格

与项目 1A 一样，我们将严格执行代码风格。您必须遵循风格指南，否则您将在自动评分器上受到处罚。

您可以使用 CS 61B 插件在本地检查您的风格。未检查代码风格将不会成为免除速度限制的理由。

获取骨架文件

按照作业工作流程指南中的说明获取骨架代码并在 IntelliJ 中打开它。对于此项目，我们将在 proj1b 目录中工作。

您将在您的代码仓库中看到一个名为 proj1b 的目录，其结构如下：

 proj1b
├── src
│   └── Deque61B.java
└── tests
    └── ArrayDeque61BTest.java

如果您遇到任何错误，请立即停止，仔细阅读git WTFs尝试自行解决，或在OH或Ed寻求帮助。相比于使用git命令盲目猜测和尝试，这能帮你省去很多麻烦。如果您发现自己尝试使用 Google 推荐的命令（如 force push），请不要这样做。即使您在 Stack Overflow 上找到的帖子建议这样做，也不要使用 force push！

您还可以观看Hug教授的演示了解如何入门，以及观看此视频解决遇到的git问题。

Deque: ADT 和 API

如果您需要复习 Deque61B，请参阅 Project 1A 规范 和 Deque61B.java 文件。

创建文件

首先创建一个名为 ArrayDeque61B 的文件。该文件应在 proj1b/src 目录中创建。为此，请右键单击 src 目录，导航到“New -> Java Class”，然后将其命名为 ArrayDeque61B。

和Project 1A一样，我们希望ArrayDeque61B能存储不同类型的数据。为此，请将类声明修改为如下所示：

public class ArrayDeque61B<T>

回顾课程内容，使用T或其他字符串（例如ArrayDeque61B<Glerp>）实际上没有区别。但是，我们建议使用 <T> 以便与其他 Java 代码保持一致。

我们还想告诉 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

作为第二个deque的实现，您将构建ArrayDeque61B类。这个 deque 必须使用 Java 数组作为后备数据结构。

如果需要，您可以在ArrayDeque61B.java中添加任何私有辅助类或方法。

构造函数

你需要以某种方式追踪数组索引来记录双端队列的队首和队尾元素的位置。我们强烈建议你将数组实现为循环数组。换句话说，如果你的队首元素位于位置 0，并且你执行 addFirst 操作，那么新的队首元素应该循环回到数组的末尾（因此双端队列中的新队首元素将是底层数组中的最后一个元素）。相比于非循环实现，这样做可以大大减少遇到的问题。

info

有关更多详细信息，请参见 Project 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

你可以通过将以下 import 语句添加到文件顶部来使用 floorMod(int a, int b) 方法：import java.lang.Math;。

danger

由于超出本课程范围的原因，你无法在 Java 中创建泛型数组（例如 new T[1000]）。 你需要使用语法 (T[]) new Object[1000]。

声明必要的实例变量，并实现构造函数。

你的后备数组的起始大小必须为 8。

addFirst 和 addLast

和之前一样，实现 addFirst 和 addLast。 这两个方法不得使用循环或递归。 单个添加操作必须花费“恒定时间”，也就是说，无论双端队列有多大，添加元素都应该花费大致相同的时间（有一个例外）。 这意味着你不能使用循环来迭代双端队列的所有/大多数元素。

扩容

danger

我们建议你先完成其他方法，并在不涉及调整大小的情况下验证其正确性，之后再考虑调整大小。

“恒定时间”要求的例外情况是当数组已满，并且你需要“调整大小”以有足够的空间来添加元素时。 在这种情况下，你可以花费“线性时间”来调整数组大小，然后再添加元素。

正确调整数组大小颇具挑战，需要仔细思考。 尝试手动绘制各种实现方案。 你可能需要花费相当长的时间才能提出正确的方法，我们鼓励你与你的同学或助教讨论这些大方向上的想法。 请确保实际代码完全由你独立完成。

确保以几何比例进行扩容。

danger

我们不建议在循环实现中使用 arraycopy。 这样做虽然可行，但会导致实现变得更加复杂，而且调试难度也会大大增加！

相反，我们建议您提前考虑 get 方法的实现，并尝试使用 for 循环来解决问题。

实现 addFirst 和 addLast，并编写测试来验证其正确性。 确保添加足够的元素，以触发后备数组的自动扩容！ 有关调整大小的更多信息，请查看这些幻灯片。

get

与 LinkedListDeque61B 不同，此方法的时间复杂度必须是常量级别。

与之前一样，当索引无效（超出范围或为负数）时，get 方法应返回 null。 在这种情况下，请忽略 Deque61B.java 文件中框架代码的注释。

在您编写测试并验证它们失败后，实现 get。

isEmpty 和 size

这两种方法的时间复杂度必须是常量级别。 也就是说，方法的执行时间不应随 deque 中元素数量的增加而增加。

为 isEmpty 和 size 方法编写测试用例，并检查它们是否失败。 然后，实现这些方法。

toList

toList 方法仍然可以用于测试您的 Deque61B 实现。

编写 toList 方法。 该方法的第一行应该类似于 List<T> returnList = new ArrayList<>(); 这样的语句。 这是允许您使用 Java 数据结构的一个地方。

danger

如果使用了 toList 方法，后续某些方法的实现可能会变得过于简单。 您不得在 ArrayDeque61B 内部调用 toList； 有一项测试会检查这一点。

info

提示 其他方法中的某一个可能对实现此方法有所帮助。

实现 toList。 这次没有给您测试用例，因此您需要自己编写测试用例！

接下来需要做的是测试并实现剩余的所有方法。 对于本项目的其余部分，我们将从高层次描述我们建议的步骤。 我们强烈建议您按照给定的顺序执行剩余的步骤。 请务必在实现方法功能之前编写相应的测试用例。 这称为“测试驱动开发”，有助于确保您在执行方法之前知道它们应该做什么。

removeFirst 和 removeLast

最后，编写一些测试来测试 removeFirst 和 removeLast 的行为，并再次确保测试失败。

不要保留对 deque 中已移除元素的引用。

removeFirst 和 removeLast 不得使用循环或递归。 与 addFirst 和 addLast 方法类似，这些操作的时间复杂度也必须是“常量级别”。 有关这意味着什么的更多信息，请参阅有关编写 addFirst 和 addLast 的部分。

缩小尺寸

程序在任何时候占用的内存空间应该和存储的数据量成正比。例如，如果你向双端队列添加 10,000 个元素，然后删除 9,999 个元素，那么你不应该仍然使用一个可以容纳 10,000 个元素的数组。对于长度为 16 或更大的数组，内存利用率应始终至少为 25%。这意味着在执行删除操作之前，如果数组中的元素数量小于等于数组长度的 25%，则应缩小数组。对于长度为 15 或更小的数组，内存利用率可以任意低。

danger

我们再次不建议将 arraycopy 与循环实现一起使用。如果你按照我们上面的建议使用 for 循环来增大数组容量，那么缩小数组容量的操作应该和增大数组容量的操作非常相似，可以考虑使用辅助方法来实现。

在您编写测试并验证它们失败后，实现 removeFirst 和 removeLast。

danger

为了达到最佳学习效果，请按照步骤顺序完成。

getRecursive

虽然我们在这个项目中不再使用链表，但仍然需要实现此方法以与我们的接口保持一致。严格来说，这个方法不应该出现在接口里，但为了方便测试，我们保留了它。你可以直接使用此代码块：

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

实现 getRecursive 方法。

编写测试

关于测试的编写方法，请参考 Project 1A spec。与 Project 1A 类似，Project 1B会根据你的单元测试覆盖率进行评分。你可能会发现 Project 1A 中的一些测试可以在本项目中重复使用；欢迎复用！

建议

• 首先尝试实现固定大小数组的所有功能，这将帮助你更好地理解相关概念。
• 在确保固定大小数组功能正常后，再尝试实现动态调整大小的功能，可以考虑使用辅助方法。
• 不要修改 Deque61B 接口

提交到自动评分器

完成本地测试并通过后，提交到自动评测机进行测试，结果可能会有所不同。

• 如果您在任何覆盖率测试中失败，则说明您的本地测试存在未覆盖的情况。
• 自动评分器的测试名称和测试覆盖率信息会提示您缺失的测试用例。
• 即使覆盖率标志显示足够，如果您在正确性测试中失败，也说明您的本地测试仍然存在未覆盖的情况。这是属于正常现象。覆盖率标志只是一个近似的参考！它们既不能涵盖所有需要测试的行为，也不能保证您对所有情况都进行了断言。此处 是它们的列表！
• 如果您在任何时间测试中失败，这意味着您的实现不符合上述时间限制。
• 您每24小时有4个令牌的使用限制。如果您因为忘记添加/提交/推送代码、或未通过代码风格检查等原因而耗尽令牌，我们将不会恢复。
• 您可以安全地忽略任何标记为 WARNING 的行。

评分

这个项目与项目 0 类似，分为各个组件，您必须完全正确地实现每个组件才能获得学分。

1. 添加 (25%)：正确实现 addFirst、addLast 和 toList。
2. isEmpty、size (5%)：在addFirst、addLast 方法正确实现的前提下，正确实现 isEmpty 和 size。
3. get (10%)：正确实现 get。
4. 移除 (30%)：正确实现 removeFirst 和 removeLast。
5. 内存 (20%)：正确实现调整大小，以便您不会使用过多的内存。

此外，还有一个测试覆盖率 (10%) 组件。我们将针对工作人员的解决方案运行您的测试，并检查测试了多少场景和边缘情况。您可以获得此组件的部分学分。此处 是它们的列表！