Java Queue的最佳实现? [英] Best implementation of Java Queue?

问题描述

我正在(使用Java)研究一种递归图像处理算法，该算法从中心点向外遍历图像的像素.

I am working (in Java) on a recursive image processing algorithm that recursively traverses the pixels of the image, outwards from a center point.

不幸的是，这导致堆栈溢出.因此，我决定切换到基于队列的算法.

Unfortunately, that causes a Stack Overflow. So I have decided to switch to a Queue-based algorithm.

现在，这一切都很好，但考虑到以下事实:它的队列将在非常短的时间内分析成千上万个像素，同时不断弹出并推动，而不会保持可预测的状态(它可能介于长度为100和20000)，则队列实现需要具有显着的快速弹出和推送功能.

Now, this is all fine and dandy- but considering the fact that its queue will be analyzing THOUSANDS of pixels in a very short amount of time, while constantly popping and pushing, WITHOUT maintaining a predictable state (It could be anywhere between length 100, and 20000), the queue implementation needs to have significantly fast popping and pushing abilities.

由于链表可以将元素推入自身而无需重新排列列表中的任何其他内容，因此它似乎很有吸引力，但是为了使其足够快，需要轻松访问其头部和尾部(或如果不是双重链接，则倒数第二个节点).可悲的是，我找不到与Java中链表的底层实现相关的任何信息，因此很难说链表是否真的是要走的路...

A linked list seems attractive due to its ability to push elements onto itself without rearranging anything else in the list, but in order for it to be fast enough, it would need easy access to both its head, AND its tail (or second-to-last node if it were not doubly-linked). Sadly, I cannot find any information related to the underlying implementation of linked lists in Java, so it's hard to say if a linked list is really the way to go...

这使我想到了我的问题.对于我打算做的事情，用Java在Queue接口中最好的实现是什么?(除了队列的首尾，我不希望编辑甚至访问任何东西-我不希望进行任何形式的重排或任何其他事情.另一方面，我确实想做很多事情然后弹出，队列将改变大小很多，因此预分配效率不高)

This brings me to my question. What would be the best implementation of the Queue interface in Java for what I intend to do? (I do not wish to edit or even access anything other than the head and tail of the queue -- I do not wish to do any sort of rearranging, or anything. On the flip side, I DO intend to do a lot of pushing and popping, and the queue will be changing size quite a bit, so preallocating would be inefficient)

推荐答案

LinkedList 似乎还有一段路要走，LinkedList是一个双向链接列表，对队列数据结构(FIFO)很有用.

LinkedList seems to a way to go, LinkedList is a doubly linked list, which is good for a Queue data structure (FIFO).

它维护对Head和Tail元素的引用，您可以分别通过 .getFirst()和 .getLast()获得这些引用.

It maintains references to the Head and Tail elements, which you can get by .getFirst() and .getLast() respectively.

您还可以使用 .add(E e)将元素添加到队列的末尾，并使用 .remove()出队并检索其头部(第一个元素).

You can also use .add(E e) to append an element to the end of the queue and .remove() to dequeue and retrieve the head (first element) of the queue.

这篇关于Java Queue的最佳实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！