堆栈ADT（抽象数据类型）implementation-阵VS联 [英] Stack ADT (Abstract Data Type) implementation- Array vs linked

问题描述

什么是优点和VS联实现基于阵列堆栈的利弊。从我有限的知识，我觉得联会的总是的是执行堆栈更好的办法，因为：

1）没有随机接取是必要的。

2）阵列是低效的，因为他们已经被调整（浪费时间），同时他们使用的存储效率低下（一些空间总是被浪费）

我敢肯定，IM在这里的东西，因为：

1）java.util.Stack中基于阵列实施（其java.util.Vector中的一个子类，是从创建Java集合接口的前一个遗留类和几乎类似于ArrayList的）。所以Java的创造者选择了做一个基于阵列的实现。

2）香港专业教育学院读的答案<一个href=\"http://stackoverflow.com/questions/26263376/should-stacks-be-made-from-arrays-or-linked-list-java\">here计算器上说：在另一方面，一个基于阵列的实现可能有更好的运行时行为。是什么这意味着，虽然我不知道。

比较即时寻找应包括以下参数：

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

2）运行时的性能（如果从理论上比较不同）。

请包括我都没有提及，由于我缺乏知识的其他重要参数。用java林如果使的任何的差异在所有的结论。

PS-我无法找到这个问题问到这个网站上的其他任何答案，所以请只纪念这一问题作为仅复制的情况下，我所有的问题已经在其他问题正确和足够详细的回答。在所有点

PPS-我知道这是一个很长的问题，所以TIA你的努力:)另外，如果你觉得这是过于宽泛那么如何打破它，你将其标记为前亲切评论过于宽泛，所以我可以编辑它根据需要

解决方案

首先，你应该知道， java.util.Stack中的是一个遗留的collection的日期回到Java 1.0的所有道路。它扩展了 java.util.Vector中的这的确是基于阵列的。然而，这通常被认为是坏的目标设计。这并不意味着，基于阵列的堆栈是一件坏事，但你应该知道，只是因为事情是在JDK并不意味着它是一个好主意。这是特别真实的较旧的API。

一个更现代的类栈数据结构是 java.util.ArrayDeque中。这也是基于阵列的。它具有一些其他的功能，但如果你坚持它的推和弹出方法（相当于 addfirst仅和 removeFirst ），它基本上是一个堆栈。需要注意的是它的文档中它说，

  

本类是可能比的Stack 作为堆栈使用时。

快

如果你看一下实现，的Stack ，如矢量，是同步的，这样就可以慢下来一点点。 的Stack 的推和弹出方法在计算实现的矢量的方法，这也是同步的。这意味着，附加的方法调用加上嵌套同步。 （该JIT大概可以优化掉大部分的这一点，虽然。）与此相反， ArrayDeque 不同步的，其堆叠类似方法直接使用在其内该操作简单的操作数组。请注意，我没有做任何基准这里来验证文档的说法。

在任何情况下， ArrayDeque 是preferred Java集合用于那些需要类栈行为问题。

但是，你问的有关链接的数据结构，而不是基于阵列的人。让我们比较 ArrayDeque 到另一个Java链接的数据结构，的LinkedList 。这种器具 deque的所以它也可以用作一个堆栈。你说，

  

1）没有随机存取是必要的。

真。需要注意的是 ArrayDeque 不提供随机访问，即使它是基于阵列的。没有优势要么。

  

2）阵列是低效的，因为他们必须被调整（浪费时间），同时他们使用的存储效率低下（一些空间总是被浪费）

的任何数据结构会产生一定的低效率。不同的数据结构会有不同的权衡，虽然。如果 ArrayDeque 的数组大小不为堆栈的典型能力，将有被调整。但是，一旦该阵列足够大，它并不需要被连续调整大小。如果堆栈收缩，阵列将仍然占用空间是空的。这可以被看作是一种浪费，或者它可以被看作是保持在备用存储器，使得它不必被调整大小并复制如果堆栈再次增长

