Queue

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

Основные принципы и операции

Queue реализует дисциплину обслуживания FIFO, аналогичную очереди людей в магазине: первый вошедший обслуживается первым. Основные операции, поддерживаемые очередью, включают:

• Enqueue (вставка) — добавление элемента в конец очереди.
• Dequeue (удаление) — извлечение элемента из начала очереди с его удалением.
• Front (или Peek) — просмотр первого элемента без его удаления.
• IsEmpty — проверка, пуста ли очередь.
• Size — получение количества элементов в очереди.

В отличие от стека (LIFO), где доступен только последний добавленный элемент, queue обеспечивает доступ к самому старому элементу. Эта особенность делает её незаменимой для задач, где требуется обработка данных в порядке их поступления.

Реализация

Queue может быть реализована различными способами в зависимости от языка программирования и требований к производительности.

На основе массива

Реализация с использованием массива (или списка) проста, но имеет ограничения. При добавлении и удалении элементов может потребоваться сдвиг всех остальных элементов, что приводит к временной сложности O(n) для операции dequeue. Для устранения этого недостатка применяется кольцевой буфер (circular buffer), где начало и конец очереди «замыкаются» в кольцо, а индексы перемещаются по модулю длины массива. Это позволяет достичь O(1) для обеих основных операций.

На основе связного списка

Очередь на основе односвязного или двусвязного списка лишена проблемы сдвига. Каждый элемент (узел) содержит данные и указатель на следующий элемент. Дополнительные указатели на голову (начало) и хвост (конец) списка позволяют выполнять enqueue и dequeue за O(1). Недостатком является дополнительный расход памяти на хранение указателей.

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

Большинство современных языков программирования предоставляют встроенные или библиотечные реализации очередей:

• C++: std::queue (адаптер контейнера, по умолчанию на основе std::deque).
• Java: java.util.Queue (интерфейс), java.util.LinkedList, java.util.ArrayDeque, java.util.concurrent.ConcurrentLinkedQueue.
• Python: collections.deque (двусторонняя очередь, оптимизированная для быстрых добавлений и извлечений с обоих концов), queue.Queue (потокобезопасная очередь).
• C#: System.Collections.Generic.Queue<T>.
• JavaScript: Массивы с методами push() и shift(), хотя shift() имеет сложность O(n). Для эффективной реализации часто используют LinkedList или библиотечные структуры.

Виды очередей

Помимо классической FIFO-очереди, существуют её модификации, адаптированные для различных задач.

Двусторонняя очередь (Deque)

Deque (Double-Ended Queue) позволяет добавлять и удалять элементы как с начала, так и с конца очереди. Она объединяет возможности стека и очереди. Реализуется обычно с помощью кольцевого буфера или двусвязного списка. Deque используется в алгоритмах, требующих двустороннего доступа, например, в реализации скользящего окна или в некоторых алгоритмах на графах.

Приоритетная очередь (Priority Queue)

В приоритетной очереди каждый элемент имеет приоритет, и элемент с наивысшим приоритетом извлекается первым, независимо от времени его добавления. Если два элемента имеют одинаковый приоритет, порядок их извлечения может быть произвольным или определяться дополнительными правилами (например, временем поступления). Приоритетная очередь обычно реализуется на основе кучи (heap), что обеспечивает временную сложность O(log n) для вставки и извлечения. Она широко применяется в алгоритмах, таких как алгоритм Дейкстры, алгоритм Хаффмана и планирование задач операционных систем.

Круговая очередь (Circular Queue)

Круговая очередь — это реализация очереди на массиве фиксированного размера, где конец очереди «замыкается» на её начало. Это позволяет эффективно использовать память, избегая сдвига элементов. При достижении конца массива указатель хвоста перемещается в начало. Круговые очереди часто применяются в буферах данных, например, в кольцевых буферах аудио- и видеопотоков.

Блокирующая очередь (Blocking Queue)

