Enqueue

Enqueue — это операция добавления нового элемента в конец очереди (queue). В информатике и программировании enqueue является одной из двух базовых операций над структурой данных «очередь», работающей по принципу FIFO (First In, First Out — «первым пришёл — первым вышел»). Операция enqueue противопоставляется операции dequeue (извлечение элемента из начала очереди).

Определение и принцип работы

Очередь — это абстрактный тип данных (АТД), представляющий собой упорядоченную коллекцию элементов, в которой добавление новых элементов происходит только в один конец (называемый хвостом, tail или rear), а удаление — только с другого конца (называемого головой, head или front). Операция enqueue реализует именно добавление: она принимает элемент и помещает его в конец очереди, после чего очередь увеличивается на один элемент.

Принцип FIFO, лежащий в основе очереди, означает, что элемент, добавленный первым (enqueue), будет извлечён первым (dequeue). Например, если в пустую очередь последовательно выполнить enqueue(A), enqueue(B), enqueue(C), то после dequeue будет получен элемент A, затем B, затем C. Операция enqueue не изменяет порядок уже находящихся в очереди элементов.

Реализация

Операция enqueue может быть реализована различными способами в зависимости от выбранной структуры данных для хранения очереди. Наиболее распространённые реализации:

Массив (циклический буфер)

При реализации очереди на основе массива фиксированного размера enqueue выполняется следующим образом:

• Проверяется, не заполнена ли очередь (не достигнут ли предел ёмкости).
• Если очередь не заполнена, элемент записывается в позицию, соответствующую текущему индексу хвоста.
• Индекс хвоста увеличивается на единицу (по модулю размера массива, если используется циклический буфер).

В случае циклического буфера (кольцевой очереди) enqueue может быть выполнена за O(1) (константное время), так как не требует сдвига элементов. Однако при превышении ёмкости массива требуется либо перераспределение памяти (создание нового массива большего размера и копирование всех элементов), либо возврат ошибки.

Связный список

При реализации очереди на основе односвязного или двусвязного списка enqueue выполняется путём:

• Создания нового узла (node), содержащего добавляемый элемент.
• Присоединения этого узла к концу списка (если список не пуст, указатель next последнего узла устанавливается на новый узел; если список пуст, новый узел становится и головой, и хвостом).
• Обновления указателя на хвост (tail).

Операция enqueue в связном списке также выполняется за O(1), так как не требует обхода всего списка (при условии, что хранится указатель на хвост). Память выделяется динамически, что позволяет очереди расти без ограничения на фиксированный размер (в пределах доступной оперативной памяти).

Встроенные реализации в языках программирования

Многие языки программирования предоставляют встроенные структуры данных, поддерживающие enqueue:

• C++: std::queue (метод push()).
• Java: java.util.Queue (метод add() или offer()).
• Python: collections.deque (метод append()) или queue.Queue (метод put()).
• JavaScript: массивы (метод push()) или специализированные библиотеки.
• C#: System.Collections.Generic.Queue<T> (метод Enqueue()).

Применение

Операция enqueue используется повсеместно в программных системах, где требуется организовать обработку данных в порядке их поступления:

Обработка задач и планирование

• Планировщики процессов в операционных системах: задачи помещаются в очередь готовых к выполнению процессов (ready queue) с помощью enqueue, а затем извлекаются планировщиком.
• Очереди заданий (job queues) в системах пакетной обработки, например, в HPC-кластерах или системах непрерывной интеграции (CI/CD).
• Пул потоков (thread pool): задачи, поступающие на выполнение, помещаются в очередь (enqueue) и затем распределяются между свободными рабочими потоками.

Сетевые и коммуникационные протоколы

• Буферизация пакетов в сетевых устройствах (маршрутизаторах, коммутаторах): входящие пакеты помещаются в очередь (enqueue) для последующей обработки или передачи.
• Очереди сообщений (message queues) в распределённых системах: сообщения от отправителей помещаются в очередь (enqueue) и затем извлекаются получателями. Примеры: RabbitMQ, Apache Kafka, Amazon SQS.
• Очереди запросов в веб-серверах: HTTP-запросы от клиентов помещаются в очередь (enqueue) для обработки серверными потоками.

Пользовательские интерфейсы и события

• Очереди событий (event queues) в графических интерфейсах пользователя (GUI): действия пользователя (клики, нажатия клавиш) помещаются в очередь (enqueue) и затем обрабатываются циклом обработки событий.
• Очереди анимаций или команд в игровых движках: действия, запланированные на выполнение, помещаются в очередь (enqueue).

Алгоритмы и структуры данных

• Поиск в ширину (BFS): при обходе графа или дерева вершины помещаются в очередь (enqueue) для последующего посещения.
• Очереди приоритетов (priority queues): хотя принцип FIFO не соблюдается, операция добавления элемента (часто называемая insert или push) аналогична enqueue, но с учётом приоритета.

Сравнение с другими операциями

Ограничения и особенности

• Ограничение по ёмкости: при реализации на массиве фиксированного размера enqueue может завершиться ошибкой переполнения (overflow), если очередь заполнена. В динамических реализациях (связный список, динамический массив) это ограничение отсутствует, но может возникнуть нехватка памяти.
• Потокобезопасность: в многопоточных средах операция enqueue должна быть синхронизирована, чтобы избежать состояния гонки (race condition). Для этого используются мьютексы, семафоры или lock-free структуры данных.
• Блокирующие и неблокирующие очереди: в некоторых реализациях (например, java.util.concurrent.BlockingQueue) enqueue может блокировать поток, если очередь заполнена (ограниченная ёмкость), до освобождения места. В неблокирующих очередях enqueue возвращает ошибку или немедленно завершается.

Историческая справка

Понятие очереди как структуры данных восходит к ранним дням программирования и теории алгоритмов. Термин «enqueue» (от англ. «en-» — приставка, означающая «помещать внутрь», и «queue» — очередь) вошёл в обиход вместе с формализацией АТД в 1960-х — 1970-х годах. Одним из первых языков, где очередь была реализована как встроенный тип, стал Simula (1967). Впоследствии очередь и операция enqueue стали стандартными компонентами библиотек практически всех языков программирования.

Интересные факты

• В некоторых языках (например, в Python) операция enqueue для collections.deque называется append(), а не enqueue(), что может вызывать путаницу у начинающих.
• В системах реального времени (real-time systems) enqueue должна выполняться за строго детерминированное время, поэтому часто используются циклические буферы фиксированного размера.
• В контексте очередей сообщений (например, RabbitMQ) enqueue может быть транзакционной: если операция завершается неудачно, сообщение не добавляется, и состояние очереди не изменяется.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание, 2009.
• Ахо А., Хопкрофт Дж., Ульман Дж. «Структуры данных и алгоритмы» (Data Structures and Algorithms), 1983.
• Документация по стандартной библиотеке C++: std::queue.
• Документация Java: java.util.Queue и java.util.concurrent.BlockingQueue.
• Документация Python: collections.deque и queue.Queue.
• Таненбаум Э., Бос Х. «Современные операционные системы» (Modern Operating Systems), 4-е издание, 2014.