java - 如果数组更易于使用且功能更强大，为什么还要使用队列和堆栈等数据结构？

Question

这可能是一个愚蠢的问题，但它已经困扰我一段时间了。大多数编程语言都有数组(例如 Java、C/C++、C#...好吧，Python 有列表!)，但在我看到的许多文献中，某些数据结构(例如堆栈和队列)被视为与数组更基本的结构。但既然这么多语言都对数组有如此强大的支持，为什么有人会使用堆栈或队列呢？我意识到，从概念上讲，数组以外的数据结构可能更适合该模型，但考虑到您可能必须实现自己的堆栈或队列，考虑到基本数组的性质，需要做更多的工作。

我想到的一个例子来自 these notes在大风沙普利号上 算法维护一个空闲人员列表(在堆栈或队列中)。 仅使用数组并相信自己只查看它的前端/末尾不是更容易吗？

我想我是在问，为什么有人会费心使用堆栈或队列之类的东西，而大多数都是使用数组实现的，而且数组无论如何都更强大？

Answer 1

有几个原因。首先，如果您的实现与算法更加匹配，将会很有帮助。也就是说，如果您的算法使用堆栈，那么如果您可以说，例如，stack.push(thing) 而不是编写:

，则会很有用。

if (stack_index >= stack_array.length)
{
    // have to extend the stack
    ....
}
stack_array[stack_index++] = thing

并且您必须在将某些内容压入堆栈的每个地方编写该代码。每次想要从堆栈中弹出时，您都必须编写多行代码。

我不了解你的情况，但我发现当我编写这样的代码时非常容易犯错误。

似乎更容易、更清晰、更可靠地将功能封装到 Stack 对象中，然后您可以按预期使用该对象:通过调用 push 和pop 方法。

另一个好处是，当您发现自己必须执行快速线程安全堆栈时，您可以修改您的 Stack 类，以在更改内部结构(即数组)的任何代码周围放置锁，并且任何调用者都会自动拥有一个线程安全的堆栈。如果您要直接在代码中寻址数组，那么您必须前往访问底层数组的每个位置并添加锁定语句。我认为您在某个地方犯错误的可能性比偶数更大，然后您会在追踪间歇性故障时度过一段有趣的时光。

数组本身并不是特别强大。他们灵活，但他们没有智慧。我们将行为包装在数组周围，以限制它们可以执行的操作，这样我们就不必“相信自己”不会做愚蠢的事情，也可以更轻松地做正确的事情。如果我正在实现一个使用队列的算法，那么我将考虑具有入队和出队操作的队列，而不是具有我所使用的头索引和尾索引的链表或数组。必须管理等等。

最后，如果您编写了 Stack 或 Queue 或类似的数据结构实现，测试它并证明其正确，您可以在多个项目中一遍又一遍地使用它，而无需再次查看代码。 它就是有效的。这与使用数组来滚动你自己的数组相反，这样你不仅必须在使用堆栈的每个项目中调试它，而且你有可能搞砸每一个推送或流行。

总而言之，我们创建数据结构而不是使用原始数组:

1. 因为从数据结构操作的角度思考比从数组的使用机制角度思考更容易。
2. 代码重用:编写一次、调试，然后在多个项目中使用。
3. 简化代码(stack.push(item) 而不是多行数组索引)。
4. 减少出错的可能性。
5. 更容易让下一个人过来并了解您所做的事情。 “哦，他正在将项目插入堆栈。”