队列的两种常见实现之间有什么区别？

Question

在Java中，队列的一个实现是“圆形阵列”，另一个是“链接列表”。它们有什么不同？

Answer 1

在他们是如何使用的术语，几乎没有任何区别可言，当你到了队列的大小限制，除了（我将在几秒钟之解释......）

由于出于其他考虑：

• 链表的方法是有利的，因为可以动态调整队列，没有额外的努力 - 这是链表的基础。当然，这可以通过重新分配一个数组来复制，但这并不是最简单的方法。

• 另外，在链表中，没有未使用的内存：在圆形数组方法中，如果队列的大小小于数组的最大容量，则会出现“空槽”。但是，这并不意味着链表是更多的内存效率，这是因为：

• 圆形阵列方式的优点是没有开销。链表中的每个节点都需要存储对下一个节点的引用 - 如果列表变大，这会加起来。另一方面，循环数组只是您通过索引访问的内存块，因此没有开销。

有赞成的和反对的每种方法，但实际上，它涉及到的具体情况它用在...除非你使用队列没有结束，它可能不会太大的差异。

Answer 2

正常情况下，圆阵的实现是在重复使用的内存稍微好一点，但运行有如果有太多的项目添加到队列增长的风险 - 可能持有过多的内存，如果正常的存储和最大存储容量是在实践中太不同了。

链表更灵活，但一般涉及到更多的垃圾回收。

在实践中，我认为我会感到惊讶，如果你发现你的代码的瓶颈取决于这个选择 - 无论使用哪一个似乎是最直观的给你。

Answer 3

大约与ArrayList和LinkedList之间的差异相同。

• 对于数组，您需要估计队列有多大才能获得，因为您需要为其分配存储空间。但是做到这一点，当接近容量时它更紧凑。 “自由点”仍然占用阵列中的空间，而他们在LinkedList中没有这样做。

• 对于链表，很容易拆卸和从中间添加元素（尽管这不应该在所有需要的队列）。

• 数组是随机存取，这意味着你可以迅速得到该元素的位置x。同样，这个特性在队列中是没有用的，但是。

Answer 4

作为链表实现不具有固定尺寸的队列，而一个为圆形阵列实现，又名ring buffer，典型地具有固定大小（虽然这将有可能使一个调整大小，很多ArrayList调整的方式）。

链表实现使用每个元素更多的内存，但数组实现需要更多的连续内存。随着元素数量变得非常大，这两个问题确实只是一个重大问题。

向圆形阵列实现添加/删除元素非常便宜，因为它只涉及调整计数器和设置引用，而链接列表实现必须在添加时分配元素，并在删除时导致GC开销。

Answer 5

编写代码，使其仅使用接口，但创建队列除外。然后很容易切换实现。

为一个开始选择一个实现。我通常会使用数组变量（例如ArrayList），因为它们更小，并且在今天的计算机上往往会稍微快一点，我认为这是由于缓存（我只是做了一点基准，通过10000个元素队列推送10000000个元素，〜 ArrayBlockingQueue为8.3s，LinkedBlockingQueue为10-11s）。如果我需要索引访问，我也会使用数组变量。只有在列表或队列中间有很多插入/删除的情况下，我才选择链接列表变体。

如果您遇到性能问题并且分析显示队列是瓶颈（这不太可能），那么应使用队列的两个实现进行基准测试并选择更好的队列。