Java中的快速队列

Question

我在寻找一种Java中的快速队列实现。我看到LinkedList实现了Queue接口，但它只能像一个LinkedList一样快吗？有没有一种方法可以拥有一个更快的队列，特别是对于add操作（我只需要poll，add和检查是否empty）。未来我可能还需要PriorityQueue，但现在还不需要。

- Eqbal

---

你已经验证过LinkedList不够快吗？在链表中添加应该很快... - Sam Holder

链表不够快？你尝试过自己编写代码来避免链表的瓶颈（无论是什么）吗？ - FrustratedWithFormsDesigner

Answer 1

如果多个线程将访问队列，则考虑使用ArrayBlockingQueue。否则，可以查看ArrayDeque。从ArrayDeque API中了解到：

此类作为堆栈使用时，可能比Stack更快；作为队列使用时，可能比LinkedList更快。

具体而言，基于数组的队列实现减少了对底层数组进行调整大小的需求，因此通常比LinkedList更快地向队列添加元素。请注意，ArrayBlockingQueue是有界实现，而ArrayDeque会根据需要调整大小。

另一方面，LinkedList通常提供更紧凑的表示，特别是在队列增长和缩小大量的情况下。例如，如果您向ArrayDeque添加1000万个元素，然后删除9999999个元素，则底层数组仍为长度1000万，而LinkedList不会遇到此问题。

实际上，在单线程访问非阻塞队列时，我倾向于使用LinkedList。我想性能差异微不足道，您可能不会注意到差异。

- Adamski

---

LinkedBlockingQueue 实际上比 ArrayBlockingQueue 更快。因此，如果您正在使用阻塞的并发队列，请使用 LinkedBlockingQueue。否则，使用 ConcurrentLinkedQueue 比这两个都更快。 - John Vint

@JohnVint，你有ArrayBlockingQueue比LinkedBlockingQueue慢的一些来源吗？由于支持数组在对象的整个生命周期内不会调整大小，因此ArrayBlockingQueue不应该是更快的吗？ - Pacerier

@Adamski，ArrayDeque在current_element_amt < 0.5 * capacity时自动缩小其大小，这一点你不知道吗？ - Pacerier

@Pacerier 我得稍后查一下，但这在《Java并发编程实践》一书中有提到。它指出，由于允许队列上的两个并行操作，因此可以更好地执行。 - John Vint

这应该是被接受的答案。我对一个算法进行了基准测试，并发现在我进行约 3500 万次添加和删除操作时，ArrayDeque 比 LinkedList 快约 25%。 - arviman

Answer 2

我看到LinkedList实现了Queue接口，但它的速度只有LinkedList快是吗？根据源代码分析，LinkedList对于Queue.add、Queue.poll和Queue.peek操作都是O（1）。希望这速度足够快了。

- Noel Ang

---

对于一个链表数据结构来说，这将是一项极其愚蠢的成就。 - Noel Ang

链表通常是O(n)的搜索，但如果你实际上将其用作队列，它永远不会出现。 - Graphics Noob

O(1)并不自动意味着它很快。链表可以是O(1)，但与其他O(1)方法相比仍可能非常慢。 - Pacerier

对Pacerier加一。使用插入和删除3500万个条目对队列进行基准测试，ArrayDeque比LinkedList快大约25%。 - arviman

@NoelAng 嗯，是的，人们总是可以添加一个单独的“列表结尾”指针来快速到达结尾，或者类似的东西。但我认为在正常的讨论中，如果有人说，“数据结构X在这个操作上提供O(n)的性能”，我们总是可以说，“不，那不是真的，因为具体的实现可能会提供一个特殊情况来处理它。”基本上按定义，具体的实现可以通过为某些特殊情况提供快捷方式来打破正常的性能规则。 - Jay

Answer 3

如果链表的性能真的是一个问题，那么一种替代方法是在数组中实现“循环队列”，即队列的起点和终点随着条目的添加和删除而移动。如果您感兴趣，我可以提供更多细节。当我使用没有集合库的语言时，这就是我始终实现队列的方式，因为它比链表更容易编写，速度更快。但是有了内置集合，为特殊情况编写和调试自己的集合的工作99％的时间都不值得麻烦：当已经编写好时，我可以以不同的方式编写它比我重新编写Java的方式更快几乎是无关紧要的事实。任何性能提升都可能太小而不值得麻烦。我会子类型化现有集合以获得我现在和以后需要的特殊行为，但我很难想到上一次从头开始编写它的时间。

- Jay

---

点赞，因为如果队列速度被证明是性能瓶颈的话，这是一个很好的替代方案。 - Merlyn Morgan-Graham

你所描述的已经在Java 6中添加了，它被称为java.util.ArrayDeque。 - Étienne Miret

Answer 4

您可以查看 https://dzone.com/articles/gaplist-lightning-fast-list，介绍了一个名为GapList的新列表实现。该实现结合了ArrayList和LinkedList的优点。

因此，它实现了Deque接口，并且还可以像上述的ArrayDeque一样进行预调整大小。此外，您还可以免费获得所有List接口的功能。获取地址：https://github.com/magicwerk/brownies-collections。

- Thomas Mauch

Answer 5

从具有“C/C++风格”和固定大小的非常简单的旋转队列实现开始。

class SimpleQueue<E>
{

int index   = 0;
int head    = 0;
int size    = 100;
int counter = 0;
E[] data    ;


@SuppressWarnings("unchecked")
SimpleQueue()
{
    data = (E[]) new Object[size];
}

public void add(E e)
{
    data[index]=e;
    index=(index+1)%size;
    counter++;
}

public E poll()
{
    E value = data[head];
    head=(head+1)%size;
    counter--;
    return value;
}

public boolean empty()
{ return counter==0; }

//Test
public static void main(String[] args)
{
    SimpleQueue<Integer> s = new SimpleQueue<Integer>();

    System.out.println(s.empty());

    for(int i=0; i< 10; i++)
        s.add(i);

    System.out.println(s.empty());

    for(int i=0; i<10; i++)
        System.out.print(s.poll()+",");

    System.out.println("\n"+s.empty());

}
}

然后改进它。

- Jan Cajthaml

---

ArrayDeque 是一个旋转队列。既然 Java SE 6 库中已经有了这个工具，为什么要重新发明轮子呢？ - ThePyroEagle