Абстрактный тип данных «очередь». Реализация очереди с помощью указателей. Привести рисунок и определить абстрактный тип «очередь».

Очередь – это специальный тип списка. Очередью называют упорядоченный набор элементов, где элементы удаляются с одного его конца, который называется началом, а вставляются с другого, который называется концом очереди. Очереди также называются списками типа FIFO (аббревиатура расшифровывается как first in first out: первым вошел – первым вышел).

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

1) MAKENULL(Q) очищает очередь Q, делая ее пустой.

2) FRONT(Q) – функция, возвращающая первый элемент очереди Q.

3) ENQUEUE(x, Q) вставляет элемент х в конец очереди Q.

4) DEQUEUE (Q) удаляет первый элемент очереди Q.

5) EMPTY (Q). Эта функция возвращает значение true (истина) тогда и только тогда, когда Q является пустой очередью.  

Реализация очереди с помощью указателей

Рассмотрим способ реализации очереди на базе списков, учитывая структурные и функциональные особенности очереди. Например, при добавлении элемента в конец очереди вместо перемещения по списку от начала к концу можно хранить указатель на конец очереди. Указатель на начало очереди будет полезен при выполнении операторов, связанных с извлечением элементов из структуры. В языке Pascal в качестве заголовка можно использовать динамическую переменную и поместить в нее указатель на начало очереди, что позволит удобно организовать очищение очереди.

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

Рассмотрим программную реализацию некоторых из вышеперечисленных операторов над очередями.

MAKENULL(Q) очищает очередь Q, делая ее пустой.

1) Procedure Makenull (var q:ptr);

begin

new ( q ); {Создание ячейки заголовка}

q^. front:=q;

q^. front^.next:=nil;

q^. rear:=q^.front;

end;

FRONT(Q) – функция, возвращающая первый элемент очереди Q.

function FRONT ( Q: QUEUE ): eltype ;

  begin

     if EMPTY(Q)

     then Write(' Очередь пуста ')

    else Front := Q. Front^.next^.element

end ; { FRONT }

ENQUEUE(x, Q) вставляет элемент х в конец очереди Q.

procedure ENQUEUE(x:eltype;var Q:QUEUE) ;

begin

New (Q.rear^.next) ;

Q.rear:= Q.rear^.next;

Q.rear^.element:= x;

O.rear^.next:= nil

end ; { ENQUEUE }

DEQUEUE ( Q ) удаляет первый элемент очереди Q .

Procedure dequeue ( var q : ptr ); {Удаление первого элемента очереди}

begin

if empty (q) then

writeln('Очередь пуста')

else

q^.front:=q^.front^.next;

end;

EMPTY (Q) . Эта функция возвращает значение true (истина) тогда и только тогда, когда Q является пустой очередью.

Function empty(q:ptr):boolean;

var z:boolean;

begin

if

q^.front= q^.rear then { Проверка пустоты очереди }

z:=true

else z:=false;

end;

Разновидности очередей

Интересной разновидностью очередей являются многопоточные очереди (multi headed queues). Элементы в нее, как обычно, добавляются в конец очереди, но очередь имеет несколько потоков ( front end ) или голов ( heads ).

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

В общем случае многопоточные очереди более эффективны, чем несколько однопоточных очередей.

Циклическая очередь. Некоторые программы можно улучшить, используя циклические очереди. При организации очереди на основе массива при достижении предела массива можно вернуть указатели вставки в очередь и удаления из нее на начало массива. В этом случае в очередь можно добавлять и удалять из нее любое число элементов. Такая очередь называется циклической, поскольку массив используется не как линейный список, а как циклический.

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

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

Приоритетные очереди . Каждый элемент в приоритетной очереди (priority queue) имеет связанный с ним приоритет. Если программе нужно удалить элемент из очереди, она выбирает элемент с наивысшим приоритетом. Как хранятся элементы в приоритетной очереди, не имеет значения, если программа всегда может найти элемент с наивысшим приоритетом.

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

Простой способ организации приоритетной очереди — поместить все элементы в список. Если требуется удалить элемент из очереди, можно найти в списке элемент с наивысшим приоритетом. Чтобы добавить элемент в очередь, он помещается в начало списка. При использовании этого метода, для добавления нового элемента в очередь требуется только один шаг. Чтобы найти и удалить элемент с наивысшим приоритетом, требуется O(N) шагов, если очередь содержит N элементов.

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