Премиум

Очередь

Базовый Algorithms
≈ 1 мин чтения

Первым пришёл — первым вышел

Очередь работает по принципу FIFO (First In, First Out): элементы извлекаются в том же порядке, в котором были добавлены. Добавление происходит в хвост, а чтение и удаление — из головы. 

Deque<String> queue = new ArrayDeque<>();

queue.addLast("A");
queue.addLast("B");
queue.addLast("C");

String first = queue.peekFirst(); // A
String removed = queue.removeFirst(); // A

После удаления A первым становится B. Для ArrayDeque добавление в хвост и удаление из головы выполняются за O(1) амортизированно.

Когда очередь подходит задаче

Очередь нужна там, где более ранний элемент должен получить обработку раньше более позднего. Например, если алгоритм постепенно добавляет новые состояния и обязан обработать их в порядке обнаружения, очередь естественно сохраняет этот порядок без ручного сдвига элементов массива.

Главное отличие от стека — не набор данных, а правило извлечения. Один и тот же набор значений даст другой порядок обработки, если заменить FIFO на LIFO, а значит может полностью изменить поведение алгоритма.

Не реализуй очередь удалением первого элемента из обычного массива. Постоянные сдвиги оставшихся элементов превращают удаление в O(n). Deque хранит границы структуры без таких сдвигов.
Назад Далее