比较情况的LinkedList 。在内部，每个列表元素需要节点实例。 （见源<一个href=\"http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b132/src/share/classes/java/util/LinkedList.java#l970\" 。相对=nofollow>这里）每个实例都包含三个参考：一个数据元素，一到下一个节点，而一到previous 节点。假设以com $ P $ 64位JVM pssed三分球，这是每参考32位。每个对象具有包含一个64位标记字和一个32位的类指针的标题。这给了总共6个32位的字，或每列表元素的24个字节。只有六个词之一是有效载荷 - 元素本身 - 所以这是20个字节或83％的开销的每个元素的

相反，在一个阵列中的每个附加元素仅消耗的引用，该元件的空间中，或32位。

例如，存储1,000个元素在的LinkedList 消耗左右的内存24K，但它们存储在 ArrayDeque 仅消耗内存约4K。即使阵列的两倍大，因为它必须持有1000元，这仅仅8K - 仍然只是大小的分数的LinkedList

  

另一方面阵列基于实现可具有更好的运行时行为

此可能是指遍历链接列表比遍历阵列慢。有两个原因。首先，链接节点占用更多的存储器，所以更存储器必须以获得相同的信息被读出。在每个节点24个字节，2.67节点可以装在一个典型的64字节的缓存行。第二，该链接的节点都可能是左右内存■$ P $垫有些随机，所以平均可以有比这个每高速缓存线更少的节点。其结果是，遍历一个链表会造成因为参考这个可怜的局部性很多缓存未命中。

在另一方面，由于以阵列引用被密集地填充有没有开销，16阵列元件可以一个64字节的高速缓存线内适合。遍历数组会造成许多更少的高速缓存未命中。此外，内存子系统优化顺序访问，所以他们也许能prefetch下一个高速缓存行，减少内存开销更进一步。

考虑内存消耗和内存访问的性能的成本，基于阵列的结构通常是preferable。可能有一些情况下，链接结构有更好的表现，但似乎有少于大多数人的想法。

设置性能之外，还有一个明显的优势，以链接结构对数组结构栈：不变的坚持。推动和基于阵列的堆栈上弹出元素固有变异的数组，所以previous版本不复存在。推动并在联结构弹出节点不需要突变的任何链接的节点的，所以要叠层的过去状态的引用可以被持续保持，将保持不变，即使别人推和弹出该​​堆栈上的元件。有效地它们是不同的堆栈，用共同部分共享。这是函数式编程环境是非常有用的。

What are the pros and cons of implementing Stack based on array vs linked. From my limited knowledge i feel that linked will always be a better way to implement Stack because:

1) no random acess is needed.

2)array are inefficient because they have to be resized(waste of time) and also they use storage inefficiently (some space is always wasted)

Im sure im missing something here because:

1) java.util.Stack is implemented based on array (its a subclass of java.util.Vector which is a legacy class from before the creation of java collections interface and is virtually similar to ArrayList). So the creators of java chose to do an array based implementation.

2)Ive read an answer here on stackoverflow that "An array based implementation on the other hand may have better runtime behavior". what is meant by this though i have no clue.

The comparison im looking for should include the following parameters:

1)Theoretical time and storage requirement.

2)Runtime performance (if different from theoretical comparison).

Please include any other important parameter which i have failed to mention due to my lack of knowledge. Im using java if that makes any difference at all on the conclusion.

P.S-I couldnt find all the points asked in this question in any other answer on this website so please only mark this question as duplicate only in case all my questions have been answered correctly and in enough detail in the other question.

P.P.S- I know this is a very long question so TIA for your effort :) Also if you feel it is too broad then kindly comment on how to break it up before you tag it as "too broad" so i may edit it as required.

解决方案

First, you should be aware that java.util.Stack is a "legacy collection" that dates all the way back to Java 1.0. It extends java.util.Vector which is indeed array-based. However, this is generally regarded as bad object design. That doesn't mean that an array-based stack is a bad thing, but you should be aware that just because something is in the JDK doesn't mean that it's a good idea. This is particularly true of the older APIs.

