IAm*_*aja 45 arrays queue stack linked-list data-structures
我试图比较堆栈和队列操作的增长率(运行时和空间),当实现为数组和链接列表时.到目前为止,我只能找到队列pop()的平均案例运行时间,但没有全面探索这两个数据结构并比较它们的运行时/空间行为.
具体地讲,我想找比较push()和pop()用于两个队列和堆栈,作为实现两个阵列和链表(因此2次操作×2种结构×2个实施方式中,或8个值).
另外,我会欣赏这两者的最佳,平均和最差情况值,以及与它们消耗的空间量有关的任何事情.
我能找到的最接近的是"所有cs作弊表的母亲"pdf,这显然是高级算法和离散函数的主人或博士级备忘单.
我只是在寻找一种方法来确定何时何地应该使用基于数组的实现与基于列表的堆栈和队列实现.
tem*_*def 83
有多种不同的方法来实现队列和堆栈与链表和数组,我不知道你正在寻找哪些.然而,在分析这些结构中的任何一个之前,让我们回顾一下上述数据结构的一些重要的运行时考虑因素.
在只带头指针的单链表中,前置值的成本是O(1) - 我们只需创建新元素,将其指针连接到指向列表的旧头,然后更新头指针.删除第一个元素的成本也是O(1),这是通过将头指针更新为指向当前头之后的元素,然后释放旧头的内存(如果执行显式内存管理)来完成的.然而,由于动态分配的费用,这些O(1)项中的常数因子可能很高.由于在每个元素中存储了额外的指针,链表的内存开销通常是O(n)总额外内存.
在动态数组中,我们可以在O(1)时间内访问任何元素.我们还可以在分摊的O(1)中追加一个元素,这意味着n次插入的总时间是O(n),尽管任何插入的实际时间范围可能更差.通常,动态数组是通过将大多数插入通过附加到预分配空间中来获取O(1)来实现的,但是通过将数组容量加倍并复制元素,在Θ(n)时间内进行少量插入.有些技术试图通过分配额外的空间并懒惰地复制元素来减少这种情况(例如,参见此数据结构).通常情况下,动态数组的内存使用情况非常好 - 例如,当数组完全填满时,只有O(1)额外的开销 - 虽然在数组大小加倍之后可能会有O(n)未使用数组中分配的元素.由于分配很少且访问速度很快,因此动态数组通常比链接列表更快.
现在,让我们考虑如何使用链表或动态数组实现堆栈和队列.有很多方法可以做到这一点,所以我假设您正在使用以下实现:
让我们依次考虑每一个.
由单链表支持的堆栈. 因为单链接列表支持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个元素.链表版本具有更好的最坏情况行为,但由于执行的分配数量可能会使整个运行时更差.在最坏的情况下,阵列版本较慢,但如果每个操作的时间不是太重要,则具有更好的整体性能.
您可能希望研究实现堆栈的另一个选项是VList,这是一种最新的数据结构,它是链表和动态数组的混合体.它使得分配比链表更少,并且其中的指针更少,尽管在最坏的情况下空间使用率稍高.您可能还希望查看块列表,它们是数组和链表的另一种混合,可用于堆栈和队列.
希望这可以帮助!