Что такое очередь (queue) как структура данных?

Question

Что такое очередь (queue) как структура данных?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 24% Категория: PHP Разработчик

Ответ

Очередь (Queue) — это абстрактный тип данных, работающий по принципу FIFO (First-In, First-Out): первый добавленный элемент будет первым извлечённым. Основные операции: enqueue (добавить в конец) и dequeue (удалить из начала).

Реализация в PHP:

Использование встроенного класса SplQueue:

$queue = new SplQueue();
$queue->enqueue('A'); // Очередь: [A]
$queue->enqueue('B'); // Очередь: [A, B]
echo $queue->dequeue(); // Выведет 'A', очередь: [B]
echo $queue->bottom();  // Показать первый элемент без удаления: 'B'

Реализация на массивах:

$queue = [];
array_push($queue, 'A'); // enqueue
array_push($queue, 'B');
$first = array_shift($queue); // dequeue -> 'A'

Области применения в разработке:

Алгоритмы: Обход графа в ширину (BFS).
Обработка задач: Управление порядком выполнения фоновых задач.
Буферизация: Сглаживание нагрузки между быстрым производителем и медленным потребителем данных.

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

Ответ 18+ 🔞

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

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

Основные движухи тут две:

enqueue — это когда ты встаёшь в хвост этой очереди. Добавился в конец и ждёшь.
dequeue — это когда тебя, наконец, обслужили. Тебя выдернули из начала очереди, и ты пошёл по своим делам.

Как это в PHP сделать? Да элементарно, ёпта.

Первый способ — по-взрослому, через встроенный класс SplQueue.
Он уже всё умеет, тебе только пользоваться.

$queue = new SplQueue(); // Создали пустую очередь
$queue->enqueue('A'); // Встал первым. Очередь: [A]
$queue->enqueue('B'); // Встал вторым. Очередь: [A, B]
echo $queue->dequeue(); // Обслужили первого. Выведет 'A'. Очередь теперь: [B]
echo $queue->bottom();  // Глянуть, кто теперь первый в очереди, но не выгонять. Покажет 'B'

Красота, правда? Всё аккуратно, как в аптеке.

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

$queue = []; // Вот тебе и очередь, обычный массив
array_push($queue, 'A'); // Это наш enqueue — пихаем в конец
array_push($queue, 'B');
$first = array_shift($queue); // А это dequeue — выдёргиваем первого. $first будет 'A'

Работает? Работает. Но тут есть нюанс, как говорится. С массивами нужно быть аккуратным, чтобы не накосячить с индексами.

А где это всё, блядь, применяется? Да везде!

В алгоритмах. Самый классический пример — обход графа в ширину (BFS). Ты ж не вглубь лезешь, как угорелый, а обрабатываешь всех соседей по порядку. Без очереди тут — никуда.
Обработка задач. Представь, у тебя куча фоновых задач на отправку писем или генерацию отчётов. Кидаешь их в очередь, а какой-нибудь воркер потихоньку выгребает и выполняет по одной. Порядок соблюдён, всё честно.
Буферизация. Допустим, у тебя один сервис данные генерирует быстро, как сумасшедший, а другой принимает их медленно. Очередь между ними будет как буфер: быстрый накидает, медленный потом по мере сил заберёт. И никто никого не затопчет.

Главное, чтобы операции enqueue и dequeue в нормальной реализации работали за O(1), то есть мгновенно. Не должно быть такого, чтобы чтобы добавить или удалить элемент, тебе пришлось пол-очереди перелопачивать. Иначе это уже не очередь, а какая-то манда с ушами.

Вот и вся наука. Просто запомни: первый пришёл — первый ушёл. Как в жизни, только без драк и без споров, кто за кем стоял.