If you need to choose the best way to do something, use PriorityQueue. The infamous traveling salesman problem benefits from a priority queue. In that problem the have to find the best route to a destination, and there are many possibilities. A LinkedList is good if your doing many insertions or deletions.
There probably isn't a "best" implementation of anything, but have a look at the java.util.Queue interface, where there is a list of implementing classes. Some of them may have instructions about how to make a Queue thread-safe. There are comments about blocking queues in Queue, too.