c - 为什么栈实现为链表？有什么需要，为什么数组实现不够？

Question

很多时候，stack是用链表实现的，是不是数组表示不够好，在array中我们可以很容易的push pop，而链表over array使得代码复杂化，相对于array实现没有优势。

您能否举例说明链表实现更有利，或者我们不能没有它。

Answer 1

我会说堆栈的许多实际实现都是使用数组编写的。例如，.NET Stack 实现使用数组作为后备存储。

数组通常更高效，因为您可以将所有附近的堆栈节点保存在连续内存中，这些内存可以很好地适合处理器上的快速缓存行。

我想你会看到使用链表的堆栈的教科书实现，因为它们更容易编写，并且不会强制你编写一些额外的代码来管理支持数组存储以及提出增长/复制/预留空间启发式。

此外，如果您真的迫于使用少量内存的压力，那么链表实现可能有意义，因为您不会“浪费”当前未使用的空间。然而，在具有大量内存的现代处理器上，通常最好使用数组来获得它们提供的高速缓存优势，而不是担心使用链表方法的页面错误。