我正在（在 Java 中）研究递归图像处理算法，该算法从中心点向外递归遍历图像的像素。
不幸的是，这会导致堆栈溢出。所以我决定切换到基于队列的算法。
现在，这一切都很好——但考虑到它的队列将在很短的时间内分析数千个像素，同时不断弹出和推送，而不保持可预测的状态（它可能在长度 100 之间，和 20000），队列实现需要具有显着的快速弹出和推送能力。
链表看起来很有吸引力，因为它能够将元素推送到自身而不重新排列列表中的任何其他内容，但为了使其足够快，它需要轻松访问其头部和尾部（或次要-last 节点，如果它不是双重链接的）。可悲的是，我找不到任何与 Java 中链表的底层实现相关的信息，所以很难说链表是否真的是要走的路……
这让我想到了我的问题。对于我打算做的事情，Java 中 Queue 接口的最佳实现是什么？（除了队列的头部和尾部之外，我不希望编辑甚至访问任何东西——我不希望进行任何类型的重新排列或任何事情。另一方面，我确实打算做很多推送和弹出，队列的大小会发生很大变化，因此预分配效率低下）
采用：
Queue<Object> queue = new LinkedList<>();
您可以使用.offer(E e)将元素附加到队列的末尾，以及.poll()出列和检索队列的头部（第一个元素）。
Java 定义了接口Queue，LinkedList提供了实现。
它还维护对 Head 和 Tail 元素的引用，您可以分别获取.getFirst()它们.getLast()。
感谢@Snicolas 建议队列接口
如果你使用 LinkedList 要小心。如果你像这样使用它：
LinkedList<String> queue = new LinkedList<String>();
那么您可以违反队列定义，因为可以删除除第一个之外的其他元素（LinkedList 中有这样的方法）。
但是如果你像这样使用它：
Queue<String> queue = new LinkedList<String>();
应该没问题，因为这是提醒用户，插入应该只发生在后面，而删除应该只发生在前面。
您可以通过将 LinkedList 类扩展为引发任何违规方法的 UnsupportedOperationException 的 PureQueue 类来克服 Queue 接口的缺陷实现。或者，您可以通过仅使用一个类型为 LinkedList 对象、列表的字段创建 PureQueue 来采用聚合方法，并且唯一的方法将是默认构造函数、复制构造函数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()
查看Deque接口，它提供了两端的插入/删除。LinkedList 实现了该接口（如上所述），但对于您的使用，ArrayDeque 可能会更好——您不会为每个节点产生常量对象分配的成本。再说一次，您使用哪种实现可能并不重要。
正常多态性的优点开始发挥作用：针对 Deque 接口而不是它的任何特定实现进行编写的美妙之处在于，您可以非常轻松地切换实现以测试哪个实现最佳。只需更改其中的行，new其余代码保持不变。
在 Java 中实现 Stack 和 Queue 时，最好使用 ArrayDeque 而不是 LinkedList。当用作堆栈时，ArrayDeque 可能比 Stack 接口（而 Stack 是线程安全的）快，而当用作队列时，它可能比 LinkedList 快。看看这个链接使用 ArrayDeque 而不是 LinkedList 或 Stack。
如果您知道队列中可能的项目数量的上限，则循环缓冲区比 LinkedList 更快，因为 LinkedList 为队列中的每个项目创建一个对象（链接）。
我认为您可以使用简单的类似实现
package DataStructures;
public class Queue<T> {
private Node<T> root;
public Queue(T value) {
root = new Node<T>(value);
}
public void enque(T value) {
Node<T> node = new Node<T>(value);
node.setNext(root);
root = node;
}
public Node<T> deque() {
Node<T> node = root;
Node<T> previous = null;
while(node.next() != null) {
previous = node;
node = node.next();
}
node = previous.next();
previous.setNext(null);
return node;
}
static class Node<T> {
private T value;
private Node<T> next;
public Node (T value) {
this.value = value;
}
public void setValue(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public void setNext(Node<T> next) {
this.next = next;
}
public Node<T> next() {
return next;
}
}
}
但是，如果您仍想使用递归算法，您可以将其更改为“尾递归”，这可能在 JVM 中进行了优化以避免堆栈溢出。
O(1) 访问第一个和最后一个节点。
class Queue {
private Node head;
private Node end;
public void enqueue(Integer data){
Node node = new Node(data);
if(this.end == null){
this.head = node;
this.end = this.head;
}
else {
this.end.setNext(node);
this.end = node;
}
}
public void dequeue (){
if (head == end){
end = null;
}
head = this.head.getNext();
}
@Override
public String toString() {
return head.getData().toString();
}
public String deepToString() {
StringBuilder res = new StringBuilder();
res.append(head.getData());
Node cur = head;
while (null != (cur = cur.getNext())){
res.append(" ");
res.append(cur.getData());
}
return res.toString();
}
}
class Node {
private Node next;
private Integer data;
Node(Integer i){
data = i;
}
public Integer getData() {
return data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
这是带有Iterator和Iterable接口的队列实现
队列大小会随着它变满而增加
队列接口
package com.practice.ds.queue;
import com.practice.ds.queue.exception.QueueException;
public interface QueueInterface<T> {
public boolean empty();
public void enqueue(T item);
public void dequeue() throws QueueException;
public T front() throws QueueException;
public void clear();
}
自定义异常类
package com.practice.ds.queue.exception;
public class QueueException extends Exception {
private static final long serialVersionUID = -884127093599336807L;
public QueueException() {
super();
}
public QueueException(String message) {
super(message);
}
public QueueException(Throwable e) {
super(e);
}
public QueueException(String message, Throwable e) {
super(message, e);
}
}
队列的实现
package com.practice.ds.queue;
import java.util.Iterator;
import com.practice.ds.queue.exception.QueueException;
public class Queue<T> implements QueueInterface<T>, Iterable<T> {
private static final int DEFAULT_CAPACITY = 10;
private int current = 0;
private int rear = 0;
private T[] queueArray = null;
private int capacity = 0;
@SuppressWarnings("unchecked")
public Queue() {
capacity = DEFAULT_CAPACITY;
queueArray = (T[]) new Object[DEFAULT_CAPACITY];
rear = 0;
current = 0;
}
@Override
public boolean empty() {
return capacity == current;
}
@Override
public void enqueue(T item) {
if(full())
ensureCapacity();
queueArray[current] = item;
current++;
}
@Override
public void dequeue() throws QueueException {
T dequeuedItem = front();
rear++;
System.out.println("Dequed Item is " + dequeuedItem);
}
@Override
public T front() throws QueueException {
return queueArray[rear];
}
@Override
public void clear() {
for (int i = 0; i < capacity; i++)
queueArray[i] = null;
current = 0;
rear = 0;
}
@SuppressWarnings("unchecked")
private void ensureCapacity() {
if (rear != 0) {
copyElements(queueArray);
} else {
capacity *= 2;
T[] tempQueueArray = (T[]) new Object[capacity];
copyElements(tempQueueArray);
}
current -= rear;
rear = 0;
}
private void copyElements(T[] array) {
for (int i = rear; i < current; i++)
array[i - rear] = queueArray[i];
queueArray = array;
}
@Override
public Iterator<T> iterator() {
return new QueueItearator<T>();
}
public boolean full() {
return current == capacity;
}
private class QueueItearator<T> implements Iterator<T> {
private int index = rear;
@Override
public boolean hasNext() {
return index < current;
}
@SuppressWarnings("unchecked")
@Override
public T next() {
return (T) queueArray[index++];
}
}
}