What is the fastest Java collection with the basic functionality of a Queue?

You can use a java.util.LinkedList - it's doubly-linked and cicrular, so adding to one end and taking from the other are O(1)

Whatever implementation you choose, refer to it by the Queue interface, so that you can easily change it if it turns out not to fit your case (if, of course, a queue is what you need in the first place)

Update: Colin's answer shows a benchmark that concludes that ArrayDeque is better. Both have O(1) operations, but LinkedList creates new objects (nodes), which slightly affect performance. Since both have O(1) I don't think it would be too wrong to choose LinkedList though.

ArrayDeque is best. See this benchmark, which comes from this blog post about the results of benchmarking this. ArrayDeque doesn't have the overhead of node allocations that LinkedList does nor the overhead of shifting the array contents left on remove that ArrayList has. In the benchmark, it performs about 3x as well as LinkedList for large queues and even slightly better than ArrayList for empty queues. For best performance, you'll probably want to give it an initial capacity large enough to hold the number of elements it's likely to hold at a time to avoid many resizes.

Between ArrayList and LinkedList, it seems that it depends on the average number of total elements the queue will contain at any given time and that LinkedList beats ArrayList starting at about 10 elements.