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

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

FIFO

Для описания элемента типа очередь нужны две переменные-указатели начала и конца очереди. Определим их как х1 и х2, тогда описание имеет вид:

Type poc = ^ oc;

Oc = record

Data: integer;

Next: poc;

End;

Var x1, x2: poc;

Над очередью определены 2 операции:

1) занесение элемента в конец очереди;

2) извлечение элемента из начала очереди.

Так как очередь может быть представлена списком, то занесение элемента в очередь соответствует занесению элемента в конец списка.

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

Procedure Write0 (var x1, x2: poc; c: integer); {здесь х1 и х2 – формальные параметры-переменные-указатели начала и конца очереди, с – новое значение}.

Var u: poc;

Begin

New(u); {указатель u получает адрес свободной ячейки

динамической памяти }

u ^. data: = c; {информационное поле получает значение с }

u ^. next: = nil; {адресная часть получает значение указателя

конца очереди}

If x1 = nil

then x1: = u {если очередь пуста, то указатель начала

х1 принимает значение нового адреса u }

Else

x2 ^. next: = u; {иначе элемент заносится в конец очереди по

адресу указателя х2 конца, далее х2 получает

значение адреса последнего элемента u }

x2: = u;

End;

Процедура извлечения элемента из очереди аналогична извлечению элементов из начала списка.

Т.к. извлечение элемента из пустой очереди осуществить нельзя, то сначала проверяем, есть ли элементы в очереди, т.е. задаем вопрос х1 = nil?

Procedure ReadO (var x1, x2: poc; var c: integer);

Var u: poc;

Begin

If x1 = nil then writeln (‘oсhered pusta’)

Else

Begin

c: = x1^. data;

u: = x1;

x1: = x1^. next;