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

问题描述

修改：我最好的AP preciate被标记为我外的功课不是学生，这是不是一项任务。我问这个问题了纯粹的好奇，因为我一直只是用一个Java 的ArrayList 我所有的列表和它终于发生，我认为我应该知道所有的区别这些结构和实现。在这些类型的结构度过一个周末阅读所有相关（wikiepdia等）的文章后，我还一直没能找到什么，我问在这个岗位。再次，不做作业。

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.

我试图当作为两个阵列和链表实现为比较的生长率栈和队列操作（包括运行时间和空间）。到目前为止，我只能够找到的情况下平均运行时间为队列 POP（） S，但没有什么COM prehensively探讨这两个数据结构和比较其运行时间/空间的行为。

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.

具体来说，我正在寻找比较推（）和 POP（）为队列，栈，为两个阵列来实现和链表（因此操作2×2结构×2的实现，或8个值）。

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).

此外，我AP preciate最好的，平均和最差值这两个，和任何与空间所消耗的数量。

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

我已经能够找到最接近的是这个pdf字样的CS小抄之母，这显然是先进的算法和离散函数的masters-或博士学位授权一级小抄。

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.

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

推荐答案

有执行队列多个不同的方式和链表和数组堆栈，我不知道你要找哪一个。之前分析这些结构的，不过，让我们来回顾一些重要的考虑运行时对上述数据结构。

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.

在只有一个头指针单链表，成本prePEND一个值是O（1） - 我们简单地创建新元素，线材的指针指向列表的老脸，然后更新头指针。删除第一元件成本也是O（1），它是通过更新头指针当前磁头后指向元素，然后释放为旧头的存储器（如果进行明确的存储器管理）来完成。然而，在这些澳恒定因素（1）而言可能是高，由于动态分配的费用。链表的存储器开销，通常是O（n）的总额外存储器由于在各元件的额外的指针的存储

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.

在动态数组，我们可以访问在O（1）时间的任何元件。我们也可以附加在摊销O（1）的一个元素，这意味着总时间对于n插入为O（n），但在任何插入的实际时间范围可能会更糟糕。由阵列容量和复制的元素超过一倍（n）的时间，通常情况下，动态数组是由具有最插入（1）通过追加到preallocated空间取0，但有一小部分插入的运行与西塔实施。有技术，试图通过分配额外的空间，懒洋洋地复制了（参见<一个元素，以减少这种href=\"http://stackoverflow.com/questions/4834490/what-would-be-an-ideal-data-structure-for-an-add-only-no-removals-collection\">this数据结构时，例如）。通常情况下，一个动态数组的内存使用量是相当不错的 - 当阵列完全充满，例如，只有O（1）额外的开销 - 尽管数组的大小增加了一倍之后可能会有O（n）的未使用阵列中的分配元件。由于分配是很少的，访问速度快，动态数组通常比链表更快。

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
    
    
    • 链表：由于有头和尾指针单链表
    
    
    • 数组：作为循环缓冲器通过数组支持
    
    
    • 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.

    堆栈由单链表的支持。由于单链表支持O（1）时间prePEND和删除，一是成本推动或弹出成linked-列表支持堆栈也O（1）的最坏情况。然而，每一个新的元件增加需要一个新的分配，以及相对于其他操作的分配可以是昂贵的

    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.

    堆栈通过动态数组支持。推入堆栈可以通过附加一个新元素的动态数组，这需要摊销O（1）时间，最坏情况为O（n）来实现时间。从堆栈中弹出可以通过只删除最后一个元素，它运行在最坏的情况Ø实现（1）（或摊销O（1）如果你想尝试回收未使用的空间）。换句话说，最常见的实现具有最好的情况O（1）push和pop，最坏情况O（n）的推动和O（1）流行音乐和摊销O（1）推动和O（1）流行。

    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.

    <强>队列由单链接列表支持。进行排队进入链表可以被附加到单链表的背面，这需要最坏情况实现时间为O（1）。出列可通过移除第一元件，这也需要最坏情况下的时间为O（1）来实现。这也要求每排队新的分​​配，这可能会很慢。

    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.

    队列被越来越循环缓冲区的支持。将进行排队循环缓冲区通过在循环缓冲区的下一个空闲位置插入一些工作。该作品以在必要时生长数组，然后插入新的元素。使用类似的分析动态数组，这需要最好的情况时间O（1），最坏情况下的时间为O（n），本金和已摊销时间O（1）。从缓冲器出列通过移除圆形缓冲器的第一个元素，这需要在最坏情况下的时间为O（1）的工作原理。

    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.

    要总结一下，所有的结构，支持和推进在O（n）时间弹出n个元素。链表版本具有更好最坏情况下的行为，但可有因进行分配的数目的恶化整体运行。阵列版本中的最坏情况下的速度较慢，但​​具有更好的整体性能，如果每个操作的时间是不是太重要。

    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.

    您可能要考虑实施栈另一个选择是 VLIST ，最近的数据结构，它是一个链表和一个动态阵列的杂交。它使得比链表分配较少，并具有在其更少的指针，尽管该空间的用法是在最坏的情况下更高些。您可能还需要寻找到chunklists，这是阵列的另一个混合动力和链表，可同时用于堆栈和队列。

    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.

    希望这有助于！

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