A more modern stack-like data structure is java.util.ArrayDeque. It's also array-based. It has a bunch of other features, but if you stick to its push and pop methods (equivalent to addFirst and removeFirst), it's basically a stack. Note that in its documentation it says,

This class is likely to be faster than Stack when used as a stack.

If you look at the implementations, Stack, like Vector, is synchronized, so that can slow it down a bit. Stack's push and pop methods are implemented in terms of Vector methods, which are also synchronized. This means additional method calls plus nested synchronization. (The JIT can probably optimize away most of this, though.) By contrast, ArrayDeque is not synchronized, and its stack-like methods use simple operations that operate directly on its internal array. Note, I haven't done any benchmarking here to validate the documentation's claims.

In any case, ArrayDeque is the preferred Java collection to use for problems that require stack-like behavior.

But you were asking about linked data structures as opposed to array-based ones. Let's compare ArrayDeque to another Java linked data structure, LinkedList. This implements Deque so it can also be used as a stack. You said,

1) no random access is needed.

True. Note that ArrayDeque doesn't offer random access, even though it's array-based. No advantage to either.

2) arrays are inefficient because they have to be resized (waste of time) and also they use storage inefficiently (some space is always wasted)

Any data structure will have some inefficiencies. Different data structures will have different tradeoffs, though. If ArrayDeque's array isn't sized for the typical capacity of the stack, it'll have to be resized. But once the array is big enough, it doesn't need to be resized continually. If the stack shrinks, the array will still consume space that's empty. This could be viewed as a waste, or it could be viewed as holding memory in reserve so that it doesn't have to be resized and copied if the stack grows again.

Compare the situation to LinkedList. Internally, each list element requires a Node instance. (See source here.) Each instance contains three references: one to the data element, one to the next Node, and one to the previous Node. Assuming a 64-bit JVM with compressed pointers, that's 32 bits per reference. Each object has a header containing a 64-bit mark word and a 32-bit class pointer. That gives a total of six 32-bit words, or 24 bytes per list element. Only one of the six words is the "payload" -- the element itself -- so that's 20 bytes or 83% overhead per element!

By contrast, each additional element in an array consumes only the space for the reference to that element, or 32 bits.

For example, storing 1,000 elements in a LinkedList consumes about 24K of memory, but storing them in an ArrayDeque consumes only about 4K of memory. Even if the array is twice as big as it needs to be to hold the 1,000 elements, that's only 8K -- still only a fraction of the size of the LinkedList.

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

This is probably referring to the traversing the linked list being slower than traversing the array. There are two reasons for this. First, the link nodes occupy more memory, so more memory must be read in order to get the same information. At 24 bytes per node, 2.67 nodes can fit in a typical 64-byte cache line. Second, the link nodes are likely to be spread around memory somewhat randomly, so on average there may be fewer nodes than this per cache line. The result is that traversing a linked list will cause a lot of cache misses because of this poor locality of reference.

On the other hand, since references in an array are densely packed with no overhead, 16 array elements can fit within a single 64-byte cache line. Traversing an array will cause many fewer cache misses. Furthermore, memory subsystems optimize for sequential access, so they might be able to prefetch the next cache line, reducing memory overhead even further.

Considering memory consumption and the performance cost of memory access, array-based structures are usually preferable. There may be some cases where linked structures perform better, but there seem to be fewer than most people think.

Setting performance aside, there is one clear advantage to a linked structure over an array structure for a stack: immutable persistence. Pushing and popping elements on an array-based stack inherently mutates the array, so previous versions no longer exist. Pushing and popping nodes on a linked structure doesn't need to mutate any of the linked nodes, so references to past states of the stack can be held persistently and will remain unchanged, even if somebody else pushes and pops elements on this stack. Effectively they are different stacks, with the common portions shared. This is extremely useful in functional programming contexts.

这篇关于堆栈ADT（抽象数据类型）implementation-阵VS联的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！