Блокирующая очередь — это потокобезопасная очередь, которая блокирует поток, пытающийся извлечь элемент из пустой очереди, или добавить элемент в полную очередь (если задан максимальный размер). Она используется в многопоточных приложениях для организации взаимодействия между потоками (модель «производитель-потребитель»). В Java это java.util.concurrent.BlockingQueue, в Python — queue.Queue.

Применение

Очереди являются одной из наиболее широко используемых структур данных в информатике.

В операционных системах

• Планирование процессов: Очереди готовых к выполнению процессов (ready queue) и очереди заблокированных процессов. Планировщик ОС выбирает следующий процесс из очереди в соответствии с алгоритмом планирования (FIFO, Round Robin, приоритетное планирование).
• Обработка прерываний: Прерывания от устройств ставятся в очередь и обрабатываются последовательно.
• Управление вводом-выводом: Запросы к диску или другим устройствам организуются в очереди для оптимизации доступа.

В компьютерных сетях

• Буферизация пакетов: Маршрутизаторы и коммутаторы используют очереди для временного хранения пакетов, ожидающих передачи. Алгоритмы управления очередями (например, RED — Random Early Detection) предотвращают перегрузку сети.
• Очереди сообщений: В системах обмена сообщениями (например, RabbitMQ, Apache Kafka, Redis Streams) сообщения помещаются в очередь и обрабатываются потребителями. Это основа асинхронной архитектуры микросервисов.

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

• Поиск в ширину (BFS): BFS в графах использует очередь для обхода вершин по уровням. Вершина помещается в очередь, затем извлекается, и все её непосещённые соседи добавляются в очередь.
• Обработка деревьев: Обход дерева в ширину (level-order traversal) также использует очередь.
• Алгоритм Дейкстры: Использует приоритетную очередь для поиска кратчайших путей во взвешенном графе.

В веб-разработке и приложениях

• Обработка задач (Task Queue): Фоновые задачи (отправка email, генерация отчётов, обработка изображений) ставятся в очередь и выполняются рабочими процессами (workers). Это позволяет разгрузить основной сервер и повысить отзывчивость приложения.
• Очереди запросов: Веб-серверы могут ставить входящие запросы в очередь, если количество одновременных подключений превышает возможности обработки.
• Кэширование: Алгоритмы вытеснения из кэша, такие как FIFO, напрямую используют очередь.

В повседневной жизни

• Очереди в магазинах, банках, аэропортах — классический пример FIFO.
• Печать документов: Задания на печать ставятся в очередь принтера и выполняются в порядке поступления.
• Call-центры: Звонки клиентов помещаются в очередь ожидания и обрабатываются по мере освобождения операторов.

Критика и ограничения

Хотя queue является мощной и простой структурой, она имеет ограничения. Основной недостаток — строгий порядок FIFO, который не всегда оптимален. В системах реального времени или при наличии срочных задач требуется приоритетная обработка, что приводит к использованию приоритетных очередей. Кроме того, реализация на основе массива фиксированного размера может привести к переполнению (overflow), если не предусмотрен механизм динамического расширения. В многопоточных средах требуется синхронизация доступа к очереди, что может снижать производительность.

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

• Термин «queue» происходит от французского слова, означающего «хвост».
• В некоторых языках программирования (например, в языке Go) каналы (channels) реализуют концепцию очереди для передачи данных между горутинами.
• Алгоритм «кольцевого буфера» (circular buffer) был впервые описан в 1950-х годах для использования в ранних компьютерах с ограниченной памятью.
• Очередь является одной из структур данных, обязательных для изучения в рамках курса «Структуры данных и алгоритмы» в большинстве университетов мира.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик Р. Фундаментальные алгоритмы на C++. — СПб.: ДиаСофт, 2002.
• Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — М.: Вильямс, 2018.
• Документация языка Python: модуль queue — стандартная библиотека.
• Документация языка Java: интерфейс java.util.Queue — Java Platform SE 8.
• Документация языка C++: std::queue — cppreference.com.