Очередь

Очередь (queue) – это такой последовательный список с переменной длиной, в который включение элементов происходит с одной стороны, а исключение – с другой стороны. Она функционирует по принципу FIFO (First In - First Out, т.е. «первым пришел - первым вышел»). Та сторона, с которой осуществляется добавление элементов, называется хвостом (tail) или концом очереди, другая сторона, из которой выполняется удаление, – головой (head). Для индикации хвоста и головы организуется два указателя: указатель хвоста (tail pointer) и указатель головы (head pointer). Логическая структура очереди, которую принято изображать в горизонтальной «ориентации», показана на рисунке 7.3. Обратите внимание, что указатель хвоста ссылается на свободную ячейку, следующую за элементом е_n, включенным в очередь последним.

Рисунок 7.3 – Логическая структура очереди

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

Основные операции в очереди - включение и исключение элемента. При включении новый элемент заносится в ячейку, адресуемую указателем хвоста, после чего указатель хвоста «перемещается» к следующему свободному элементу. При исключении из очереди извлекается элемент е₁, адресуемый указателем головы, и этот указатель «передвигается» к элементу е₂, который становится головным элементом. Признаком пустой очереди является равенство указателей хвоста и головы.

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

В кольцевой очереди соблюдается дисциплина FIFO. В отличие от обычной очереди включение в кольцевую очередь организовано следующим образом: сразу после выхода указателя хвоста за пределы его границы он переводится на слот, расположенный «вплотную» к границе, расположенной со стороны головы и, если этот слот пуст, то в него включается новый элемент. На рисунке 7.4 показана ситуация, когда перемещение указателя хвоста к начальному слоту происходит при включении элемента е₄, а затем элемента е₅. Очевидно, в кольцевой очереди возможно любое соотношение между указателями головы и хвоста.

Рисунок 7.4 – Логическая структура кольцевой очереди

Очереди находят интенсивное применение в вычислительной технике, например, при буферизации данных в устройствах. Буфер представляет собой набор внутренних ячеек памяти с определенными правилами доступа как со стороны устройства, так и со стороны компьютерного «центра» (программы, исполняемой процессором).

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

По принципу кольцевой очереди функционируют, например, буферы некоторых устройств с блочным обменом данными (диски, адаптеры локальных сетей). Наиболее известным примером кольцевой очереди является структура, называемая буфером клавиатуры (буфер BIOS для записи кодов нажимаемых клавиш).

Дек

Особым типом последовательного списка с переменной длиной является дек (deque). Другие названия дека - двухсторонняя очередь, очередь с двумя концами (double ended queue). Дек – это такой последовательный список, в котором как включение, так и исключение могут выполняться с любого из двух концов.

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

Структура дека аналогична структуре обычной очереди. Однако применительно к деку вместо хвоста и головы говорят о правом и левом концах.