随机访问队列数据结构

Question

我正在寻找用于实现随机访问队列（“直线”队列，而不是优先级队列）的数据结构。也就是说，需要标准队列操作（从后面添加，从前面删除，大小/是否为空），但有一个小变化，即我希望能够进行类似于数组的索引到队列中间位置的操作（但不是插入或删除）。 （澄清一下：我仅在队列的后面添加元素，并且仅从前面删除元素。）可以将其想象成具有可变大小的滑动窗口。

• 必须是无界的（因此固定长度循环缓冲区无法使用）
• 不需要考虑并发性
• 性能比空间要求更重要（当然在限制范围内：例如一个具有2的64次方个元素的平坦数组并不实际）
• 性能的一致性比直接性能更重要：真正的最坏情况而不是摊销情况���因此，据我所知，（大多数）基于数组的数据结构都无法胜任。

理想情况下，我正在寻找支持O(1)操作的数据结构，但至少需要具有子线性最坏情况的数据结构。

注意：我不是在寻找实现或库，而是在寻找数据结构。（这是出于个人好奇心，跟随我最近考试中提出的相关问题）

- TLW

Answer 1

使用可调整大小的数组可以实现平摊复杂度为O（1）的插入和删除操作，以及O（1）的随机访问。

---

或者，您可以使用顺序统计树来实现队列。

顺序统计树基本上是一个二叉搜索树（具体而言是自平衡树以获得高效性能），但每个节点存储一个额外的值，即该节点为根的子树的大小（即其下面的节点数）。

插入将涉及在最大位置插入值，删除将从最小位置删除。随机访问只需使用子树的大小来遍历到对应于给定索引的节点。

这将导致所有操作的O(log n)性能。

---

与上面类似，但在实现上更简单的方法是，我们可以使用标准的二叉搜索树，由递增的唯一ID进行索引 - 每个插入的值都会获得上一个插入的ID加一的ID。要进行随机访问，您只需通过给定的索引偏移树中最小的ID，并在树中查找该ID。

如果ID溢出，您可以继续使用另一个BST，并在第一个BST为空时最终将其删除 - 这样做并不理想，但它可能仍然比实现自己的树更简单（因为有序统计树在库中并不常见）。

- Bernhard Barker

---

可调整大小的数组不幸地不能满足一致的性能要求。是的，它的平摊复杂度是O(1)，但在最坏情况下是O(n)，这正是我所关注的。感谢提供有序统计树的链接，但问题在于如何以不会导致缓慢最坏情况性能的方式进行重新平衡。（在这种情况下，最坏情况是O(log n)，但仍然比最佳情况慢得多） - TLW