java堆栈ADT（抽象数据类型）实现数组与链接

Question

基于数组和链接实现堆栈的优缺点是什么。根据我有限的知识，我觉得linked将永远是实现堆栈的更好方法，因为：

1）不需要随机访问

2）阵列效率低下，因为它们必须调整大小（浪费时间），而且它们对存储的使用效率低下（总是浪费一些空间）

我肯定我错过了一些东西，因为：

1）爪哇。util。堆栈是基于array实现的（它是java.util.Vector的一个子类，它是java collections接口创建之前的遗留类，实际上与ArrayList类似）。因此，java的创建者选择了基于数组的实现

2）我在stackoverflow上读到了一个答案，即“另一方面，基于数组的实现可能具有更好的运行时行为”。虽然我不知道这是什么意思

我寻找的比较应该包括以下参数：

1）理论时间和储存要求

2）运行时性能（如果与理论比较不同）

请包括我因缺乏知识而未能提及的任何其他重要参数。如果这对结论有任何影响，我会使用java

另外，我无法在本网站的任何其他答案中找到此问题的所有要点，因此请仅在其他问题中正确且足够详细地回答了我的所有问题后，将此问题标记为重复问题

p.p.S-我知道这是一个很长的问题，所以感谢你的努力：）如果你觉得它太宽了，那么请在你标记为“太宽”之前评论一下如何分解它，以便我可以根据需要编辑它

Answer 1

首先，您应该知道java.util.Stack是一个“遗留集合”，可以追溯到Java1.0。它扩展了java.util.Vector，这实际上是基于数组的。然而，这通常被认为是糟糕的对象设计。这并不意味着基于阵列的堆栈是一件坏事，但您应该意识到，仅仅因为JDK中有一些东西并不意味着它是一个好主意。对于较旧的API尤其如此

更现代的堆栈式数据结构是java.util.ArrayDeque。它也是基于阵列的。它还有很多其他特性，但如果你坚持使用它的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是不同步的，它的堆栈式方法使用直接在其内部数组上操作的简单操作。注意，我在这里没有做任何基准测试来验证文档的声明

在任何情况下，ArrayDeque都是解决需要类似堆栈行为的问题的首选Java集合

但你问的是链接数据结构，而不是基于数组的数据结构。让我们将ArrayDeque与另一个Java链接的数据结构LinkedList进行比较。这实现了Deque，因此它也可以用作堆栈。你说

1) no random access is needed.

没错。请注意ArrayDeque不提供随机访问，即使它是基于数组的。这对两人都没有好处

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的数组的大小不适合堆栈的典型容量，则必须调整其大小。但一旦阵列足够大，就不需要不断调整大小。如果堆栈缩小，阵列仍将消耗空的空间。这可能被视为浪费，也可能被视为保留内存，以便在堆栈再次增长时不必调整大小和复制

将这种情况与{}进行比较。在内部，每个列表元素都需要一个Node实例。（见资料来源here。）每个实例包含三个引用：一个引用到数据元素，一个引用到下一个Node，一个引用到上一个Node。假设一个带有压缩指针的64位JVM，即每个引用32位。每个对象都有一个包含64位标记字和32位类指针的头。这将提供总共六个32位字，即每个列表元素24字节。这六个字中只有一个是元素本身的“有效负载”，因此每个元素有20个字节或83%的开销

相比之下，数组中的每个附加元素只消耗引用该元素的空间，即32位

例如，在LinkedList中存储1000个元素会消耗大约24K的内存，但在ArrayDeque中存储它们只会消耗大约4K的内存。即使数组的大小是容纳1000个元素所需大小的两倍，也只有8K，仍然只是LinkedList大小的一小部分

"An array based implementation on the other hand may have better runtime behavior"

这可能是指遍历链表比遍历数组慢。这有两个原因。首先，链接节点占用更多内存，因此必须读取更多内存才能获得相同的信息。在每个节点24字节的情况下，2.67个节点可以容纳在典型的64字节缓存线中。其次，链路节点可能会随机分布在内存中，因此平均而言，每个缓存线的节点数可能少于此数。结果是，由于引用的局部性较差，遍历链表将导致大量缓存未命中

另一方面，自从数组中的引用是密集的，没有开销，16个数组元素可以放在一个64字节的缓存线中。遍历数组将导致更少的缓存未命中。此外，内存子系统针对顺序访问进行了优化，因此它们可能能够预取下一个缓存线，从而进一步减少内存开销

考虑到内存消耗和内存访问的性能成本，基于阵列的结构通常更可取。在某些情况下，连接结构的性能可能更好，但似乎比大多数人想象的要少

撇开性能不谈，对于堆栈来说，链接结构比数组结构有一个明显的优势：不可变持久性。在基于数组的堆栈上推送和弹出元素会固有地改变数组，因此以前的版本不再存在。在链接的结构上推送和弹出节点不需要改变任何链接的节点，因此对堆栈过去状态的引用可以持续保留，并且将保持不变，即使其他人推送和弹出该堆栈上的元素。实际上，它们是不同的堆栈，共享公共部分。这在函数式编程环境中非常有用