ArrayDeque 操作

Question

我有一些空闲时间并试图了解 ArrayDeque 的内部工作原理。我在这里阅读了几篇文章和 questions/answers，我认为我已经很接近了。我使用调试来跟踪工作流程，但有些事情困扰着我。我创建了一个空的双端队列，它产生了一个包含 16 个空元素的数组。当我使用 addFirst 时，它在数组中的位置 16 上添加了一个元素，并在位置 0 的开头添加了 addLast 。我错过了什么，可以请您分享一些知识或为我指明正确的方向，以便我可以完全了解幕后发生的事情。 提前致谢！

Answer 1

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

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

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

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

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

每当我们执行addFirst时，我们都会将头指针后退一步，然后将元素写入我们找到的位置。由于我们假装数组的两端链接在一起，因此在此处后退一步将头指针移动到最后一个位置：

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

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

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

这是如果我们再做两个 addFirsts 的样子：

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

下面是如果我们再做两个 addLasts 会是什么样子：

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

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

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

ArrayDeque 操作

ArrayDeque operations

java

data-structures

deque

circular-buffer

arraydeque