我正在阅读Albahari兄弟的《C# 4.0权威指南》，看到这段话：
堆栈（Stack）使用一个内部实现了动态扩容的数组，和队列（Queue）以及列表（List）一样。（第288页，第4段）
我不禁想问为什么。链表（LinkedList）提供了 O(1) 的头尾插入和删除操作（这对于堆栈或队列来说应该很好用）。可调整大小的数组在平均情况下具有 O(1) 的插入操作（如果我没记错的话），但最坏情况下是 O(n)（我不确定删除操作）。对于大型堆栈/队列，它可能会使用更多的空间。
这里是否有比这更多的考虑？双向链表实现的缺点是什么？
但最坏情况下是 O(n)。
虽然插入和删除操作的时间有长有短，但是平摊分析的整体最坏情况仍然是O(1)，这就是平摊分析的全部意义。此外，数组使用的空间也比链表少（毕竟每个元素都要存储一个额外的指针）。
此外，与链表相比，数组的开销更小。总之，在几乎所有的用例中，基于数组的实现方式都比基于链表的实现方式更加高效（事实上，队列可以通过利用以链表形式管理的页面来稍微更有效地实现 - 参见C++的`std :: deque` 实现）。
deque，而不是dequeue。 - Konrad Rudolph以下是一个大致的估算，用于描述存储100个System.Int32类型的栈所需的内存资源：
如果使用数组实现，则需要以下内容：
type designator 4 bytes
object lock 4
pointer to the array 4 (or 8)
array type designator 4
array lock 4
int array 400
stack head index 4
---
Total 424 bytes (in 2 managed heap objects)
链表的实现需要以下内容：
type designator 4 bytes
object lock 4
pointer to the last node 4 (or 8)
node type designator 4 * 100 = 400
node lock 4 * 100 = 400
int value 4 * 100 = 400
pointer to next node 4 (or 8) * 100 = 400 (or 800)
-----
Total 1,612 bytes (in 101 managed heap objects)
数组实现的主要缺点是在需要扩展时复制数组。忽略其他因素，这将是一个O(n)操作，其中n是堆栈中项的数量。除了两个因素之外，这似乎是一件非常糟糕的事情：它几乎从不发生，因为每次增量都会使扩展加倍，而数组复制操作已经高度优化并且非常快速。因此，在实践中，扩展很容易被其他堆栈操作淹没。
队列同理。