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

问题描述

编辑：我很乐意被标记为非家庭作业，因为我不是学生，而不是任务。我从纯粹的好奇心中提出这个问题，因为我一直在为所有的列表使用一个Java ArrayList ，最终发生在我身上，我应该知道所有的这些结构和实现。在花了一个周末阅读有关这些类型结构的所有相关（wikiepdia等）文章后，我仍然无法找到我在这篇文章中提出的问题。再次，不是家庭作业。

我试图比较堆栈和队列操作的增长率（运行时和空间），实现为数组和链接列表。到目前为止，我只能找到队列 pop（）的平均病例运行时间，但没有一个全面地探讨这两个数据结构并比较其运行时间/空间行为。

具体来说，我正在寻找比较 push（）和对于两个队列和堆栈，pop（）实现为数组和链表（因此2个操作x 2个结构x 2个实现或8个值）

此外，我会感谢这两者的最佳平均值和最差情况值，以及与他们消费的空间相关的任何内容。

我最能找到的是这个所有cs作弊书的母亲pdf，显然是高级算法和离散功能的硕士或博士级作文。

我正在寻找一种方法来确定何时和在哪里我应该使用基于数组的实现与基于列表的实现bo

解决方案

有多种不同的方式来实现具有链接列表和数组的队列和堆栈，我不知道你要找哪一个。在分析任何这些结构之前，我们来看看上述数据结构的一些重要的运行时注意事项。

在一个单头列表中，只有一个头指针，成本前面加一个值是（1） - 我们只需创建新元素，将其指针连接到指向列表的旧头，然后更新头指针。删除第一个元素的成本也是O（1），这是通过更新头指针来指向当前头之后的元素来完成的，然后释放旧头的存储器（如果执行显式存储器管理）。然而，这些O（1）项中的常数因素可能由于动态分配的费用而高。由于在每个元素中存储额外的指针，链表的内存开销通常为O（n）个额外的内存。在动态数组中，我们可以在O（1）时间内访问任何元素。我们还可以在分摊的O（1）中附加一个元素，这意味着n个插入的总时间为O（n）虽然任何插入的实际时间范围可能会更糟。通常，动态数组通过将大多数插入通过附加到预先分配的空间中而取得O（1）来实现，但是通过将阵列容量和复制元素加倍来实现少量的插入。有一些技术可以通过分配额外的空间和懒洋洋地复制元素来减少这种情况（参见这个数据结构）。通常，动态数组的内存使用情况非常好 - 当数组完全满时，例如，只有O（1）个额外的开销 - 尽管数组的大小已经翻倍了，可能有O（n）未使用在数组中分配的元素。因为分配不频繁，访问速度很快，动态数组通常比链表快。

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

• 堆栈：
  
  
  
  
  • 链接列表：作为单链表 /头部指针。
  
  
  • 数组：作为动态数组
  
  


• 队列：
  
  
  
  
  • 链接列表：作为单链列表，一个头尾指针。
  
  
  • 数组：作为一个循环缓冲区，由数组。
  
  

由单链列表支持的堆栈。由于单链表支持O（1）时间前置和删除优先，因此推送或弹出的成本链表支持的堆栈也是O（1）最坏的情况。但是，添加的每个新元素都需要新的分配，与其他操作相比，分配可能是昂贵的。

由动态数组支持的堆栈。可以通过将一个新元素附加到动态数组来实现堆栈，这个元素需要分摊O（1）个时间和最坏情况的O（n）时间。从堆栈弹出可以通过删除最坏的情况下运行的最后一个元素（如果要尝试回收未使用的空间）（或摊销O（1）），则可以实现。换句话说，最常见的实现有最好的O（1）推和弹，最坏情况O（n）推和O（1）弹出，并且分摊O（1）推和O（1）弹出。 / p>

由单链列表支持的队列。进入链接列表可以通过追加到单链列表的背面来实现，这是最差的时间O（1）。可以通过删除第一个元素来实现出队，这也是最坏的时间O（1）。这也需要每个入队的新分配，这可能很慢。

由越来越多的循环缓冲区支持的队列。排入循环缓冲区通过在循环缓冲区中的下一个空闲位置插入某些东西。这可以通过增加数组，如果需要，然后插入新的元素。对动态数组使用类似的分析，这是最佳情况时间O（1），最坏情况时间O（n）和摊销时间O（1）。通过删除循环缓冲区的第一个元素，在最坏的情况下需要时间O（1），从缓冲区中排队。

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

另一个可能需要查看的选项用于实施堆栈的是 VList ，这是一个最近的数据结构，它是一个链表和动态数组的混合。它比链表更少的分配，并且在其中具有较少的指针，尽管在最坏的情况下空间使用率要高一些。您可能还想查看chunklists，它们是数组和链表的另一个混合，可用于堆栈和队列。

希望这有帮助！ p>

Edit: I'd appreciate being tagged out-of-homework as I am not a student and this is not an assignment. I ask this question out of pure curiosity because I've always just used a Java ArrayList for all my lists and it finally occured to me that I should know the difference between all of these structures and implementations. After spending a weekend reading all the relevant (wikiepdia, etc.) articles on these types of structures, I still haven't been able to find what I'm asking in this post. Again, not homework.

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.

Another option you may want to look into for implementing stacks is the VList, a recent data structure that is a hybrid of a linked list and a dynamic array. It makes fewer allocations than a linked list and has fewer pointers in it, though the space usage is a bit higher in the worst case. You might also want to look into chunklists, which are another hybrid of arrays and linked lists, that can be used for both stacks and queues.

Hope this helps!

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