3

作为开发人员，他们关心的每个人都必须面临这样的要求：您需要可调整大小的集合，您可以在其中添加、删除、检索 (FIFO)。

在我看到的每个应用程序中，我都使用 List(ArrayList) 来满足这个要求，但我的问题是为什么开发人员不选择 Queue(probably ArrayDeque) 。根据我目前的理解，我发现 ArrayList(List) 和 ArrayDeque(Queue) 对于我所说的要求同样适用。但是我在我的职业生涯中仍然没有发现队列，总是只找到列表。

所以我的问题是为什么不优先使用队列而不是列表。我相信一定有某种原因，但不知何故我错过了这种理解？

更新：-这是我的明确要求

1）加法发生在最后，应该很快。可能 O(1)

2）迭代应该很快

3）查找和删除任何特定元素应该更快。

按照上述要求，我认为 Arralist 比 ArrayDeque 更有意义。这是我的逐点理由

1) Arraylist 和 ArrayDeque 都是 O(1) 。对？

2）两者的迭代性能相同，因为它将基于 index 。对于 ArrayDeque 索引将基于时间戳，而对于 arraylist 用户可以明确提及索引。对？

3) 两者都是 O(1)，因为查找将基于 om 索引进行

4

3 回答 3

1

如果我更改实现，我更喜欢使用任何可以为我提供最简单迁移所需的最小功能集的参考。

如果我只需要添加和删除，我可以这样做

Collection<T> myCol = new // pick any implementation

如果我需要按 FIFO 顺序获取它们，我不会使用 a List，因为该List接口没有弹出最旧的方法。它有一个弹出索引 0 的方法，但这不一样。如果我需要 FIFO 排序，我必须让自己使用 Queue 参考。

Queue<T> myQueue = new // pick any implementation

大多数 Queue 和 Deque 实现本身就是列表，因此可能会造成混淆是有道理的。但你不想这样做：

ArrayDeque<T> myQueue = new ArrayDeque<T>(); // yuck! don't use a concrete reference!

相反，使用具有完成这项工作所需的最少功能的参考。在这种情况下，这意味着使用接口而不是ArrayDeque类的实现特定方法。

于 2013-12-24T18:17:22.977 回答
1

如果您只打算访问集合的末端，那么 ArrayList 和 ArrayDeque 本质上将具有相同的功能。如果您的目标是将集合的使用限制为 FIFO，那么我会说您最好只使用队列，因为双端队列将允许在任一端进行扩展和收缩（而不是 FIFO）。

另一方面，如果您想知道使用 ArrayDeque 以获得比 ArrayList 更好的性能，我认为它们是等效的。当它们需要更多空间并且在任何索引处的访问仍然是恒定的（尽管您将其限制为 FIFO）时，两者都需要调整大小。如果性能是一个问题，您可以通过使用“循环队列”来提高性能，其中队列可以在第 N 个索引处环绕并在索引 0 处重新启动（防止您因为删除时需要经常调整大小）大小仍然小于容量）。

数组实现的另一个好处是更好的缓存未命中/命中，这是一个不错的好处。

于 2013-12-24T18:33:01.700 回答
0

除了这里提到的，我个人认为这也可能是语言障碍的情况。有些人可能会觉得 poll、peek、提供一些令人费解的词，因此他们对 Queue 视而不见，并使用标准 List 自己实现队列。

于 2013-12-24T18:35:18.623 回答