java - 数组堆栈、链接堆栈和堆栈之间有什么区别

Question

最近我在研究Stack、Bag 和 Queue。当我阅读类笔记时，我的脑海中浮现出一个问题。

数组和链接有什么区别？为什么我们不能只使用Stack？

Stack<String> stack = new Stack<String>()
Stack<String> stack = new ArrayStack<String>()

这两个我认为他们做同样的事情，他们可以查看、弹出和删除

我不明白为什么我们需要实现数组或链接

Answer 1

基本上，这与性能有关。 “堆栈”只是一个接口(interface) - 它是一种通过某些命令集获取数据以进行查看和修改的方法。然而，这并没有说明数据如何存储在结构中 - 这就是 ArrayStack 和 LinkedStack 等内容变得重要的地方。

本质上，这些堆栈中的每一个都由一些更原始的结构“支持” - 这是实际存储我们放入其中的数据的幕后部分。对于ArrayStack来说，这是一个数组；对于LinkedStack来说，这是一个链表。

那么有什么区别呢？好吧，考虑一下数组。数组必须使用连续的内存 - 也就是说，必须在内存中为整个数组提供一个 block ，该 block 是一个长而不间断的 block 。另一方面，链表由通过指针链接的各个节点组成 - 根本不要求它是连续的。这使得调整数组大小成为问题 - 本质上，我们必须创建一个新数组，并将所有内容复制到其中以调整其大小。这可能是堆栈的问题，因为我们通常不知道堆栈将达到多大。链接列表没有这个问题 - 我们只需创建一个新节点并将其链接到列表，就像以前一样。

因此，总体而言，差异在于内存使用和性能 - 尝试实现两者并计时它们如何处理大数据以查看差异。