很多时候，栈是用链表实现的，是不是数组表示不够好，在数组中我们可以很容易地进行push pop，而链表比数组更复杂代码，与数组实现相比没有优势。
您能否举一个链接列表实现更有益的示例，或者我们不能没有它。
问问题
3220 次
5 回答
2
我会说许多实际的堆栈实现都是使用数组编写的。例如，.NET Stack 实现使用数组作为后备存储。
数组通常更有效，因为您可以将堆栈节点都保留在附近的连续内存中，这可以很好地适合处理器上的快速缓存行。
我想您会看到使用链表的堆栈的教科书实现，因为它们更容易编写并且不会强迫您编写一些额外的代码来管理后备数组存储以及提出增长/复制/预留空间启发式。
此外，如果您真的需要使用很少的内存，那么链表实现可能是有意义的，因为您不会“浪费”当前未使用的空间。但是，在具有大量内存的现代处理器上，通常最好使用数组来获得它们提供的缓存优势，而不是担心链表方法的页面错误。
于 2012-08-21T14:25:40.907 回答
1
数组的大小是有限的和预定义的。当您不知道其中有多少时，链表是一个完美的选择。
更详细的比较：-（+表示支配链表，-表示数组）
Size and type constraint:-
(+) 数组的其他成员以相等的距离对齐并且需要连续的内存，而在另一边的链接列表可以提供非连续的内存解决方案，所以有时它对内存以及在大数据的情况下也有好处（避免 cpu 轮询资源）。
(+) 假设您使用数组作为堆栈，并且数组的类型为 int。现在您将如何在其中容纳双精度数？
Portability
- (+) 数组可能会导致索引超出范围异常等异常，但您可以随时在链表中增加链。
Speed and performance
- (-)如果它与性能有关，那么对于数组来说，显然大部分复杂性都在 O(1) 左右。如果是链表，您将不得不选择一个起始节点来开始跟踪，这会增加性能损失。
于 2012-08-21T14:20:48.147 回答
0
当堆栈的大小变化很大时，如果您有一个总是分配一个巨大数组的通用例程，那么您会浪费空间。
于 2012-08-21T14:18:51.520 回答
0
显然，固定大小的数组有事先知道最大大小的限制。
如果您考虑dynamic array，那么链接列表与数组涵盖了包括执行操作的复杂性在内的细节。
于 2012-08-21T14:24:57.050 回答
0
堆栈是使用链表实现的，因为 Push 和 Pop 操作的时间复杂度为 O(1)，而数组的时间复杂度为 O(n)。（除了链表中灵活的大小优势）
于 2012-12-26T22:58:34.987 回答