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

При реализации очереди рассматриваются очередь как отображение на массив (полустатическая реализация) и очередь как отображение на список.

Совокупность операций, определяющих структуру типа очередь:

· Операция инициализации.

· Операция включения элемента в очередь.

· Операция исключения элемента из очереди.

· Операция проверки: очередь пуста / очередь не пуста.

· Операция проверки: очередь переполнена / очередь не переполнена.

В последовательной памяти очередь имеет следующий вид:

Здесь: Uk 1 – указатель на “голову” (начало) очереди, Uk 2 – указатель на “хвост” (конец) очереди.

Чтобы избежать переполнения, рациональней использовать кольцевую очередь. При этом Uk 1 > Uk 2 или Uk 2 > Uk 1. В случае же если очередь не кольцевая, то всегда Uk 2 > Uk 1. Если очередь пуста или переполнена, то Uk 1 = Uk 2.

Пусть n – текущее состояние очереди, а N – количество элементов в очереди, тогда имеем условие 0 £ n £ N и значение n может являться условием проверки состояния очереди. Операция включения возможна, если n < N, а операция исключения, если n > 0. В случае кольцевой очереди при операции модуля указатели будут меняться следующим образом: Uk 1 = Uk 1 mod N + 1, Uk 2 = Uk 2 mod N + 1.

Схема на физическом уровне СД типа очередь выглядит следующим образом:

Дескриптор:

Условные обозначения	Название очереди
Нижний адрес очереди
Верхний адрес очереди
Указатель начала очереди
Указатель конца очереди
Свойства элементов очереди