为什么Stack 和Queue 用数组实现？
我正在Albahari兄弟的Nutshell中阅读C＃4.0，我发现了这个：
堆栈在内部实现，其数组根据需要resize ，与Queue和List一样。 （第288页，第4段）
我不禁想知道为什么。 LinkedList提供O（1）头尾插入和删除（这应该适用于堆栈或队列）。 可resize的数组有O（1）缓冲插入（如果我没记错的话），但O（n）最坏的情况（我不确定删除）。 它可能比链表使用更多的空间（对于大型堆栈/队列）。
还有更多吗？ 双链表实现的缺点是什么？
但O（n）最坏的情况
摊销的最坏情况仍为O（1）。 长期和短期插入时间平均 – 这是摊销分析的整个点（并且删除相同）。
数组也比链表使用更少的空间（毕竟必须为每个元素存储一个额外的指针）。
此外，开销远远低于链表。 总而言之，基于数组的实现对于几乎所有用例来说都是（非常）更高效，即使偶尔访问需要更长时间（事实上，通过采取一些队列可以更有效地实现页面本身在链表中管理的优点 – 请参阅C ++’ std::deque实现）。
这是对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是堆栈中的项目数。 这似乎是一个非常糟糕的事情，除了两个因素：它几乎不会发生，因为扩展在每个增量加倍，并且arrays复制操作高度优化并且速度惊人。 因此，实际上，扩展很容易被其他堆栈操作淹没。
同样对于队列。
这是因为.NET被设计为在现代处理器上运行。 哪个比内存总线快得多。 处理器的运行速度约为2千兆赫兹。 机器中的RAM时钟通常为几百兆赫兹。 从RAM读取一个字节需要超过一百个时钟周期。
这使得CPU缓存在现代处理器上非常重要，大量的芯片空间被烧毁，使缓存尽可能大。 典型的今天是L1缓存64 KB，最快的内存和非常接近处理器核心的物理位置，L2缓存256 KB，更慢和更远离核心，L3缓存大约8 MB，更慢和更远离开，由芯片上的所有核心共享。
要使缓存有效，按顺序访问内存非常重要。 如果需要L3或RAM存储器访问，读取第一个字节可能非常昂贵，接下来的63个字节非常便宜。 “高速缓存行”的大小，即内存总线的数据传输单位。
这使得数组成为迄今为止最有效的数据结构，其元素按顺序存储在内存中。 到目前为止，链表是最糟糕的数据结构，其元素通过内存自然分散，可能会导致每个元素的非常昂贵的缓存未命中。
因此，除LinkedList <>之外的所有.NET集合都在内部实现为数组。 请注意，Stack <>已经自然地实现为数组，因为您只能从数组的末尾推送和弹出元素。 O（1）操作。 调整数组大小是分摊O（logN）。