Что такое очередь?¶
Очередь - это упорядоченная коллекция элементов, в которой добавление новых происходит с одного конца, называемого “хвост очереди”, а удаление существующих - с другого, “головы очереди”. Как только элемент добавляется в конец очереди, он начинает свой путь к её началу, ожидая удаления предыдущих.
Самые последние из добавленных в очередь единиц должны ждать в конце коллекции. Элемент, который пробыл в очереди дольше всего, находится в её начале. Такой принцип упорядочения иногда называют FIFO, first-in first-out (англ. “первым пришёл - первым вышел”). Ещё он известен, как “первым пришёл - первым обслужен”.
Простейший пример такой структуры данных - это обычная очередь, в которой все мы иногда стоим: в кинотеатре, перед кассой в бакалейной лавке, в закусочной (где мы, кстати, можем “выталкивать” поднос из стопки/стека). Правильные очереди очень ограничены тем, что имеют только один путь в и один путь из. Для них не предусмотрены прыжки в середину или выход до того, как пройдёт достаточно времени, чтобы переместиться в начало. Рисунок 1 показывает простую очередь из объектов данных Python.
Рисунок 1: Очередь из объектов данных Python
В информатике тоже есть распространённые примеры очередей. В нашей компьютерной лаборатории стоит 30 компьютеров, подключённых по сети к одному принтеру. Когда студенты хотят что-то распечатать, они набирают задание “встать в очередь” вместе со всеми другими ожидающими печати заданиями. Первое задание - следующее, которое будет выполнено. Если вы последний в очереди, то должны ждать, пока напечатаются все стоящие перед вами документы. Позднее мы исследуем этот интересный пример более подробно.
В дополнение к очереди на печать оперативная система использует несколько различных очередей для контроля процессов внутри компьютера. Планирование, что делать следующим, обычно основывается на алгоритме очереди, который пытается запускать программы на выполнение так быстро, как это возможно, и обслуживать максимальное число пользователей. Также иногда в процессе печати на клавиатуре нажатия клавиш опережают появление символов на экране. Это происходит из-за того, что компьютер в этот момент выполняет другую работу. Нажатия клавиш помещаются в очередеподобный буфер, чтобы в конце концов отобразиться на экране в правильном порядке.