基于数组与基于列表的堆栈和队列 [英] Array-Based vs List-Based Stacks and Queues

问题描述

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

具体来说，我希望比较队列和堆栈的 push() 和 pop()，实现为 both 数组和链表(因此 2 个操作 x 2 个结构 x 2 个实现，或 8 个值).

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

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

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

解决方案

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

在只有一个头指针的单向链表中，添加一个值的成本是 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 个元素.链表版本具有更好的最坏情况行为，但由于执行的分配数量可能具有更差的整体运行时间.数组版本在最坏的情况下速度较慢，但​​如果每个操作的时间不太重要，则具有更好的整体性能.

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

希望这有帮助！

I'm trying to compare the growth rates (both run-time and space) for stack and queue operations when implemented as both arrays and as linked lists. So far I've only been able to find average case run-times for queue pop()s, but nothing that comprehensively explores these two data structures and compares their run-times/space behaviors.

Specifically, I'm looking to compare push() and pop() for both queues and stacks, implemented as both arrays and linked lists (thus 2 operations x 2 structures x 2 implementations, or 8 values).

Additionally, I'd appreciate best, average and worst case values for both of these, and anything relating to the amount of space they consume.

The closest thing I've been able to find is this "mother of all cs cheat sheets" pdf that is clearly a masters- or doctoral-level cheat sheet of advanced algorithms and discrete functions.

I'm just looking for a way to determine when and where I should use an array-based implementation vs. a list-based implementation for both stacks and queues.

解决方案

There are multiple different ways to implement queues and stacks with linked lists and arrays, and I'm not sure which ones you're looking for. Before analyzing any of these structures, though, let's review some important runtime considerations for the above data structures.

In a singly-linked list with just a head pointer, the cost to prepend a value is O(1) - we simply create the new element, wire its pointer to point to the old head of the list, then update the head pointer. The cost to delete the first element is also O(1), which is done by updating the head pointer to point to the element after the current head, then freeing the memory for the old head (if explicit memory management is performed). However, the constant factors in these O(1) terms may be high due to the expense of dynamic allocations. The memory overhead of the linked list is usually O(n) total extra memory due to the storage of an extra pointer in each element.

In a dynamic array, we can access any element in O(1) time. We can also append an element in amortized O(1), meaning that the total time for n insertions is O(n), though the actual time bounds on any insertion may be much worse. Typically, dynamic arrays are implemented by having most insertions take O(1) by appending into preallocated space, but having a small number of insertions run in Θ(n) time by doubling the array capacity and copying elements over. There are techniques to try to reduce this by allocating extra space and lazily copying the elements over (see this data structure, for example). Typically, the memory usage of a dynamic array is quite good - when the array is completely full, for example, there is only O(1) extra overhead - though right after the array has doubled in size there may be O(n) unused elements allocated in the array. Because allocations are infrequent and accesses are fast, dynamic arrays are usually faster than linked lists.

Now, let's think about how to implement a stack and a queue using a linked list or dynamic array. There are many ways to do this, so I will assume that you are using the following implementations:

• Stack:
  • Linked list: As a singly-linked list with a head pointer.
  • Array: As a dynamic array
• Queue:
  • Linked list: As a singly-linked list with a head and tail pointer.
  • Array: As a circular buffer backed by an array.

Let's consider each in turn.

Stack backed by a singly-linked list. Because a singly-linked list supports O(1) time prepend and delete-first, the cost to push or pop into a linked-list-backed stack is also O(1) worst-case. However, each new element added requires a new allocation, and allocations can be expensive compared to other operations.

Stack backed by a dynamic array. Pushing onto the stack can be implemented by appending a new element to the dynamic array, which takes amortized O(1) time and worst-case O(n) time. Popping from the stack can be implemented by just removing the last element, which runs in worst-case O(1) (or amortized O(1) if you want to try to reclaim unused space). In other words, the most common implementation has best-case O(1) push and pop, worst-case O(n) push and O(1) pop, and amortized O(1) push and O(1) pop.

Queue backed by a singly-linked list. Enqueuing into the linked list can be implemented by appending to the back of the singly-linked list, which takes worst-case time O(1). Dequeuing can be implemented by removing the first element, which also takes worst-case time O(1). This also requires a new allocation per enqueue, which may be slow.

Queue backed by a growing circular buffer. Enqueuing into the circular buffer works by inserting something at the next free position in the circular buffer. This works by growing the array if necessary, then inserting the new element. Using a similar analysis for the dynamic array, this takes best-case time O(1), worst-case time O(n), and amortized time O(1). Dequeuing from the buffer works by removing the first element of the circular buffer, which takes time O(1) in the worst case.

To summarize, all of the structures support pushing and popping n elements in O(n) time. The linked list versions have better worst-case behavior, but may have a worse overall runtime because of the number of allocations performed. The array versions are slower in the worst-case, but have better overall performance if the time per operation isn't too important.

These aren't the only ways you can implement lists. You could have an unrolled linked list, where each linked list cell holds multiple values. This slightly increases the locality of reference of the lookups and decreases the number of allocations used. Other options (using a balanced tree keyed by index, for example) represent a different set of tradeoffs.

Hope this helps!

这篇关于基于数组与基于列表的堆栈和队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！