支持添加开始、加数和随机访问的恒定时间的数据结构
我正在寻找一种支持恒定时间性能的数据结构，用于将元素添加到开始、结束和随机访问。
我在想双端队列。双端队列是否支持随机访问的恒定时间性能？如果是的话，它是如何实现的？
我知道可以使用双链表来构建双端队列。但是如何在所有元素上建立索引以实现恒定时间随机访问呢？
感谢您的帮助。
杰瑞
I am looking for a data structure that supports constant time performance for adding an element to the beginning, end, and random access.
I am thinking double ended queue. Does double ended queue support constant time performance for random access? If so, how does it achieve it?
I know one can use double linked list to build a double ended queue. But How do you build an index on all the elements to achieve constant time random access?
Thank you for your help.
Jerry
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
根据定义，您正在寻找的是双端队列，但这只是一个抽象的数据结构。维基百科在动态数组方面讨论了双端队列的几种实现策略；使用这些，您可以获得摊销的 O(1) 前置和附加。乍一看，循环缓冲区策略似乎是最容易实现的。
What you're looking for would be a double-ended queue by definition, but that's just an abstract data structure. Wikipedia discusses several implementation strategies for deques in terms of dynamic arrays; using these, you can get amortized O(1) prepend and append. The circular buffer strategy seems the easiest to implement, at first glance.