Очередь (структура данных)

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

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

Над очередью определены следующие фундаментальные операции:

• Enqueue (добавление): помещает новый элемент в конец очереди.
• Dequeue (удаление): извлекает и удаляет элемент из начала очереди.
• Peek / Front (просмотр): возвращает значение элемента, находящегося в начале очереди, не удаляя его.
• IsEmpty (проверка на пустоту): возвращает логическое значение, указывающее, содержит ли очередь хотя бы один элемент.
• Size (размер): возвращает количество элементов, находящихся в очереди в данный момент.

История и происхождение

Понятие очереди как структуры данных возникло в ранние годы развития программирования, в первую очередь в связи с необходимостью организации буферизации данных и управления задачами в операционных системах. Одним из первых практических применений очередей стали алгоритмы планирования процессов, где они использовались для реализации дисциплины FIFO (First-Come, First-Served — «первым прибыл — первым обслужен»). Теоретическое обоснование и формализация очереди как абстрактного типа данных (ADT) были выполнены в рамках развития теории алгоритмов и структур данных в середине XX века, в частности в работах таких учёных, как Дональд Кнут.

Реализации

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

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

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

Преимущества:

• Простота реализации.
• Быстрый доступ к элементам по индексу (для операций, не предусмотренных стандартным ADT очереди).
• Эффективное использование кэш-памяти процессора (локальность данных).

Недостатки:

• Фиксированный размер при использовании статического массива (может потребоваться перераспределение памяти при переполнении).
• При реализации без кольцевого буфера операция Dequeue может требовать сдвига всех оставшихся элементов, что даёт временную сложность O(n).

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

Очередь может быть реализована с помощью односвязного списка, где каждый элемент (узел) содержит хранимые данные и указатель на следующий узел. Для эффективного выполнения операций Enqueue (добавление в конец) и Dequeue (удаление из начала) необходимо хранить два указателя: на голову (начало) и на хвост (конец) списка.

Преимущества:

• Динамический размер — очередь может расти по мере необходимости, не требуя предварительного выделения памяти.
• Операции Enqueue и Dequeue выполняются за время O(1) (константное время) при наличии указателей на оба конца.

Недостатки:

• Более сложная реализация и управление памятью (ручное выделение/освобождение узлов в языках без сборки мусора).
• Худшая локальность данных по сравнению с массивом, что может снижать производительность из-за кэш-промахов.
• Дополнительные затраты памяти на хранение указателей.

На основе двух стеков

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

Преимущества:

• Использование уже реализованного ADT стека, что упрощает разработку в некоторых языках программирования.
• Амортизированная временная сложность операций Enqueue и Dequeue составляет O(1).

Недостатки:

• В худшем случае операция Dequeue может потребовать O(n) времени (при переносе всех элементов из одного стека в другой).
• Требуется дополнительная память для хранения двух стеков.

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

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

Очередь с приоритетом

В очереди с приоритетом (Priority Queue) каждый элемент имеет ассоциированный с ним приоритет. Элементы извлекаются не в порядке поступления, а в порядке возрастания (или убывания) приоритета. Если два элемента имеют одинаковый приоритет, порядок их извлечения может быть произвольным или определяться дополнительными правилами (например, по времени поступления). Реализуется обычно на основе кучи (heap) или бинарного дерева поиска.

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

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

Циклическая очередь

Циклическая очередь (Circular Queue) — это реализация очереди на основе массива, в которой логически начало и конец очереди соединены, образуя кольцо. Это позволяет эффективно использовать память, не сдвигая элементы при удалении из начала. При достижении последней ячейки массива указатель хвоста переходит на первую ячейку, если она свободна.

Блокирующая очередь

Блокирующая очередь (Blocking Queue) — это очередь, используемая в многопоточных приложениях, которая поддерживает синхронизацию доступа. Если поток пытается извлечь элемент из пустой блокирующей очереди, он приостанавливается (блокируется) до тех пор, пока другой поток не добавит элемент. Аналогично, если поток пытается добавить элемент в полную очередь, он блокируется до освобождения места. Широко применяется в архитектурах «производитель-потребитель» (Producer-Consumer).

Применение

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

• Операционные системы: управление очередями процессов (планировщик задач), обработка прерываний, управление буферами ввода-вывода.
• Сетевые технологии: буферизация пакетов в маршрутизаторах и коммутаторах, управление очередями сообщений в системах обмена данными (например, RabbitMQ, Apache Kafka).
• Компьютерная графика и анимация: реализация очередей событий, обработка пользовательского ввода (например, очередь нажатий клавиш).
• Алгоритмы: поиск в ширину (BFS) в графах, алгоритм Дейкстры (с использованием очереди с приоритетом), алгоритм Беллмана-Форда (с использованием очереди для оптимизации).
• Веб-разработка: обработка HTTP-запросов на сервере, управление задачами в фоновых рабочих процессах (например, отправка электронных писем, генерация отчётов).
• Системы массового обслуживания: моделирование работы банков, магазинов, call-центров и других систем, где клиенты обслуживаются в порядке поступления.

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

• В некоторых языках программирования (например, C++) очередь является частью стандартной библиотеки шаблонов (STL) и реализована на основе дека (deque) по умолчанию, что обеспечивает хороший баланс производительности.
• Термин «FIFO» также используется для обозначения метода оценки стоимости запасов в бухгалтерском учёте, где первая поступившая партия товара считается первой проданной.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms)
• Кнут Д. «Искусство программирования» (The Art of Computer Programming)
• Седжвик Р. «Фундаментальные алгоритмы на C++» (Algorithms in C++)
• ISO/IEC 14882:2020 — Стандарт языка программирования C++ (раздел о контейнерах и адаптерах)
• Tanenbaum A., Bos H. «Современные операционные системы» (Modern Operating Systems)