arrays - 基于数组与基于列表的堆栈和队列

Question

当实现为数组和链表时，我试图比较堆栈和队列操作的增长率(运行时间和空间)。到目前为止，我只能找到队列 pop() 的平均情况运行时间。 s，但没有全面探索这两种数据结构并比较它们的运行时间/空间行为。

具体来说，我想比较 push()和 pop()对于队列和堆栈，实现为 两者 数组和链表(因此 2 个操作 x 2 个结构 x 2 个实现，或 8 个值)。

此外，我很欣赏这两种情况的最佳、平均和最坏情况值，以及与它们消耗的空间量有关的任何内容。

我能找到的最接近的东西是这个“所有 cs 备忘单之母”pdf，它显然是高级算法和离散函数的硕士或博士级备忘单。

我只是在寻找一种方法来确定我应该在何时何地对堆栈和队列使用基于数组的实现与基于列表的实现。

Answer 1

有多种不同的方法可以使用链表和数组来实现队列和堆栈，我不确定您要寻找哪种方法。不过，在分析任何这些结构之前，让我们回顾一下上述数据结构的一些重要的运行时注意事项。

在只有一个头指针的单链表中，添加一个值的成本是 O(1) - 我们只需创建新元素，将其指针连接到指向列表的旧头，然后更新头指针。删除第一个元素的成本也是 O(1)，这是通过更新头指针指向当前头之后的元素，然后为旧头释放内存(如果执行显式内存管理)来完成的。然而，由于动态分配的开销，这些 O(1) 项中的常数因子可能很高。由于在每个元素中存储了一个额外的指针，链表的内存开销通常为 O(n) 总额外内存。

在动态数组中，我们可以在 O(1) 时间内访问任何元素。我们也可以在 amortized O(1) 中附加一个元素，这意味着 n 次插入的总时间是 O(n)，尽管任何插入的实际时间界限可能更糟。通常，动态数组是通过将大多数插入添加到预分配空间中花费 O(1) 来实现的，但通过将数组容量加倍并复制元素，在 Θ(n) 时间内运行少量插入。有一些技术可以通过分配额外空间和延迟复制元素来尝试减少这种情况(例如，请参见 this data structure )。通常，动态数组的内存使用情况非常好——例如，当数组完全满时，只有 O(1) 额外开销——尽管在数组大小增加一倍之后，可能有 O(n) 未使用数组中分配的元素。由于分配不频繁且访问速度快，因此动态数组通常比链表快。

现在，让我们考虑如何使用链表或动态数组来实现堆栈和队列。有很多方法可以做到这一点，所以我假设您正在使用以下实现:

堆:

链表:作为singly-linked list带有头指针。

数组:作为 dynamic array

队列:

链表:作为带有头尾指针的单向链表。

数组:作为 circular buffer由数组支持。

让我们依次考虑每一个。

由单链表支持的堆栈。 因为单链表支持 O(1) 时间前置和删除优先，插入或弹出链表支持的堆栈的成本也是 O(1) 最坏情况。但是，添加的每个新元素都需要新的分配，并且与其他操作相比，分配的成本可能很高。

由动态数组支持的堆栈。 压入堆栈可以通过向动态数组添加一个新元素来实现，这需要分摊 O(1) 时间和最坏情况 O(n) 时间。从堆栈中弹出可以通过删除最后一个元素来实现，该元素在最坏情况下运行为 O(1)(如果您想尝试回收未使用的空间，则为分摊 O(1))。换句话说，最常见的实现有最佳情况 O(1) 推送和弹出，最坏情况 O(n) 推送和 O(1) 弹出，以及分摊 O(1) 推送和 O(1) 弹出。

由单链表支持的队列。 加入链表可以通过追加到单链表的后面来实现，这需要最坏情况时间 O(1)。出队可以通过移除第一个元素来实现，这也需要最坏情况时间 O(1)。这也需要每个入队的新分配，这可能很慢。

队列由不断增长的循环缓冲区支持。 进入循环缓冲区的工作原理是在循环缓冲区的下一个空闲位置插入一些东西。这通过在必要时增加数组，然后插入新元素来工作。对动态数组使用类似的分析，这需要最佳情况时间 O(1)、最坏情况时间 O(n) 和摊销时间 O(1)。从缓冲区出队的工作原理是删除循环缓冲区的第一个元素，在最坏的情况下需要时间 O(1)。

总而言之，所有结构都支持在 O(n) 时间内推送和弹出 n 个元素。链表版本具有更好的最坏情况行为，但由于执行的分配数量可能具有更差的整体运行时间。在最坏的情况下，阵列版本较慢，但如果每个操作的时间不太重要，则具有更好的整体性能。

这些并不是实现列表的唯一方法。你可以有一个 unrolled linked list ，其中每个链表单元格都包含多个值。这会略微增加查找的引用位置并减少使用的分配数量。其他选项(例如，使用以索引为键的平衡树)代表一组不同的权衡。

希望这可以帮助!