Какой принцип FIFO реализует коллекция в Java

Что проверяют

Знаете ли вы иерархию очередей в Java Collections Framework и отличаете ли интерфейс от конкретной реализации. Следом спрашивают, чем ArrayDeque лучше LinkedList и какую очередь брать, если с ней работают несколько потоков.

Как отвечать

FIFO описывает интерфейс Queue: элементы добавляются в хвост, извлекаются из головы. Но порядок гарантирует реализация, а не интерфейс. Оговорите исключение: PriorityQueue тоже реализует Queue, но отдаёт элементы по приоритету, а не по времени добавления.

Реализации с порядком FIFO:

• ArrayDeque: кольцевой буфер на массиве, выбор по умолчанию для однопоточного кода. Быстрее LinkedList, не создаёт узел на каждый элемент, не принимает null;
• LinkedList: тоже реализует Deque, допускает null, но расходует больше памяти;
• ConcurrentLinkedQueue: неблокирующая потокобезопасная очередь на CAS;
• ArrayBlockingQueue и LinkedBlockingQueue: блокирующие очереди для схемы «производитель и потребитель». Методы put() и take() ждут, пока появится место или элемент.

У Queue каждая операция есть в двух вариантах:

• add() и offer(): добавление. При заполненной ограниченной очереди первый бросает IllegalStateException, второй возвращает false;
• remove() и poll(): извлечение из головы. На пустой очереди первый бросает NoSuchElementException, второй возвращает null;
• element() и peek(): просмотр головы без удаления, поведение на пустой очереди такое же.

Для LIFO берут тот же ArrayDeque с методами push() и pop(), а не устаревший Stack, который наследует синхронизированный Vector.

Где спотыкаются

Говорят, что любая реализация Queue работает по FIFO, и забывают про PriorityQueue. Причём её итератор не обходит элементы даже в порядке приоритета, упорядочен только результат poll().

Используют LinkedList как очередь по привычке и не могут объяснить, почему ArrayDeque быстрее: меньше объектов и нагрузки на сборщик мусора.

Берут ArrayDeque или LinkedList в многопоточном коде без синхронизации. Для передачи задач между потоками нужна BlockingQueue, иначе потребитель крутится в пустом цикле или ловит гонки.