0

我有一些空闲时间并试图了解 ArrayDeque 在内部是如何工作的。我在这里阅读了几篇文章和问题/答案，我想我已经很接近了。我使用调试来遵循工作流程，有些事情让我很困扰。我创建了一个空的双端队列，它产生了一个包含 16 个为空元素的数组。当我使用addFirst时，它在数组的第 16 位添加了一个元素，并在第 0 位的开头添加了addLast。我错过了什么，请您分享一些知识或指出正确的方向，以便我可以完全理解正在发生的事情窗帘后面。提前致谢！

4

1 回答 1

1

基于数组的双端队列通常使用称为循环缓冲区的数据结构来实现。这个想法是我们维护一个元素数组，但假设数组的末端粘在一起形成一个环。

从您的调试来看，内部似乎ArrayDeque维护了一个包含 16 个元素的数组，我们可以这样查看：

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

我们维护两个不同的指针，一个头指针和一个尾指针，跟踪双端队列第一个元素的位置和双端队列最后一个元素的位置。最初，它们将指向数组的开头：

 head
  |
  v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  ^
  |
 tail

每当我们执行 anaddFirst时，我们都会将头指针备份一步，然后将元素写入我们找到的位置。由于我们假设数组的两端是链接在一起的，所以这里后退一步会将头指针移动到最后一个位置：

                                                             head
                                                              |
                                                              v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  ^
  |
 tail

要做一个addLast，我们写到尾部位置，然后向前推进：

                                                             head
                                                              |
                                                              v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      ^
      |
     tail

如果我们再做两个 s，它会是什么样子addFirst：

                                                     head
                                                      |
                                                      v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X |   |   |   |   |   |   |   |   |   |   |   |   | X | X | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      ^
      |
     tail

addLast这就是如果我们再做两个s 的样子：

                                                     head
                                                      |
                                                      v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X | X | X |   |   |   |   |   |   |   |   |   |   | X | X | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
              ^
              |
             tail

我们从头指针开始读取双端队列的元素，然后继续前进，直到到达尾指针。所以在这种情况下，我们从 指向的槽开始读取head，而不是数组中的第一个位置。

最终，两个指针将在中间相遇。发生这种情况时，我们会创建一个比原始数组大（通常大 150%）的全新数组，然后将元素复制到新数组中以释放一些空间。

于 2020-11-12T17:44:01.883 回答