FIFO — принцип организации очередей¶

FIFO (англ. First In, First Out — «первый вошёл, первый вышел») — принцип организации обработки данных, при котором элементы обслуживаются строго в том порядке, в котором они поступили: первый добавленный элемент обрабатывается первым. Противоположный принцип — LIFO (Last In, First Out, «последний вошёл, первый вышел»), при котором最先 обрабатывается последний добавленный элемент. Термин применяется в информатике, математике, логистике, производстве и теории массового обслуживания.

¶Основные понятия

FIFO реализует абстрактный тип данных «очередь» (queue). Основные операции над очередью:

• enqueue — добавление элемента в конец очереди;
• dequeue — извлечение элемента из начала очереди;
• peek (front) — просмотр элемента без его удаления.

Сложность обеих основных операций в типичных реализациях — O(1), что делает очередь эффективной структурой данных для потоковой обработки.

¶Способы реализации

¶Массив

Простейшая реализация — кольцевой буфер (circular buffer): массив фиксированного размера и два индекса — на начало и на конец. При достижении конца массива индекс «заворачивается» в начало. Ограничение — заранее известная максимальная ёмкость.

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

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

¶Динамический массив

Массив, который расширяется при заполнении (как в std::queue на базе std::deque в C++ или collections.deque в Python). Амортизированная сложность операций остаётся O(1).

¶Применение в информатике

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

FIFO-планирование (FIFO scheduling) — один из первых алгоритмов диспетчеризации процессов: процессы выполняются в порядке поступления в очередь готовых процессов. Простота алгоритма сочетается с недостатками: возможен эффект конвоя (convoy effect), когда короткие задачи ждут завершения долгих, и отсутствие приоритетов.

¶Сети передачи данных

В сетевых устройствах (маршрутизаторах, коммутаторах) очереди буферов обычно устроены по принципу FIFO. При переполнении буфера применяется политика tail drop — отбрасывается последний поступивший пакет. Альтернативы — RED (Random Early Detection) и AQM (Active Queue Management).

¶Базы данных и брокеры сообщений

FIFO-очереди используются в системах обмена сообщениями: Apache Kafka, RabbitMQ, Amazon SQS, Redis (команды LPUSH/LRPOP). Kafka гарантирует упорядоченную доставку в пределах партиции. Системы очередей применяются для асинхронной обработки задач, разгружения веб-серверов и интеграции микросервисов.

¶Графы и алгоритмы

Обход графа в ширину (BFS) использует FIFO-очередь: вершины обрабатываются по мере удаления от стартовой. Для поиска кратчайшего пути в невзвешенном графе BFS с FIFO-очередью даёт оптимальный результат.

¶Применение вне информатики

¶Логистика и складское дело

В складском хозяйстве FIFO означает правило «первая партия поступления — первая отгрузка». Это стандарт для товаров с ограниченным сроком годности (продукты питания, фармацевтика). Система WMS (Warehouse Management System) поддерживает FIFO-учёт для контроля сроков.

¶Производство и теория массового обслуживания

В теории массового обслуживания (теории очередей) каналы типа M/M/1 и M/M/c работают по дисциплине FIFO. В японской системе lean manufacturing FIFO-потоки используются для выравнивания загрузки линий.

¶Финансы

При расчёте себестоимости продаж FIFO означает, что первыми списываются самые ранние поступившие запасы. Метод FIFO для определения стоимости запасов признан МСФО (IAS 2), но не разрешён РСБУ без перехода на международные стандарты.

¶Сравнение с LIFO

¶Ограничения

FIFO не учитывает приоритеты: срочная задача, поступившая последней, будет ждать обработки всех предыдущих. Для решения этой проблемы существуют приоритетные очереди (priority queue) и алгоритмы с обратной связью. Кроме того, при большом объёме данных FIFO-очередь может стать узким местом, если скорость потребления ниже скорости производства.

¶См. также

• Очередь (структура данных)
• Стек (структура данных)
• Кольцевой буфер
• Алгоритм поиска в ширину
• Планирование процессов

Источники:

• Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. — «Алгоритмы: построение и анализ»
• Таненбаум Э. — «Современные операционные системы»
• Седжвик Р., Уэйн К. — «Алгоритмы»
• Гарсия-Молина Х., Ульман Дж., Уидом Дж. — «Системы управления базами данных. Полный курс»
• IAS 2 «Запасы» — Международные стандарты финансовой отчётности