一起实现堆栈和队列的最有效方法？

Question

在单个数据结构中有效地一起实现堆栈和队列的最合适方法是什么。元素的数量是无限的。检索和插入都应该在恒定时间内发生。

Answer 1

双向链表最适合这个。列表中的每个节点都有两个引用：一个指向它之前的项目，一个指向它之后的项目。主列表对象维护对列表前面的项目和列表后面的项目的引用。

任何时候插入一个项目，列表：

1. 创建一个新节点，为其提供对列表中先前第一个或最后一个节点的引用（取决于您是添加到前面还是后面）。
2. 连接之前的第一个或最后一个节点指向新创建的节点。
3. 更新它自己对第一个或最后一个节点的引用，以指向新节点。

从列表的前面或后面删除一个项目可以有效地逆转这个过程。

插入到结构的前面或后面总是一个 O(1) 操作。

Answer 2

一个doubly linked list可以用常数时间解决这个问题：

• 通过将元素附加到 以恒定时间列出。
• 它允许pop()通过在常数时间内删除最后一个元素
• 它允许 dequeue() 通过删除第一个元素，也是在恒定时间内。

Answer 3

一个双向链表，具有您想要的所有计算复杂性属性，但缓存局部性较差。

A ring buffer (array) 允许在头部和尾部追加和移除具有相同的复杂性特征。它使用动态数组并需要重新分配，一旦元素数量超出其容量。

但是，类似于数组列表/向量，在实践中顺序访问通常比链表更快。在大多数情况下，它比使用双向链表实现更快、内存效率更高。

它是 Java 中 dequeue abstract data structure, see e.g. the ArrayDeque<E> 实现的可能实现之一。