java - LinkedList与堆栈

Question

在Java中，可以使用LinkedList实现的堆栈。换句话说，您可以使用链表来实现堆栈的所有功能。从这个意义上说，为什么我们仍然需要堆栈类，为什么我们不只是坚持使用链表来保持简单性呢？
谢谢

Answer 1

首先，在Stack文档的介绍中说:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

这就告诉我们Stack类主要是一个剩余的东西，在新的Java Collections Framework中或多或少地变得多余了。

其次，“提供相同的功能”不是衡量一个类是否应该存在的好方法。尽管LinkedList提供了生成堆栈所需的所有操作，但它的性能会很差。链接列表非常适合在随机位置插入和删除元素。在堆栈中，我们只能在末尾追加或删除，这使得ArrayList对实现堆栈更具吸引力。

在这一点上，我们意识到ArrayList和LinkdList都提供了List的功能，这使我们接近了良好的面向对象设计的核心:

我们在接口(interface)中定义了一组操作(例如List)。

我们提供该接口(interface)的一个或多个实现，这些实现必须全部提供所需的功能，但可以针对特定用例(例如ArrayList或LinkedList)进行优化。

如果某个特定的使用模式特别频繁地发生，我们可能决定添加另一个在其名称中引用该模式的类，这将使代码的结构更好。例如，我们可以通过简单地委派给Stack来实现ArrayList，但是提供一种类型，该类型以其名称清楚地说明其含义，并且不提供可能违反堆栈概念的操作(例如随机访问)。 (这不是java.util.Stack所做的，这使我们回到了文档的引文中。)

请注意，List和较新的Deque接口(interface)之间的继承关系比List和Stack之间的继承关系更加一致。 LinkedList实现了正确的Deque，因为Deque要求可以从/到开头或结尾添加元素或从中删除元素，并且LinkedList通过在随机位置提供插入和删除来满足此要求。另一方面，Stack实现了List，应将其视为可疑的。

最近更新:由于我对“链接列表可在随机位置插入和删除元素非常有用”的说法不赞成。在堆栈中，我们只能在末尾追加或删除，这使得ArrayList对实现堆栈更具吸引力。”，我想对此进行扩展。

链接列表允许在恒定时间内在任意位置插入和删除元素。另一方面，在给定索引的情况下，查找元素需要花费线性时间。当我说它们适合在随机位置插入和删除时，是指由迭代器而不是索引给出的位置。如果给定索引，则对于链表和数组，插入和删除将是线性时间操作，但是链表的常数因子会更高。

基于数组的列表允许在末期摊销固定时间的插入和删除，并允许按索引进行固定时间的访问。无论位置是由索引还是由迭代器(基本上只是数组的索引)提供，在随机位置处添加和删除元素都是线性时间操作。

在堆栈实现中，不需要链表的唯一优点–能够在恒定时间内在任意位置(由迭代器提供)插入和删除元素的功能。另一方面，它的内存开销要高得多，并且其内存访问要大大逊于连续阵列。鉴于在这两种情况下，用于从列表末尾追加和删除项目的渐近复杂性都是摊销常量，因此基于数组的列表是实现堆栈存储的更好选择。

更好的数据结构是可变数量的固定大小的缓冲区，这些缓冲区通过指针链接在一起。这种数据结构通常用于实现所谓的双端队列。它以很少的额外开销提供了阵列的大多数优点，并且从末尾(或开始)向/从末尾添加和删除不仅是摊销的，而且始终是恒定时间的操作。