为什么 Stack<T>和队列<T>用数组实现? [英] Why are Stack<T> and Queue<T> implemented with an array?

问题描述

我正在阅读 Albahari 兄弟的 C# 4.0 in a Nutshell，我发现了这个:

I'm reading C# 4.0 in a Nutshell by the Albahari brothers and I came across this:

堆栈是通过根据需要调整大小的数组在内部实现的，与队列和列表一样.(第 288 页，第 4 段)

Stacks are implemented internally with an array that's resized as required, as with Queue and List. (pg 288, paragraph 4)

我不禁想知道为什么.LinkedList 提供 O(1) 头尾插入和删除(这应该适用于堆栈或队列).可调整大小的数组具有 O(1) 分期插入(如果我没记错的话)，但 O(n) 最坏情况(我不确定删除).而且它可能比链表使用更多的空间(对于大型堆栈/队列).

I can't help but wonder why. LinkedList provides O(1) head and tail inserts and deletes (which should work well for a stack or queue). A resizable array has O(1) amortized insert (if I remember right), but O(n) worst case (I'm not sure about delete). And it probably uses more space than the linked list (for large stacks/queues).

还有比这更多的吗?双向链表实现的缺点是什么?

Is there more to it than that? What is the downside to a doubly linked list implementation?

推荐答案

但 O(n) 最坏情况

but O(n) worst case

摊销的最坏情况仍然是 O(1).插入时间的长短均化——这就是摊销分析的重点(删除也是如此).

The amortized worst case is still O(1). Long and short insertion times average out – that’s the whole point of amortised analysis (and the same for deletion).

数组也比链表使用更少空间(毕竟链表必须为每个元素存储一个额外的指针).

An array also uses less space than a linked list (which after all has to store an additional pointer for each element).

此外，开销比使用链表要少得多.总而言之，对于几乎所有用例来说，基于数组的实现(非常)效率更高，即使偶尔访问会花费更长的时间(实际上，队列可以通过以下方式更有效地实现)页面本身在链表中管理的优势 - 请参阅 C++ 的 std::deque 实现).

Furthermore, the overhead is just much less than with a linked list. All in all, an array-based implementation is just (much) more efficient for almost all use-cases, even though once in a while an access will take a little longer (in fact, a queue can be implemented slightly more efficiently by taking advantage of pages that are themselves managed in a linked list – see C++’ std::deque implementation).

这篇关于为什么 Stack<T>和队列<T>用数组实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！