Java Queue的最佳实现？

Question

我正在使用递归图像处理算法(在Java中),该算法以递归方式从中心点向外遍历图像的像素.

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

现在,这一切都很好而且花花公子 - 但考虑到它的队列将在很短的时间内分析成千上万的像素,同时不断地弹出和推动,而不保持可预测的状态(它可以在长度100之间的任何地方,和20000); 队列实现需要具有显着快速的弹出和推送能力.

链表似乎很有吸引力,因为它能够在不重新排列列表中的任何其他内容的情况下将元素推送到自身,但为了使其足够快,它需要轻松访问其头部和尾部(或者第二个 - -last节点,如果它没有双重链接).遗憾的是,虽然我找不到任何与Java中链接列表的底层实现相关的信息,但很难说链接列表是否真的要走了......

这让我想到了我的问题.对于我打算做什么,Java中Queue接口的最佳实现是什么？(我不想编辑甚至访问队列的头部和尾部以外的任何东西 - 我不希望做任何类型的重新排列或任何事情.另一方面,我打算做很多推动和弹出,队列将大大改变大小,因此预分配将是低效的)

Answer 1

.getFirst()似乎还有一个方法,LinkedList是一个双向链表,这对于队列数据结构(FIFO)是有益的.它保持头/尾参考,你可以通过.getLast()和.push(E e).

Answer 2

如果你使用LinkedList要小心.如果你这样使用它:

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

然后你可以违反队列定义,因为可以删除除第一个之外的其他元素(LinkedList中有这样的方法).

但如果你像这样使用它:

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

它应该没问题,因为这是向用户提出的,插入只应出现在后面,而删除只发生在前面.

您可以通过将LinkedList类扩展到PureQueue类来克服Queue接口的有缺陷的实现,该类会抛出任何有问题的方法的UnsupportedOperationException.或者你可以用只有一个字段是类型的LinkedList对象,列表产生PureQueue采取与aggreagation办法,唯一的方法将是一个默认的构造函数,一个拷贝构造函数,isEmpty(),size(),add(E element),remove(),和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

在 Java 中实现 Stack 和 Queue 时，最好使用 ArrayDeque 而不是 LinkedList。当用作堆栈时，ArrayDeque 可能比 Stack 接口更快（而 Stack 是线程安全的），当用作队列时比 LinkedList 更快。看看这个链接Use ArrayDeque 而不是 LinkedList 或 Stack。

Answer 4

查看Deque接口,该接口提供两端的插入/移除.LinkedList实现了该接口(如上所述),但是为了您的使用,ArrayDeque可能更好 - 您不会为每个节点承担持续对象分配的成本.然后,您使用哪种实现可能无关紧要.

普通的多态性良好发挥作用:针对Deque接口而不是任何特定实现的写作的美妙之处在于,您可以非常轻松地切换实现以测试哪一个最佳.只需更改其中的行,new其余代码保持不变.