Java队列的最佳实现方式是什么？

Question

我正在使用Java编写递归图像处理算法，该算法从中心点开始递归遍历图像像素。

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

现在，这都很好 - 但考虑到它的队列会在非常短的时间内分析数千个像素，同时不断地弹出和推入，而没有维护可预测的状态（它可能在长度100到20000之间的任何位置），队列实现需要具有显着快速的弹出和推入能力。

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

这就带来了我的问题。对于我打算做的事情，Java中的Queue接口的最佳实现是什么？（我不想编辑甚至访问除队列的头部和尾部之外的任何内容 - 我不想进行任何形式的重新排列或其他操作。另一方面，我确实打算大量进行推入和弹出，并且队列将发生相当大的变化，因此预先分配资源将是低效的）

- Georges Oates Larsen

---

也许你需要退一步，思考一下是否有比逐个将成千上万的像素推入数据结构更好的方法（如果这确实是你正在做的事情）。 - Thilo

这是一个斑点检测算法，其思想是从斑点上的一个点开始向外遍历到斑点的边缘。我不认为还有其他（简单）的方法来做到这一点。此外，队列只存储感兴趣的点--它实际上并没有将像素存储在队列中，队列主要只是一种跟踪位置的方式。类似于许多路径查找算法。 - Georges Oates Larsen

Answer 1

使用：

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

你可以使用 .offer(E e) 在队列的末尾添加元素，使用 .poll() 函数出队并检索队头（第一个元素）。 Java 定义了接口 Queue，LinkedList 提供了一种实现方式。 同时它还维护了对头和队尾元素的引用，你可以分别使用 .getFirst() 和 .getLast() 获取它们。

感谢 @Snicolas 建议使用队列接口。

- didxga

---

我更倾向于使用由LinkedList实现的Queue方法：使用add进行入队操作，使用poll进行出队操作。 - Snicolas

我的回答涉及到这个问题，请看下面。不建议使用LinkedList，而是将其实例化为Queue接口...请看下面。 - azec-pdx

Answer 2

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

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

那么你可以违反队列的定义，因为LinkedList中有一些方法可以删除除第一个元素之外的其他元素。

但是如果你像这样使用它：

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

这应该没问题，因为它向用户说明插入只能在后面进行，删除只能在前面进行。

您可以通过将LinkedList类扩展到PureQueue类来克服队列接口的缺陷实现，以抛出任何有问题方法的UnsupportedOperationException异常。或者你可以采用聚合的方式，创建一个PureQueue，其中仅有一个字段是类型为LinkedList对象的list，并且唯一的方法将是默认构造函数、复制构造函数、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()

- azec-pdx

Answer 3

在Java中实现堆栈和队列时，建议使用ArrayDeque而不是LinkedList。当用作堆栈时，ArrayDeque比Stack接口（尽管Stack线程安全）更快，并且在用作队列时比LinkedList更快。请参阅此链接使用ArrayDeque替代LinkedList或Stack。

- Kehe CAI

Answer 4

请查看Deque接口，它提供了两端插入/删除的功能。 LinkedList实现了该接口（如上所述），但是对于您的使用，ArrayDeque可能更好--您不必为每个节点承担常量对象分配的成本。 然而，使用哪种实现可能并不重要。

正常的多态性发挥作用：针对Deque接口编写代码的好处是，您可以非常容易地切换实现以测试哪种实现效果最佳。 只需更改包含“new”的行，其余代码保持不变即可。

- yshavit

Answer 5

如果你知道队列中可能存在的最大数量，循环缓冲区比链表更快，因为链表会为队列中的每个项创建一个对象（链接）。

- Alexei Kaigorodov

Answer 6

我认为你可以提出一个类似的实现。

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;
      }
   }
}

- Grigor Nazaryan

---

双端队列操作在最坏情况下需要 O(n) 的时间，而队列数据结构应该在插入和删除时花费常数时间。这是一个天真的队列实现，请避免使用它。 - user1613360

你的双向队列方法为什么返回Node<T>而不是T？ - Zack Zatkin-Gold

如果这个实现了java.util.Queue接口就太好了。 - byxor

只需要进行一个小的更正，dequeue方法应该返回一个'T'。Node是队列的内部实现，不应该在队列实现之外可用。 - Dinesh Kumar

Answer 7

然而，如果您仍然想使用递归算法，您可以将其更改为"尾递归"，这可能会在JVM中进行优化以避免堆栈溢出。

- jaguililla

---

是的，你说得对，尾递归将克服堆栈溢出错误。我知道像Scala这样的语言本身支持尾递归来进行优化。然而，我怀疑Java是否不支持尾递归。如果我错了，请纠正我。 - Madhawa Gunasekara

JVM可以通过特殊的操作码支持更通用的功能，而Java编译器可以在相当受限制的条件下直接实现它。有一个愿望清单项目，但过去从未实际实现过，尽管它可能在未来实现。此外，您不应该建议依赖“可能存在”的优化，特别是如果优化的存在/不存在将使程序工作或崩溃。 - toolforger

Answer 8

第一个和最后一个节点的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;
    }
}

- skynet skynet

Answer 9

这是使用迭代器和可迭代接口实现的队列。

当队列满时，队列大小会增加。 队列接口。

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++];
        }
    }

}

- Vpn_talent