什么是实现队列的最佳数据结构？

Question

什么是实现队列的最佳数据结构？

data-structuresqueue

3

我只需要"enque"和"dequeue"这两个操作。

- user1009285

1

那要看使用的编程语言而定。并非所有语言都具有相同的功能。您使用的是哪种语言？ - elixenide

3个回答

4

你可以使用数组（内存中连续的空间），也可以使用链表（不一定连续）。

数组及其衍生类（ArrayList、vector等）可能更复杂。它们不太高效，因为如果您开始添加太多元素，可能会用尽连续的内存空间，而且您必须将队列中的所有内容复制到一个新的内存块中。

对我来说，链表似乎相当高效，只要您跟踪前面和后面（头部和尾部，无论您想称呼什么）。

这可能会有所帮助：https://www.cs.bu.edu/teaching/c/queue/linked-list/types.html

- cdixit2

1

我不建议使用 array（或任何基于 array 实现的数据结构），因为 dequeue 操作会导致所有元素的移动。在这种情况下，我会选择 单向链表，在其中你可以在末尾插入并从开头删除，但是如果你想从末尾删除，则需要使用 双向链表，因为你需要一个指向倒数第二个节点的指针来删除最后一个节点 (dequeue)，而在单指针 链表 的情况下，这将导致扫描整个列表。

- Ouney

在数组版本中，我们只需移动HEAD指针。我们实际上不会删除和移动元素。 - Kumar Manish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4842163 · Accepted Answer

从理论上讲，一个带有头和尾的单向链表。从前面删除，添加到尾部。这样你就可以拥有理论上的O(1)常数时间复杂度（即使是最坏情况下），并且比双向链表占用更少的存储空间。

从实际角度来看，基于可增长数组的连续结构可以使用循环索引实现更好的性能。硬件在处理连续内存时表现出色，因为它具有空间局部性（适合多个相邻元素的缓存行等）。这些结构的算法复杂度较差，只有摊销常数时间和最坏情况下的线性时间复杂度（虽然这种情况非常罕见，通常不会对性能产生太大影响）。

同样从实际角度来看，展开列表可能效果很好（基本上是存储在节点中的多个元素的数组链接在一起，给你参考的局部性+保证的常数时间入队和出队）。

“最好”的选择真的很难说，因为它取决于您的需求。

例如，带有尾部的单向链表存在节点分配/释放开销和引用局部性丢失的弱点，除非您支持一个高效的连续分配器来帮助缓解这些弱点。它还需要为每个元素支付列表指针/引用的内存开销（加上可能由于每个节点的单独分配而产生的一些额外开销）。正如评论中指出的那样，链表通常并不像听起来那么好，因为它们与硬件实际性质的匹配程度不够高（至少需要通过分配器的大量帮助才能达到理想状态）。

循环数组存在一个弱点，它需要额外的容量来减少重新分配的次数（否则最坏情况下的线性时间复杂度会更频繁地发生），以及副本（尽管在某些情况下它们可以是浅拷贝）。此外，由于它只是一个大的连续内存块，如果您使用巨大的数据集，即使在拥有虚拟地址的计算机上也可能出现内存错误（在这种情况下，内存不足并不一定意味着所有内存都已经用完，而是表示未找到与请求大小匹配的未使用页面的连续集合）。

未展开的列表可以减少列表指针和节点分配开销，但会在节点中存储一些多余的容量。如果你使用一个能够在每个节点中存储64个元素的未展开的列表，并且只在队列中存储3个元素，那么这将非常浪费。