java - 堆栈ADT(抽象数据类型)实现-数组与链接

Question

基于数组vs链接实现Stack的优缺点是什么？据我所知，我认为链接永远是实现Stack的更好方法，因为：

1）不需要随机访问。

2）数组效率低下，因为它们必须调整大小（浪费时间），而且存储效率低下（总是浪费一些空间）

我确定我在这里错过了一些东西，因为：

1）java.util.Stack是基于数组实现的（它是java.util.Vector的子类，它是Java集合接口创建之前的旧类，实际上类似于ArrayList）。因此，java的创建者选择执行基于数组的实现。

2）我已经阅读了关于stackoverflow的答案here，“另一方面，基于数组的实现可能具有更好的运行时行为”。这是什么意思，尽管我不知道。

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

1）理论时间和存储要求。

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

请包括由于我缺乏知识而未能提及的任何其他重要参数。我使用java，如果在结论上有任何不同的话。

附言：我无法在本网站上的任何其他答案中找到该问题的所有要点，因此仅在我的所有问题均已正确回答且在另一问题中足够详细时，才将此问题标记为重复。

PPS-我知道这是一个很长的问题，因此TIA需要您努力：)另外，如果您觉得它太宽泛，请在将其标记为“太宽泛”之前对如何分解加以评论，以便我可以根据需要对其进行编辑。

Answer 1

首先，您应该意识到java.util.Stack是一个“遗留集合”，可以追溯到Java 1.0。它扩展了java.util.Vector的确是基于数组的。但是，这通常被认为是不良的对象设计。这并不意味着基于数组的堆栈是一件坏事，但是您应该意识到，仅因为JDK中包含某些内容并不意味着它是一个好主意。对于较旧的API尤其如此。

java.util.ArrayDeque是更现代的类似于堆栈的数据结构。它也是基于数组的。它还有很多其他功能，但是如果坚持使用push和pop方法（相当于addFirst和removeFirst），则基本上是堆栈。请注意，在其文档中说：


  当用作堆栈时，此类可能比Stack更快。


如果您看一下实现，则Stack与Vector一样，是同步的，因此会使其速度变慢。 Stack的push和pop方法是根据Vector方法实现的，这些方法也是同步的。这意味着附加的方法调用以及嵌套的同步。 （不过，JIT可能可以优化其中的大多数功能。）相反，ArrayDeque是不同步的，其类似堆栈的方法使用直接在其内部数组上进行操作的简单操作。请注意，在这里我没有做任何基准测试来验证文档的声明。

无论如何，ArrayDeque是首选的Java集合，用于需要类似堆栈行为的问题。

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


  1）不需要随机访问。


真正。请注意，即使ArrayDeque基于数组，也不提供随机访问。两者都没有优势。


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


任何数据结构都会有效率低下的情况。但是，不同的数据结构将具有不同的权衡。如果ArrayDeque的数组的大小不适合堆栈的典型容量，则必须重新调整大小。但是，一旦阵列足够大，就不需要连续调整大小。如果堆栈缩小，则阵列仍将占用空的空间。可以将其视为浪费，也可以将其视为保留内存，以便在堆栈再次增长时不必调整大小和复制内存。

比较情况与LinkedList。在内部，每个列表元素都需要一个Node实例。 （请参见源here。）每个实例包含三个引用：一个引用到数据元素，一个引用到下一个Node，以及一个引用到前一个Node。假设具有压缩指针的64位JVM，则每个引用32位。每个对象都有一个包含64位标记字和32位类指针的标头。这样一来，总共有六个32位字，即每个列表元素24个字节。六个词中只有一个是“有效负载”（即元素本身），因此每个元素20个字节或83％的开销！

相比之下，数组中的每个其他元素仅占用用于引用该元素的空间，即32位。

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


  “另一方面，基于数组的实现可能具有更好的运行时行为”


这可能是指遍历链表比遍历数组要慢。有两个原因。首先，链接节点占用更多的内存，因此必须读取更多的内存才能获得相同的信息。每个节点24字节时，典型的64字节高速缓存行可以容纳2.67个节点。其次，链接节点可能会在内存中随机分布一些，因此平均而言，每条缓存行的节点数可能少于该节点。结果是，遍历链接列表将导致大量缓存丢失，因为引用的本地性很差。

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

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

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