logo标签列表

数组、栈和队列的性能差异

javaarraysstackqueue
4

数组、栈和队列的搜索性能如何？

我认为数组是最快和最直接的，因为我可以通过调用索引来立即访问任何元素。这个观点正确吗？那么栈和队列的性能如何？它们之间有什么比较？

2
你的问题比较宽泛，请问能否具体说明你要询问的内容是什么？ - Nick Bailey
我的老师让我比较一下数组和栈队列的不同之处。比较应该涉及以下三个方面：数组与栈队列的比较：a-它们的角色 b-访问限制 c-搜索的便利性 d-插入或删除操作。 - Somaya
在Java中，对于您提到的所有集合，都有一个数组实现。对于暴力搜索，性能应该基本相同。您可以做出某些操作比其他操作更昂贵的假设，但是它们都具有相同的O（N）搜索N个元素，因此根据理论得出的任何差异结论都不太可能有用，在我看来。 - Peter Lawrey
6个回答
3
我会尽可能简单地回答。
堆栈和队列是用于临时存储数据，以便您可以逐个处理内容。就像购买电影票的队列或一堆煎饼一样，您每次处理一个元素。
数组也用于存储数据以及从开头、结尾或中间访问元素。对于搜索来说，数组是更好的选择。
你能在堆栈和队列中搜索元素吗？可能可以。但这不是它们的主要用途。
2

数组（以及基于数组的集合，例如ArrayList）在搜索性能方面很差，因为在最坏的情况下，您将比较每个项目（O(n)）。 但是，如果您不介意修改元素的顺序，可以对数组进行排序（Arrays.sort(yourArray)），然后在其上使用Arrays.binarySearch(yourArray, element)，这提供了一个O(log n)的性能概要（比O(n)好得多）。

堆栈的时间复杂度为O(n)，所以不行。

队列甚至没有被设计用于迭代，因此在这里查找对象将意味着消耗整个队列，这既不高效（O(n)），也可能不是您想要的。

因此，在您提出的数据结构中，我会选择一个排序过的数组。

现在，如果您不介意考虑其他数据结构，您确实应该看看那些使用哈希函数的数据结构（HashSet，HashMap...）。 哈希函数非常擅长搜索元素，性能概要为O(1)（使用您对象中良好的hashcode()方法）。

谢谢大家的回答，我还不知道如何写我的答案，这是老师布置的作业。有些答案我没能理解，因为我还是Java的初学者 :) - Somaya
1
很遗憾，我们不能替你完成作业。我们可以回答问题，但你需要证明你理解了。 - Nick Bailey
2
在Java中，你有ArrayList（基于数组构建），一个Stack（也是基于数组构建的）以及ArrayQueue和ArrayDeque（也是基于数组构建的）。由于它们都使用相同的底层数据结构，因此它们的访问速度基本相同。对于暴力搜索，扫描或迭代它们的时间（它们都支持迭代）为O（n）。顺便说一句，即使HashMap也使用数组存储其条目，这就是为什么迭代其元素以查找值（例如containsValue）也是O（n）的原因。
虽然你可以有一个排序过的数组，它更自然地适合于ArrayList，但你同样可以认为PriorityQueue将最有效地找到并删除下一个元素。Stack非常适合查找最近添加的元素。
要回答这个问题，你必须确定提问者所做的假设。如果没有这些进一步的假设，你必须说它们都可以被利用。在这种情况下，我会使用ArrayList，因为在我看来它是最简单易懂的。
1
这取决于你的搜索方式（或搜索算法）是如何实现的。像BFS、DFS这样的某些搜索应用程序中，栈或队列也可能有所帮助。但在正常情况下，当你使用线性搜索时，你可以考虑使用数组或ArrayList。
1

栈、队列和数组都是三种不同且高效的数据结构，但作为一名生物信息学家，如果您想存储生物学数据，应该选择栈作为数据结构，因为递归过程的后进先出特性表明它是最合适的数据结构。递归实际上是栈的一个特征。在每个过程调用中，一个值可以轻松地被推入其中，并在退出过程时检索。因此，它实际上是一种易于使用的方法。

0

你不能将一个数据结构与另一个进行比较。每个数据结构都有其优点和缺点。

虽然数组很好，但由于其固定大小，您不能始终使用它们。它们用于插入、删除等操作，因为它们需要O(1)时间。

但是，当您只想从一侧访问和插入数据，并且不想在中间执行搜索、删除时，可以选择堆栈和队列。堆栈和队列仅在访问元素的方法上有所不同。在堆栈中，您从输入数据的同一侧访问数据[LIFO]，需要O(1)时间。在队列中，您从另一个角落[FIFO]访问数据。可以访问中间的元素，但这不是它们的主要用途。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接