Очередь FIFO

Очередь FIFO (от англ. first in, first out — «первым пришёл, первым ушёл») — это абстрактный тип данных, реализующий дисциплину обслуживания, при которой первый добавленный элемент извлекается раньше всех последующих. В информатике и смежных дисциплинах очередь FIFO является фундаментальной структурой данных, моделирующей принцип работы обычной очереди в реальной жизни: люди, стоящие первыми, обслуживаются первыми. Основные операции, поддерживаемые очередью, — это добавление элемента в конец (обычно называется enqueue, push или offer) и удаление элемента из начала (dequeue, pop или poll), при этом доступ к элементу в начале очереди (без удаления) также часто предусмотрен (peek или front).

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

Принцип FIFO как организационная модель существовал задолго до появления вычислительной техники. В торговле, логистике и бюрократии он использовался для упорядочивания обслуживания клиентов, обработки заказов и документооборота. С развитием компьютерных систем в середине XX века возникла необходимость в формальном описании и программной реализации этого принципа.

Одним из первых теоретических обоснований очередей как структур данных стало развитие теории массового обслуживания (теории очередей), заложенной Агнером Крарупом Эрлангом в начале 1900-х годов для анализа телефонных сетей. В программировании понятие очереди FIFO получило широкое распространение с появлением языков высокого уровня и операционных систем, где требовалось управлять потоками данных и задачами. В 1960-х годах очередь стала стандартной структурой в алгоритмах и библиотеках языков, таких как ALGOL, а затем и в языках C, Pascal и других.

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

Очередь FIFO характеризуется строгим порядком обработки элементов. В отличие от стека (LIFO — last in, first out), где последний добавленный элемент извлекается первым, в очереди порядок извлечения совпадает с порядком добавления.

Базовые операции

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

Дополнительные операции

В некоторых реализациях могут быть доступны операции очистки очереди (clear) или проверки переполнения (для очередей с фиксированным размером).

Реализации

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

На основе массива (кольцевой буфер)

Классический способ — использование массива фиксированного размера с двумя указателями: на начало (head) и конец (tail). При добавлении элемента указатель tail сдвигается вперёд, при удалении — head. Для эффективного использования памяти применяется кольцевой буфер, где при достижении конца массива указатели переходят на начало. Недостаток — фиксированный размер, требующий либо предварительного выделения памяти, либо перераспределения при переполнении.

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

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

На основе стека

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

В языках программирования

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

• C++: std::queue (адаптер контейнера по умолчанию на основе deque).
• Java: интерфейс Queue и его реализации, например LinkedList, ArrayDeque, PriorityQueue (последняя не является строго FIFO, так как использует приоритет).
• Python: collections.deque (двусторонняя очередь) и queue.Queue (потокобезопасная очередь).
• Go: пакет container/list для связного списка или использование среза.
• JavaScript: массивы с методами push и shift (хотя shift имеет O(n) для массивов), или специализированные структуры.

Применение

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

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

• Планирование процессов: многие алгоритмы планирования, такие как FCFS (First Come, First Served), используют очередь FIFO для организации порядка выполнения процессов.
• Управление вводом-выводом: очереди запросов к диску, принтеру или другим устройствам.
• Буферизация: очередь сообщений между процессами (IPC) или в каналах (pipes).

Сети и коммуникации

• Маршрутизация пакетов: в коммутаторах и маршрутизаторах пакеты часто обрабатываются в порядке поступления (FIFO-очереди).
• Очереди сообщений: в системах обмена сообщениями (например, RabbitMQ, Apache Kafka) для гарантии порядка доставки.
• TCP/IP: буферы приёма и передачи данных в протоколах транспортного уровня.

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

• Поиск в ширину (BFS): алгоритм обхода графа использует очередь для хранения вершин, подлежащих посещению.
• Кэширование: алгоритм вытеснения FIFO (первый вошёл — первый вышел) в кэшах, хотя он менее эффективен, чем LRU.
• Обработка событий: в графических интерфейсах и играх события (нажатия клавиш, движения мыши) помещаются в очередь и обрабатываются по порядку.

Производство и логистика

• Управление запасами: метод FIFO в бухгалтерском учёте и складской логистике предполагает, что товары, поступившие первыми, продаются или используются первыми.
• Производственные линии: конвейеры и сборочные линии часто работают по принципу FIFO.

Разновидности и расширения

На основе базовой очереди FIFO разработаны более сложные структуры:

• Двусторонняя очередь (deque): позволяет добавлять и удалять элементы как с начала, так и с конца.
• Приоритетная очередь: элементы извлекаются в порядке приоритета, а не времени поступления.
• Очередь с ограниченным размером (bounded queue): имеет фиксированную вместимость; при переполнении может блокировать добавление или отбрасывать элементы.
• Потокобезопасная очередь: обеспечивает корректную работу в многопоточных средах с использованием блокировок или неблокирующих алгоритмов (например, lock-free queue).
• Циклическая очередь: реализация на кольцевом буфере, позволяющая эффективно использовать память.

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

Несмотря на простоту и широкое применение, очередь FIFO имеет недостатки. В системах реального времени или при неравномерной нагрузке строгий порядок FIFO может приводить к «голоданию» задач с более высоким приоритетом, если они поступают позже. Поэтому в планировщиках операционных систем часто используются гибридные алгоритмы (например, многоуровневые очереди с обратной связью). В кэшировании FIFO уступает алгоритмам, учитывающим частоту или давность использования (LRU, LFU). Кроме того, при реализации на массиве фиксированного размера возможно переполнение, а при динамическом выделении — фрагментация памяти.

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

• Термин «FIFO» впервые появился в контексте бухгалтерского учёта в начале XX века, но в информатику он пришёл позже.
• В некоторых языках программирования (например, в Forth) очередь FIFO реализуется аппаратно на уровне процессора.
• Очередь FIFO лежит в основе работы многих онлайн-сервисов: от обработки заказов в интернет-магазинах до очередей в техподдержку.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (CLRS), глава 10.1 «Очереди и стеки».
• Кнут Д. Э. «Искусство программирования», том 1, раздел 2.2.1 «Очереди».
• Таненбаум Э., Бос Х. «Современные операционные системы», глава 2 «Процессы и потоки».
• Седжвик Р. «Фундаментальные алгоритмы на C++», часть 4 «Очереди».
• ISO/IEC 14882:2017 (C++17), раздел 23.6.3 «queue».