Очереди и стек: ArrayDeque и PriorityQueue

ArrayDeque: кольцевой буфер

ArrayDeque — двусторонняя очередь на основе массива с указателями head и tail, который при достижении границ «заворачивается» (кольцевой буфер). Добавление и снятие с обоих концов — амортизированно O(1), ёмкость — степень двойки для быстрого индекса по маске.

За счёт плотного массива у него отличная cache locality — он быстрее LinkedList и не создаёт мусорных узлов на каждый элемент. Null хранить нельзя: null используется как маркер пустоты.

Замена Stack и LinkedList

Как стек используют именно ArrayDeque (push/pop/peek), а не легаси-класс Stack: Stack наследует Vector и синхронизирован на каждой операции, что бессмысленно для локального стека и медленно.

Как очередь FIFO (offer/poll) ArrayDeque тоже предпочтительнее LinkedList по тем же причинам — память и кэш.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
int top = stack.pop(); // 2  — современная замена java.util.Stack

PriorityQueue: бинарная куча

PriorityQueue — это бинарная min-куча, хранящаяся в массиве: для узла с индексом i дети находятся в 2i+1 и 2i+2. Корень — минимальный (или экстремальный по Comparator) элемент.

offer и poll — O(log n) (просеивание вверх/вниз для восстановления свойства кучи), а peek — O(1). Порядок задаётся Comparable или Comparator.

Ловушка итерации кучи

Куча упорядочена лишь частично (родитель ≤ детей), поэтому итерация по PriorityQueue НЕ даёт отсортированный порядок — гарантирован только порядок извлечения через poll. Это частая ошибка: распечатать очередь и ждать сортировки.

PriorityQueue не потокобезопасна; для конкурентного варианта есть PriorityBlockingQueue.

Как отвечать на собеседовании

Скажите, что для стека/очереди современный выбор — ArrayDeque (кольцевой буфер, O(1), лучше кэш, замена Stack/LinkedList), а PriorityQueue — это бинарная куча в массиве с O(log n) на вставку/снятие и важной оговоркой: итерация не отсортирована.