为什么列表比队列更受青睐？

Question

作为开发人员，每个人在他们的职业生涯中都必须面对需要可调整大小的集合的要求，您可以添加、删除、检索(FIFO)。

在每个应用程序中，我看到使用List(ArrayList)来满足这个需求，但我的问题是为什么开发人员不选择Queue(可能是ArrayDeque)。根据我目前的了解，我认为ArrayList(List)和ArrayDeque(Queue)在满足我所说的需求时同样好。但是我从未在我的职业生涯中遇到过队列，总是只找到List。

因此，我的问题是为什么不优先选择队列而不是List。我相信一定有一些原因，但不知何故我缺乏理解？

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

1)添加发生在末尾，应该很快。可能是O(1)

2)迭代应该很快

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

根据以上要求，我认为Arralist比ArrayDeque更有意义。以下是我的逐点原因：

1)Both Arraylist and ArrayDeque will be O(1) . Right?

2)迭代性能对于两者都是相同的，因为它将基于索引。对于ArrayDeque，索引将基于时间戳，而对于arraylist，用户可以显式地指定索引。对吗？

3)对于两者来说，它将是O(1)，因为查找将基于索引进行。

- M Sach

---

相关（我实际上正在寻找它，因为我记得有一个重复的）：为什么典型的Array List实现不是双端的？ - cHao

Answer 1

我更喜欢使用提供最小功能集的参考文献，以便在更改实现时轻松迁移。如果只需要添加和删除，我可以这样做：

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

如果我需要按照FIFO顺序获取它们，我将不使用List，因为List接口没有弹出最旧元素的方法。它有一种弹出索引0的方法，但那不是同样的东西。如果我需要FIFO排序，我必须接受使用队列引用。

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

大多数队列和双端队列实现本身就是列表，因此可能会让人感到困惑。但是你不应该这样做：

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

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

- corsiKa

---

corsiKlause 哈哈哈。请查看我的更新帖子，并友好地告诉我您的想法。 - M Sach

我认为如果我需要先进先出的检索，我必须使用队列；但如果我想按索引进行检索，我必须使用列表。这正确吗？ - M Sach

听起来没错。如果你只需要从末尾删除，考虑使用CircularArrayQueue - 没有默认的Java实现，但是如果你在互联网上搜索，就会找到可用的实现。 - corsiKa

FYI：ArrayList未能通过您对第3个要求的测试。如果您需要从中间删除，ArrayList具有O(n)的删除操作。 :-{ - corsiKa

正如你所说，“如果需要从中间删除，ArrayList 的删除操作的时间复杂度为 O(n)。” 我认为你的意思是删除操作的时间复杂度为 O(1)，但是被删除元素下方的元素需要向上移动。因此总成本变为 O(n)。对吗？ - M Sach

我猜你可以那样看待它，但这有点意味着移动其他节点是可选的，而实际上并不是。如果你仔细想想，其实不需要删除：你只需要将其他节点移到它的位置上方。所以，如果你这样看，你可以把删除称为O(0)。考虑到成本时，我更喜欢考虑所有必需的操作，这就是为什么我说ArrayList具有O(n)的删除操作。你不能只将数组索引设置为空，然后说“哦，看，它被删除了！” - corsiKa

Answer 2

如果你只打算访问集合的末端，那么ArrayList和ArrayDeque将具有相同的功能。如果你的目标是限制集合仅按FIFO顺序使用，则最好使用队列而不是deque，因为deque将允许在任一端进行扩展和收缩（而不是FIFO）。

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

数组实现的另一个好处是具有更好的高速缓存命中率/未命中率，这是一个不错的优点。

- CM0491

Answer 3

除了这里提到的，我个人认为这也可能是语言障碍的问题。一些人可能会觉得poll、peek、offer这些词有点令人困惑，因此他们对队列不屑一顾，并使用标准列表自己实现队列。

- Shinhung