22.2. Очереди

Наиболее простые способы формирования и обслуживания очередей (дисциплины обслуживания):

1) LIFO — Last Input – First Output («Последним пришел - Первым вышел», т.е. обслуживание в порядке, обратном поступлению);

2) FIFO — First Input – First Output («Первым пришел - Первым вышел», т.е. обслуживание в порядке поступления).

Рассмотрим механизм формирования и выборки очередей на примере списка, в которых информационный элемент имеет тип Char.

22.2.1. Очередь типа lifo

Это – наиболее простая очередь. Очередной элемент добавляется (или убирается) только в начало очереди.

Для создания и управления очередью типа LIFO достаточно иметь указатель на начало очереди и указатель на текущий элемент очереди. На бытовом уровне – это странная очередь, а в вычислительной технике она отображает работу стека. Новый объект (на него указывает текущий указатель) настраивает свой указатель на первый элемент существующей очереди, а указатель на первый элемент обновляемой очереди - настраивает на себя. Таким образом, пришедший последним – в очереди оказывается и выбирается из нее первым.

Рассмотрим алгоритм формирования очереди LIFO, считая, что элементы очереди (символы) вводятся с клавиатуры. В конце набирается символ ’*’. Он может быть таким.

1. Задать начальный элемент очереди.

2. Пока Информационный_элемент не равен ’*’ выполнить

Ввести очередной Информационный_элемент и

Поместить его в очередь.

3. Вывести Элементы очереди.

4. Закончить.

Уточним алгоритм, приняв во внимание, что в очереди типа LIFO добавление и выборка элементов осуществляется только в одном месте (в начале очереди), и получим.

1.1. Указатель_из_элемента_очереди = Nil (последний элемент).

1.2. Ввести Информационный_элемент.

2. Пока Информационный_элемент не равен ’*’ выполнить

2.1. Выделить память для Текущего_элемента.

2.2. Задать Информационный_элемент.

2.3. Связать Текущий_элемент со Следующим («хвостом» очереди).

2.4. Ввести Информационный_элемент.

3.1. Указатель_Текущего_элемента = Указатель_Следующего (начального элемента).

3.2. Пока Указатель_Текущего_элемента не Nil выполнить

3.2.1. Вывести Текущий_информационный_элемент;

3.2.2. Перейти к Следующему_элементу_очереди.

4. Закончить.

Программа для этого алгоритма будет иметь вид

Program Lifo;

Type

Ptr = ^El;

El = Record

Buk : Char; { Информационное поле }

Sl : Ptr; { Поле указателя }

End;

Var

Fp,Tp : Ptr; { Указатель на начало и текущий }

C : Char;

Begin

{ Начало формирования очереди }

Fp := Nil; {Указатель на начало очереди. Очередь пустая}

Writeln(’Введите элемент очереди’);

Readln(C);

{ Формирование очереди }

While C <> ’*’do

Begin

New(Tp); {Выделение памяти для нового элемента}

Tp^.Buk := C; {Запись информационной компоненты}

Tp^.Sl := Fp; {Запись в поле указателя нового элемента}

{ссылки на начало очереди – связь с остальной очередью}

Fp := Tp; { Теперь Fp, как и Tp, указывает }

{ на начало очереди }

Writeln(’ Введите элемент очереди’);

Readln(C);

End;

{В этом месте Fp и Tp - ссылки на начало очереди}

{ Вывод очереди с ее начала (головы) }

WriteLn(’Вот такая очередь:’);

While Tp <> Nil do

Begin

Write (Tp^.Buk:2); {Вывод информационного поля элемента}

Tp := Tp^.Sl; { Переход к следующему элементу }

End;

WriteLn;

Writeln(’Конец работы. Нажмите ENTER’);

Readln;

End.

На рис.2.18 показана последовательность формирования очереди LIFO на примере двух элементов в соответствии с текстом программы.