堆栈 ADT（抽象数据类型）实现 - 数组与链接
Stack ADT (Abstract Data Type) implementation- Array vs linked
基于数组与链接实现 Stack 的优缺点是什么。根据我有限的知识，我认为 linked 总是 是实现 Stack 的更好方法，因为：
1) 不需要随机访问。
2) 数组效率低下，因为它们必须调整大小（浪费时间），而且它们使用存储效率低下（一些 space 总是被浪费）
我确定我在这里遗漏了一些东西，因为：
1) java.util.Stack 是基于数组实现的（它是 java.util.Vector 的子class，这是 [=45= 创建之前的遗留 class ] 集合接口，实际上类似于 ArrayList）。因此 java 的创建者选择了基于数组的实现。
2)我在 Whosebug 上阅读了一个答案 here "An array based implementation on the other hand may have better runtime behavior"。这是什么意思，虽然我不知道。
我要查找的比较应包括以下参数：
1)理论时间和存储要求。
2)运行时性能（如果与理论比较不同）。
请包括由于我缺乏知识而未能提及的任何其他重要参数。如果任何结论完全不同，我将使用java。
P.S-我无法在本网站的任何其他答案中找到此问题中提出的所有要点，因此仅在我的所有问题都得到正确且足够详细的回答的情况下，才将此问题标记为重复在另一个问题中。
P.P.S- 我知道这是一个很长的问题，所以 TIA 为您的努力 :) 此外，如果您觉得它太宽泛，请在将其标记为之前评论如何分解它"too broad" 所以我可以根据需要进行编辑。
首先，您应该知道 java.util.Stack 是一个可以追溯到 Java 1.0 的 "legacy collection"。它扩展了 java.util.Vector，实际上是 array-based。然而，这通常被认为是糟糕的 object 设计。这并不意味着 array-based 堆栈是坏事，但您应该意识到仅仅因为 JDK 中有某些内容并不意味着它是个好主意。对于较旧的 API 尤其如此。
更现代的 stack-like 数据结构是 java.util.ArrayDeque。也是array-based。它还有许多其他功能，但如果您坚持使用它的 push 和 pop 方法（相当于 addFirst 和 removeFirst），它基本上就是一个堆栈。请注意，在其文档中它说，
This class is likely to be faster than Stack when used as a stack.
如果您查看实现，Stack 与 Vector 一样是同步的，因此可以稍微减慢速度。 Stack的push和pop方法是根据Vector方法实现的，也是同步的。这意味着额外的方法调用加上嵌套同步。 （不过，JIT 可能可以优化大部分内容。）相比之下，ArrayDeque 不是同步的，它的 stack-like 方法使用直接在其内部数组上操作的简单操作。请注意，我没有在这里进行任何基准测试来验证文档的声明。
无论如何，ArrayDeque 是首选 Java collection 用于需要 stack-like 行为的问题。
但是您问的是 linked 数据结构，而不是 array-based 数据结构。让我们将 ArrayDeque 与另一个 Java linked 数据结构 LinkedList 进行比较。这实现了 Deque 因此它也可以用作堆栈。你说，
1) no random access is needed.
没错。请注意 ArrayDeque 不提供随机访问，即使它是 array-based。两者都没有优势。
2) arrays are inefficient because they have to be resized (waste of time) and also they use storage inefficiently (some space is always wasted)
任何数据结构都会有一些低效的地方。不过，不同的数据结构会有不同的权衡。如果 ArrayDeque 的数组大小不适合堆栈的典型容量，则必须调整它的大小。但是一旦数组足够大，就不需要不断调整大小。如果堆栈缩小，数组仍将消耗空的 space。这可能被视为一种浪费，或者它可能被视为保留内存，以便在堆栈再次增长时不必调整大小和复制它。
将情况与 LinkedList 进行比较。在内部，每个列表元素都需要一个 Node 实例。 （参见来源 here。）每个实例包含三个引用：一个指向数据元素，一个指向下一个 Node，一个指向前一个 Node。假设一个带有压缩指针的 64 位 JVM，每个引用是 32 位。每个 object 都有一个 header 包含一个 64 位标记字和一个 32 位 class 指针。这给出了总共六个 32 位字，或每个列表元素 24 个字节。六个单词中只有一个是 "payload" —— 元素本身 —— 因此每个元素有 20 个字节或 83% 的开销 ！
相比之下，数组中的每个附加元素仅消耗 space 用于对该元素的引用，或 32 位。
例如，将1000个元素存储在一个LinkedList中会消耗大约24K的内存，而将它们存储在一个ArrayDeque中只消耗大约4K的内存。即使数组的大小是容纳 1,000 个元素所需大小的两倍，也只有 8K —— 仍然只是 LinkedList.
大小的一小部分
"An array based implementation on the other hand may have better runtime behavior"
这可能是指遍历 linked 列表比遍历数组慢。有两个原因。首先，link个节点占用的内存较多，因此必须读取更多的内存才能获得相同的信息。在每个节点 24 字节的情况下，2.67 个节点可以放入一个典型的 64 字节缓存行中。其次，link 节点可能随机分布在内存中，因此平均每个缓存行的节点数可能少于此数量。结果是遍历 linked 列表将导致大量缓存未命中，因为引用的局部性很差。
另一方面，由于数组中的引用密集打包且没有开销，因此单个 64 字节缓存行中可以容纳 16 个数组元素。遍历数组将导致更少的缓存未命中。此外，内存子系统针对顺序访问进行了优化，因此它们可能能够预取下一个缓存行，从而进一步减少内存开销。
考虑到内存消耗和内存访问的性能成本，array-based结构通常更可取。可能在某些情况下 linked 结构表现更好，但似乎比大多数人想象的要少。
撇开性能不谈，linked 结构比堆栈的数组结构有一个明显的优势：不可变的持久性。在 array-based 堆栈上压入和弹出元素本质上会改变数组，因此以前的版本不再存在。在 linked 结构上推送和弹出节点不需要改变任何 linked 节点，因此对堆栈过去状态的引用可以持久保存并且将保持不变，即使有人否则pshes 和 pops 这个堆栈上的元素。实际上，它们是不同的堆栈，共享公共部分。这在函数式编程上下文中非常有用。
基于数组与链接实现 Stack 的优缺点是什么。根据我有限的知识，我认为 linked 总是 是实现 Stack 的更好方法，因为：
1) 不需要随机访问。
2) 数组效率低下，因为它们必须调整大小（浪费时间），而且它们使用存储效率低下（一些 space 总是被浪费）
我确定我在这里遗漏了一些东西，因为：
1) java.util.Stack 是基于数组实现的（它是 java.util.Vector 的子class，这是 [=45= 创建之前的遗留 class ] 集合接口，实际上类似于 ArrayList）。因此 java 的创建者选择了基于数组的实现。
2)我在 Whosebug 上阅读了一个答案 here "An array based implementation on the other hand may have better runtime behavior"。这是什么意思，虽然我不知道。
我要查找的比较应包括以下参数：
1)理论时间和存储要求。
2)运行时性能（如果与理论比较不同）。
请包括由于我缺乏知识而未能提及的任何其他重要参数。如果任何结论完全不同，我将使用java。
P.S-我无法在本网站的任何其他答案中找到此问题中提出的所有要点，因此仅在我的所有问题都得到正确且足够详细的回答的情况下，才将此问题标记为重复在另一个问题中。
P.P.S- 我知道这是一个很长的问题，所以 TIA 为您的努力 :) 此外，如果您觉得它太宽泛，请在将其标记为之前评论如何分解它"too broad" 所以我可以根据需要进行编辑。
首先，您应该知道 java.util.Stack 是一个可以追溯到 Java 1.0 的 "legacy collection"。它扩展了 java.util.Vector，实际上是 array-based。然而，这通常被认为是糟糕的 object 设计。这并不意味着 array-based 堆栈是坏事，但您应该意识到仅仅因为 JDK 中有某些内容并不意味着它是个好主意。对于较旧的 API 尤其如此。
更现代的 stack-like 数据结构是 java.util.ArrayDeque。也是array-based。它还有许多其他功能，但如果您坚持使用它的 push 和 pop 方法（相当于 addFirst 和 removeFirst），它基本上就是一个堆栈。请注意，在其文档中它说，
This class is likely to be faster than
Stackwhen used as a stack.
如果您查看实现，Stack 与 Vector 一样是同步的，因此可以稍微减慢速度。 Stack的push和pop方法是根据Vector方法实现的，也是同步的。这意味着额外的方法调用加上嵌套同步。 （不过，JIT 可能可以优化大部分内容。）相比之下，ArrayDeque 不是同步的，它的 stack-like 方法使用直接在其内部数组上操作的简单操作。请注意，我没有在这里进行任何基准测试来验证文档的声明。
无论如何，ArrayDeque 是首选 Java collection 用于需要 stack-like 行为的问题。
但是您问的是 linked 数据结构，而不是 array-based 数据结构。让我们将 ArrayDeque 与另一个 Java linked 数据结构 LinkedList 进行比较。这实现了 Deque 因此它也可以用作堆栈。你说，
1) no random access is needed.
没错。请注意 ArrayDeque 不提供随机访问，即使它是 array-based。两者都没有优势。
2) arrays are inefficient because they have to be resized (waste of time) and also they use storage inefficiently (some space is always wasted)
任何数据结构都会有一些低效的地方。不过，不同的数据结构会有不同的权衡。如果 ArrayDeque 的数组大小不适合堆栈的典型容量，则必须调整它的大小。但是一旦数组足够大，就不需要不断调整大小。如果堆栈缩小，数组仍将消耗空的 space。这可能被视为一种浪费，或者它可能被视为保留内存，以便在堆栈再次增长时不必调整大小和复制它。
将情况与 LinkedList 进行比较。在内部，每个列表元素都需要一个 Node 实例。 （参见来源 here。）每个实例包含三个引用：一个指向数据元素，一个指向下一个 Node，一个指向前一个 Node。假设一个带有压缩指针的 64 位 JVM，每个引用是 32 位。每个 object 都有一个 header 包含一个 64 位标记字和一个 32 位 class 指针。这给出了总共六个 32 位字，或每个列表元素 24 个字节。六个单词中只有一个是 "payload" —— 元素本身 —— 因此每个元素有 20 个字节或 83% 的开销 ！
相比之下，数组中的每个附加元素仅消耗 space 用于对该元素的引用，或 32 位。
例如，将1000个元素存储在一个LinkedList中会消耗大约24K的内存，而将它们存储在一个ArrayDeque中只消耗大约4K的内存。即使数组的大小是容纳 1,000 个元素所需大小的两倍，也只有 8K —— 仍然只是 LinkedList.
"An array based implementation on the other hand may have better runtime behavior"
这可能是指遍历 linked 列表比遍历数组慢。有两个原因。首先，link个节点占用的内存较多，因此必须读取更多的内存才能获得相同的信息。在每个节点 24 字节的情况下，2.67 个节点可以放入一个典型的 64 字节缓存行中。其次，link 节点可能随机分布在内存中，因此平均每个缓存行的节点数可能少于此数量。结果是遍历 linked 列表将导致大量缓存未命中，因为引用的局部性很差。
另一方面，由于数组中的引用密集打包且没有开销，因此单个 64 字节缓存行中可以容纳 16 个数组元素。遍历数组将导致更少的缓存未命中。此外，内存子系统针对顺序访问进行了优化，因此它们可能能够预取下一个缓存行，从而进一步减少内存开销。
考虑到内存消耗和内存访问的性能成本，array-based结构通常更可取。可能在某些情况下 linked 结构表现更好，但似乎比大多数人想象的要少。
撇开性能不谈，linked 结构比堆栈的数组结构有一个明显的优势：不可变的持久性。在 array-based 堆栈上压入和弹出元素本质上会改变数组，因此以前的版本不再存在。在 linked 结构上推送和弹出节点不需要改变任何 linked 节点，因此对堆栈过去状态的引用可以持久保存并且将保持不变，即使有人否则pshes 和 pops 这个堆栈上的元素。实际上，它们是不同的堆栈，共享公共部分。这在函数式编程上下文中非常有用。