ArrayDeque

ArrayDeque представляет обобщенную двунаправленную очередь.
Содержит методы для работы:
1. Как с очередью (addFirst(), addLast(), offer(), peekLast(), ...).
2. Как со стеком (push(), pop(), peek()).
3. Как с коллекцией (size(), isEmpty(), iterator(), toArray(), ...).

Операции добавления/удаления/получения из начала и конца очереди выполняются за конечное время О(1), при этом быстрее, чем у LinkedList. Это особенно хорошо видно на больших объёмах хранимых элементов.

Удаление элемента по значению производится итеративно за время О(n). Так что, если требуется удалять элементы, то рекомендуется использовать LinkedList.

ArrayDeque внутри себя хранит элементы в массиве типа Object (Object[] elements). Массив elements работает как циклический массив, в котором положение ячейки не фиксировано, она может быть началом, может быть концом, или где-нибудь в середине.

Очередь содержит индекс элемента, который будет удалён с помощью remove() или pop() (поле head), и индекс элемента, по которому будет добавлен новый элемент в конец с помощью addLast(E), add(E), или push(E) (поле tail).
ArrayDeque не допускает добавление null, т.к. некоторые его методы возвращают null когда очередь пуста. При попытке добавить null будет выброшен NullPointerException.
ArrayDeque не реализует интерфейс List, поэтому не имеет методов прямого доступа к элементам по индексу (get(), set()).
ArrayDeque не синхронизирован.