Java中的快速队列
我正在寻找Java中的快速queue实现。 我看到LinkedList实现了Queue接口，但它只能和LinkedList一样快吗？ 有没有办法让队列更快，特别是对于add （我只需要poll ， add和检查为empty ）。 我可能还需要一个PriorityQueue但还没有。
我看到LinkedList实现了Queue接口，但它只能和LinkedList一样快吗？
对于源代码而言，LinkedList对于Queue.add，Queue.poll和Queue.peek操作是O（1）。
我希望这个足够快。
如果要访问队列的多个线程，请考虑使用ArrayBlockingQueue 。 否则看看ArrayDeque 。 从ArrayDeque API：
当用作堆栈时，此类可能比Stack快，并且在用作队列时比LinkedList更快。
具体而言，如果现有arrays具有足够的容量，则基于arrays的队列实现减少了调整底层arrays大小的需要，从而使得对队列的添加通常比LinkedList更快。 请注意， ArrayBlockingQueue是一个有界实现，而ArrayDeque将根据需要resize。
另一方面， LinkedList通常会提供更紧凑的表示，特别是在队列增长和缩小的情况下。 例如，如果向ArrayDeque添加了10,000,000个元素，然后删除了9,999,999个元素，则底层数组的长度仍为10,000,000，而LinkedList不会遇到此问题。
实际上，对于非阻塞队列的单线程访问，我倾向于使用LinkedList 。 我认为性能差异是如此可以忽略不计，你无论如何都不会注意到差异。
如果链接列表的性能确实是一个问题，则另一种方法是在数组中实现“循环队列”，即在添加和删除条目时开始和结束点移动的队列。 如果你关心，我可以提供更多细节。 当我使用没有集合库的语言时，这就是我总是实现队列的方式，因为它比链表更容易编写，而且速度更快。 但是对于内置的集合，在特殊情况下编写和调试我自己的集合的努力在99％的时间里都不值得给它带来麻烦：当它已经编写完成时，我可以用不同的方式写出它比我更快的方式以Java的方式重写它几乎是一个无关紧要的事实。 任何性能提升都可能太小而不值得麻烦。 我对现有的集合进行子类型化以获得我现在需要的特殊行为，但是我很难想到我最后一次从头开始写一个。
您可能需要查看引入GapList http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list 。 这个新的列表实现结合了ArrayList和LinkedList的优点。
因此它实现了Deque接口，但也可以像上面提到的ArrayDeque那样进行ArrayDeque 。 此外，您还可以免费获得List界面的所有可能性。
从具有“C / C ++喜欢”态度和固定大小的非常简单的旋转队列实现开始。
class SimpleQueue { 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 s = new SimpleQueue (); 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()); } }
然后改进它。