我正在寻找用于实现随机访问队列(“直线”队列,而不是优先级队列)的数据结构。也就是说,需要标准队列操作(从后面添加,从前面删除,大小/是否为空),但有一个小变化,即我希望能够进行类似于数组的索引到队列中间位置的操作(但不是插入或删除)。 (澄清一下:我仅在队列的后面添加元素,并且仅从前面删除元素。)可以将其想象成具有可变大小的滑动窗口。
注意:我不是在寻找实现或库,而是在寻找数据结构。(这是出于个人好奇心,跟随我最近考试中提出的相关问题)
- 必须是无界的(因此固定长度循环缓冲区无法使用)
- 不需要考虑并发性
- 性能比空间要求更重要(当然在限制范围内:例如一个具有2的64次方个元素的平坦数组并不实际)
- 性能的一致性比直接性能更重要:真正的最坏情况而不是摊销情况���因此,据我所知,(大多数)基于数组的数据结构都无法胜任。
O(1)
操作的数据结构,但至少需要具有子线性最坏情况的数据结构。注意:我不是在寻找实现或库,而是在寻找数据结构。(这是出于个人好奇心,跟随我最近考试中提出的相关问题)
O(1)
,但在最坏情况下是O(n)
,这正是我所关注的。感谢提供有序统计树的链接,但问题在于如何以不会导致缓慢最坏情况性能的方式进行重新平衡。(在这种情况下,最坏情况是O(log n)
,但仍然比最佳情况慢得多) - TLW