在单个数据结构中有效地一起实现堆栈和队列的最合适方法是什么。元素的数量是无限的。检索和插入都应该在恒定时间内发生。
最佳答案
双向链表，具有您想要的所有计算复杂性属性，但缓存局部性较差。
A ring buffer (array) 允许在头部和尾部添加和删除具有相同的复杂性特征。它使用动态数组并需要重新分配，一旦元素数量超出其容量。
但是，类似于数组列表/向量，在实践中顺序访问通常比链表更快。在大多数情况下，它比使用双向链表实现更快、内存效率更高。
它是 dequeue 的可能实现之一。抽象数据结构，参见例如 ArrayDeque<E> 在 Java 中实现。
关于algorithm - 一起实现堆栈和队列的最有效方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29992000/