Cas*_*ton 29 performance stack linked-list dynamic-arrays data-structures
我开始在学校最后一年开始之前检查数据结构和算法,以确保我掌握一切.一个评论问题说"使用链表或动态数组实现堆栈并解释为什么你做出了最好的选择".
对我来说,使用带有尾指针的列表来实现堆栈似乎更直观,因为它可能需要经常调整大小.对于大量数据来说,列表是更好的选择,因为动态数组重新调整大小是一项昂贵的操作.此外,使用列表,您不需要分配比实际需要更多的空间,因此它更节省空间.
但是,动态数组肯定允许更快地添加数据(除非需要调整大小).但是,我不确定使用数组是否整体更快,或者只是不需要调整大小.
该书的解决方案说"存储非常大的对象,列表是一个更好的实现",但我不明白为什么.
哪种方式最好？应该使用哪些因素来确定哪种实施方式"最佳"？还有,我的逻辑是什么？
tem*_*def 30
这里涉及许多权衡,我不认为这个问题有"正确"的答案.
如果使用带尾指针的链表实现堆栈,则推送,弹出或查看的最坏情况运行时为O(1).但是,每个元素都会有一些额外的开销(即指针),这意味着结构总是有O(n)开销.此外,根据内存分配器的速度,为堆栈分配新节点的成本可能会很明显.此外,如果您不断地从堆栈中弹出所有元素,则可能会从较差的位置获得性能损失,因为无法保证链接列表单元格将连续存储在内存中.
如果使用动态数组实现堆栈,则推送或弹出的分摊运行时为O(1),最坏情况下的查看成本为O(1).这意味着如果您关心堆栈中任何单个操作的成本,这可能不是最好的方法.也就是说,分配很少,因此添加或删除n个元素的总成本可能比基于链表的方法中的相应成本更快.此外,此方法的内存开销通常优于链表的内存开销.如果动态数组只存储指向元素的指针,那么最坏情况下的内存开销会在填充一半元素时发生,在这种情况下会有n个额外的指针(与使用链接时的情况相同)在动态数组已满的最佳情况下,没有空单元格,额外开销为O(1).另一方面,如果动态数组直接包含元素,那么在最坏的情况下,内存开销会更糟.最后,因为元素是连续存储的,所以如果你想连续推送或弹出堆栈中的元素,那么就有更好的局部性,因为所有元素在内存中都是紧挨着的.
简而言之:
这些结构都不比其他结构明显"好".这真的取决于你的用例.找出哪个更快的最佳方法是将两者都计时,看看哪个表现更好.
希望这可以帮助!
好吧，对于小对象与大对象的问题，如果堆栈上有小对象，请考虑为链接列表使用多少额外空间。然后考虑一下，如果堆栈上有一堆大型对象，则需要多少额外空间。
接下来，考虑相同的问题，但采用基于动态数组的实现。