Best implementation of Java Queue?

Check out the Deque interface, which provides for insertions/removals at both ends. LinkedList implements that interface (as mentioned above), but for your use, an ArrayDeque may be better -- you won't incur the cost of constant object allocations for each node. Then again, it may not matter which implementation you use.

Normal polymoprhism goodness comes to play: the beauty of writing against the Deque interface, rather than any specific implementation of it, is that you can very easily switch implementations to test which one performs best. Just change the line with new in it, and the rest of the code stays the same.

If you use LinkedList be careful. If you use it like this:

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

then you can violate queue definition, because it is possible to remove other elements than first (there are such methods in LinkedList).

But if you use it like this:

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

it should be ok,as this is heads-up to users that insertions should occur only at the back and deletions only at the front.

You can overcome defective implementation of the Queue interface by extending the LinkedList class to a PureQueue class that throws UnsupportedOperationException of any of the offending methods. Or you can take approach with aggreagation by creating PureQueue with only one field which is type LinkedList object, list, and the only methods will be a default constructor, a copy constructor, isEmpty(), size(), add(E element), remove(), and element(). All those methods should be one-liners, as for example:

/**
* 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()

Use:

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

You can use .offer(E e) to append an element to the end of the queue and .poll() to dequeue and retrieve the head (first element) of the queue.

Java defined the interface Queue, the LinkedList provided an implementation.

It also maintains references to the Head and Tail elements, which you can get by .getFirst() and .getLast() respectively.

credit to @Snicolas for suggesting queue interface