Java队列的最佳实现？

Question

我正在（用Java）研究递归图像处理算法，该算法从中心点向外递归遍历图像的像素。

不幸的是，这会导致堆栈溢出。所以我决定切换到基于队列的算法。

现在，这一切都很好，但是考虑到它的队列将在很短的时间内分析数千个像素，同时不断弹出和推送，而不保持可预测的状态（长度可能在100到20000之间），队列实现需要具有显著的快速弹出和推送能力。

链表似乎很有吸引力，因为它能够将元素推到自己身上，而无需重新排列列表中的任何其他元素，但为了让它足够快，它需要容易地访问其头部和尾部（如果不是双重链接，则是倒数第二个节点）。遗憾的是，我找不到任何与Java中链表的底层实现相关的信息，所以很难说链表是否真的是一种方式。。。

这就引出了我的问题。在Java中，队列接口的最佳实现是什么？（我不希望编辑或访问队列的头和尾以外的任何内容——我不希望进行任何形式的重新排列或任何其他操作。另一方面，我确实打算进行大量的推送和弹出操作，队列的大小会有很大的变化，因此预分配效率很低。）

Answer 1

看看Deque接口，它在两端都提供了插入/删除功能。LinkedList实现了那个接口(如上所述)，但是对于您的使用来说，ArrayDeque可能更好——您不会为每个节点产生常量对象分配的开销。同样，您使用哪种实现可能并不重要。

正常的多用途主义发挥了作用:针对Deque接口而不是其任何特定实现进行编写的好处在于，您可以非常容易地切换实现来测试哪一个执行得最好。只需更改包含< code>new的行，其余代码保持不变。

Answer 2

如果您使用LinkedList，请小心。如果您这样使用它：

LinkedList<String> queue = new LinkedList<String>();

那么您可能会违反队列定义，因为除了first之外，还可能删除其他元素(LinkedList中有这样的方法)。

但是，如果您像这样使用它：

Queue<String> queue = new LinkedList<String>();

应该没问题，因为这是对用户的提醒，插入应该只发生在后面，删除应该只发生在前面。

您可以通过将LinkedList类扩展到一个PureQueue类来克服Queue接口实现的缺陷，该类抛出任何有问题的方法的UnsupportedOperationException。或者，您可以通过创建只有一个字段(类型为LinkedList object，List)的PureQueue来进行聚合，唯一的方法是默认构造函数、复制构造函数、< code>isEmpty()、< code>size()、< code>add(E element)、< code>remove()和< code>element()。所有这些方法都应该是一行程序，例如:

/**
* Retrieves and removes the head of this queue.
* The worstTime(n) is constant and averageTime(n) is constant.
*
* @return the head of this queue.
* @throws NoSuchElementException if this queue is empty.
*/
public E remove()
{
    return list.removeFirst();
} // method remove()

Answer 3

使用:

Queue<Object> queue = new LinkedList<>();

您可以使用＜code＞。提供（E E E）将元素附加到队列的末尾，然后＜code＞。poll（）以退出队列并检索队列的头（第一个元素）。

Java定义了接口队列，“>链接列表提供了一个实现。

它还维护对头部和尾部元素的引用，您可以分别通过 .getFirst（） 和 .getLast（） 获得这些元素。

感谢@Snicolas对队列接口的建议