data-structures - 支持 addbegin、addend 和随机访问的恒定时间的数据结构

Question

我正在寻找一种支持恒定时间性能的数据结构，以便在开始、结束和随机访问中添加元素。

我在想双端队列。双端队列是否支持随机访问的恒定时间性能？如果是这样，它是如何实现的？

我知道可以使用双链表来构建双端队列。但是如何在所有元素上建立索引以实现恒定时间随机访问？

感谢您的帮助。

杰瑞

Answer 1

根据定义，您正在寻找的是双端队列，但这只是一个抽象的数据结构。维基百科讨论 several implementation strategies for deques在动态数组方面；使用这些，您可以获得摊销 O(1) 前置和附加。乍一看，循环缓冲区策略似乎最容易实现。