ArrayDeque操作

Question

我有一些空闲时间，并试图了解ArrayDeque是如何内部工作的。我在这里读过几篇文章和问题/答案，我想我已经很接近了。我用调试来遵循工作流，有些事情困扰着我。我创建了一个空的deque，结果是一个包含16个元素的数组，这些元素都是空的。当我使用addFirst时，它在数组的位置16上添加了一个元素，在位置0上添加了addLast。我错过了什么，你能不能分享一些知识或者指出正确的方向，这样我才能完全理解窗帘背后发生的事情。，提前谢谢！

Answer 1

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

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

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

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

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

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

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

要执行addLast，我们将写到尾部位置，然后向前推进：

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

如果我们再执行两个addFirst，如下所示：

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

如果我们再做两个addLast，情况会是这样的：

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

我们读取deque的元素，从头指针开始，然后继续前进，直到我们到达尾部指针。因此，在本例中，我们从head指向的槽开始读取，而不是数组中的第一个位置。

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