Нужна очередь FIFO внутри одного потока. Что выбрать по умолчанию?

LinkedList действительно реализует Deque, но платит объектом-узлом за каждый элемент и разбросанностью по куче. ArrayDeque хранит элементы в кольцевом массиве, поэтому добавление и снятие с обоих концов константны и дружелюбны к кэшу. ArrayList для очереди не годится: удаление из начала сдвигает весь хвост. PriorityQueue — это куча, она выдаёт элементы по приоритету, а не в порядке поступления, и порядок её итератора вообще не определён. Ограничения ArrayDeque стоит знать: он не допускает null-элементов и не является потокобезопасным — для обмена между потоками берут реализации BlockingQueue.