Many times, stack is implemented as a linked list, Is array representation not good enough, in array we can perform push pop easily, and linked list over array complicates the code, and has no advantage over array implementation.
很多时候，栈被实现为一个链表，是数组表示不够好，在数组中我们可以很容易地执行push pop，而在数组上的链表使代码变得复杂，并且与数组实现相比没有优势。
Can you give any example where a linked list implementation is more beneficial, or we cant do without it.
你能举个例子来说明链表实现的好处吗?或者我们离不开链表实现。
5 个解决方案
#1
2
I would say that many practical implementations of stacks are written using arrays. For example, the .NET Stack implementation uses an array as a backing store.
我想说的是，许多栈的实际实现都是使用数组编写的。例如，. net堆栈实现使用数组作为支持存储。
Arrays are typically more efficient because you can keep the stack nodes all nearby in contiguous memory that can fit nicely in your fast cache lines on the processor.
数组通常更有效，因为您可以将堆栈节点都保存在相邻内存中，这些节点可以很好地适应处理器上的快速缓存行。
I imagine you see textbook implementations of stacks that use linked lists because they're easier to write and don't force you to write a little bit of extra code to manage the backing array store as well as come up with a growth/copy/reserve space heuristic.
我猜你会看到教科书上的堆栈实现使用链表，因为它们更容易编写，并且不会强迫你编写一些额外的代码来管理后台数组存储，同时还会提出增长/复制/保留空间启发式。
In addition, if you're really pressed to use little memory, a linked list implementation might make sense since you don't "waste" space that's not currently used. However, on modern processors with plenty of memory, it's typically better to use arrays to gain the cache advantages they offer rather than worry about page faults with the linked list approach.
此外，如果您确实需要使用很少的内存，那么链表实现可能是有意义的，因为您不会“浪费”当前未使用的空间。然而，在拥有大量内存的现代处理器上，最好使用数组来获得它们提供的缓存优势，而不是使用链表方法担心页面错误。
#2
1
Size of array is limited and predefined. When you dont know how many of them are there then linked list is a perfect option.
数组的大小是有限的和预定义的。如果你不知道其中有多少个，那么链表是一个完美的选择。
More Elaborated comparison:-(+ for dominating linked list and - for array)
更详细的比较:-(+表示主导链表和-表示数组)
Size and type constraint:-
尺寸和类型约束:-
-
(+) Further members of array are aligned at equal distance and need contiguous memory while on the other side link list can provide non contiguous memory solution, so sometimes it is good for memory as well in case of huge data(avoids cpu polling for resource).
(+)数组的其他成员在相同的距离上对齐，需要连续的内存，而在另一边的链路列表上可以提供非连续的内存解决方案，所以有时在大数据(避免cpu轮询资源)的情况下，它对内存也有好处。
-
(+) Suppose in a case you are using an array as stack, and the array is of type int.Now how will you accommodate a double in it??
(+)假设在使用数组作为堆栈时，数组的类型为int.现在如何在其中容纳一个double ?
Portability
可移植性
- (+) Array can cause exceptions like index out of bound exceptions but you can increase the chain anytime in a linked list.
- (+)数组可以引起异常，如带界异常的索引，但是您可以在任何时候在链表中增加链。
Speed and performance
速度和性能
- (-)If its about performance, then obviously most of the complexity fall around O(1) for arrays.In case of a linked list you will have to select a starting node to start the tracing and this adds to performance penalty.
- (-)如果它是关于性能的，那么很明显，对于数组来说，大部分的复杂性都在O(1)附近。如果有一个链表，您将必须选择一个启动节点来启动跟踪，这将增加性能惩罚。
#3
0
When the size of the stack can vary greatly you waste space if you have generalized routines which always allocate a huge array.
当栈的大小变化很大时，如果你有一个通用例程，它总是分配一个巨大的数组，那么你就浪费了空间。
#4
0
Obviously a fixed size array has limitation of knowing maximum size before hand.
If you consider dynamic array then Linked List vs. Arrays covers the details including complexities for performing operations.
显然，一个固定尺寸的数组在事先知道最大尺寸是有限制的。如果考虑动态数组，那么链表和数组包含了执行操作的复杂性等细节。
#5
0
Stack is implemented using Linked List because Push and Pop operations are of O(1) time complexities, compared to O(n) for arrays. (apart from flexible size advantage in Linked List)
栈是使用链表实现的，因为Push和Pop操作的时间复杂度是O(1)，而数组的时间复杂度是O(n)。(除了链表的灵活尺寸优势外)
#1
2
I would say that many practical implementations of stacks are written using arrays. For example, the .NET Stack implementation uses an array as a backing store.
我想说的是，许多栈的实际实现都是使用数组编写的。例如，. net堆栈实现使用数组作为支持存储。
Arrays are typically more efficient because you can keep the stack nodes all nearby in contiguous memory that can fit nicely in your fast cache lines on the processor.
数组通常更有效，因为您可以将堆栈节点都保存在相邻内存中，这些节点可以很好地适应处理器上的快速缓存行。
I imagine you see textbook implementations of stacks that use linked lists because they're easier to write and don't force you to write a little bit of extra code to manage the backing array store as well as come up with a growth/copy/reserve space heuristic.
我猜你会看到教科书上的堆栈实现使用链表，因为它们更容易编写，并且不会强迫你编写一些额外的代码来管理后台数组存储，同时还会提出增长/复制/保留空间启发式。
In addition, if you're really pressed to use little memory, a linked list implementation might make sense since you don't "waste" space that's not currently used. However, on modern processors with plenty of memory, it's typically better to use arrays to gain the cache advantages they offer rather than worry about page faults with the linked list approach.
此外，如果您确实需要使用很少的内存，那么链表实现可能是有意义的，因为您不会“浪费”当前未使用的空间。然而，在拥有大量内存的现代处理器上，最好使用数组来获得它们提供的缓存优势，而不是使用链表方法担心页面错误。
#2
1
Size of array is limited and predefined. When you dont know how many of them are there then linked list is a perfect option.
数组的大小是有限的和预定义的。如果你不知道其中有多少个，那么链表是一个完美的选择。
More Elaborated comparison:-(+ for dominating linked list and - for array)
更详细的比较:-(+表示主导链表和-表示数组)
Size and type constraint:-
尺寸和类型约束:-
-
(+) Further members of array are aligned at equal distance and need contiguous memory while on the other side link list can provide non contiguous memory solution, so sometimes it is good for memory as well in case of huge data(avoids cpu polling for resource).
(+)数组的其他成员在相同的距离上对齐，需要连续的内存，而在另一边的链路列表上可以提供非连续的内存解决方案，所以有时在大数据(避免cpu轮询资源)的情况下，它对内存也有好处。
-
(+) Suppose in a case you are using an array as stack, and the array is of type int.Now how will you accommodate a double in it??
(+)假设在使用数组作为堆栈时，数组的类型为int.现在如何在其中容纳一个double ?
Portability
可移植性
- (+) Array can cause exceptions like index out of bound exceptions but you can increase the chain anytime in a linked list.
- (+)数组可以引起异常，如带界异常的索引，但是您可以在任何时候在链表中增加链。
Speed and performance
速度和性能
- (-)If its about performance, then obviously most of the complexity fall around O(1) for arrays.In case of a linked list you will have to select a starting node to start the tracing and this adds to performance penalty.
- (-)如果它是关于性能的，那么很明显，对于数组来说，大部分的复杂性都在O(1)附近。如果有一个链表，您将必须选择一个启动节点来启动跟踪，这将增加性能惩罚。
#3
0
When the size of the stack can vary greatly you waste space if you have generalized routines which always allocate a huge array.
当栈的大小变化很大时，如果你有一个通用例程，它总是分配一个巨大的数组，那么你就浪费了空间。
#4
0
Obviously a fixed size array has limitation of knowing maximum size before hand.
If you consider dynamic array then Linked List vs. Arrays covers the details including complexities for performing operations.
显然，一个固定尺寸的数组在事先知道最大尺寸是有限制的。如果考虑动态数组，那么链表和数组包含了执行操作的复杂性等细节。
#5
0
Stack is implemented using Linked List because Push and Pop operations are of O(1) time complexities, compared to O(n) for arrays. (apart from flexible size advantage in Linked List)
栈是使用链表实现的，因为Push和Pop操作的时间复杂度是O(1)，而数组的时间复杂度是O(n)。(除了链表的灵活尺寸优势外)