Очередь fifo

Принцип работы – “Первый пришел, первый вышел”.

Для организации такой очереди используются две ссылочные переменные типа Adres1 (см. пример 7.7): Left – для указания начала и Right – для указания конца очереди.

Добавление элемента в очередь осуществляется в соответствии со значением Right. Затем значение Right изменяется и указывает на последний занесенный элемент.

Выборка элементов из очереди происходит, исходя из значения Left. Затем Left изменяется и указывает на следующий элемент очереди.

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

А. Занесение элемента в очередь

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм занесения элемента в очередь:

1. Cоздание нового звена.

2. Занесение в последнее звено адреса нового звена.

3. Занесение Nil в поле Adrcled нового звена.

4. Занесение элемента в информационное поле нового звена.

5. Созданное звено сделать концом очереди.

Пример 7.16.

Процедура занесения элемента в очередь. Первый параметр – Right – адрес последнего занесенного элемента, второй – заносимое в очередь значение.

Procedure Dobavl (Var Right: Adres1; El: <Тип_элементов_очереди>);

Var

Q: Adres1;

Begin

{5} New (Q); {1-й этап алгоритма занесения}

{6} Right^.Adrcled := Q; {2-й этап алгоритма занесения}

{7} Q^.Adrcled := Nil; {3-й этап алгоритма занесения}

{8} Q^.Element := El; {4-й этап алгоритма занесения}

{9} Right:=Q {5-й этап алгоритма занесения}

End;

Б. Выбор элемента из очереди

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Алгоритм выбора элемента из очереди:

1. Чтение значения из начала очереди.

2. Запоминание ссылки на начало очереди.

3. Исключение первого звена из начала очереди.

4. Уничтожение первого звена.

Пример 7.17.

Процедура выбора элемента из очереди. Параметр Left используется для передачи адреса начала очереди. В параметр Elem передается значение из начала очереди.

Procedure Udal (Var Left: Adres1; Var Elem: <Тип_элементов_очереди>);

Var

Q: Adres1;

Begin

Elem := Left^.Element; {1-й этап алгоритма выбора}

{10} Q := Left; {2-й этап алгоритма выбора}

{11} Left := Left^.Adrcled; {3-й этап алгоритма выбора}

Dispose(Q) {4-й этап алгоритма выбора}

End;

В. Организация очереди

Пусть в программе имеется описание типа, приведенное в примере 7.7.

Организация очереди основана на использовании операции занесения элемента в очередь

Пример 7.18.

Организация очереди. Ввод исходного текста в очередь. Признак окончания текста – точка. Используется процедура Dobavl занесения элемента в очередь (см. пример 7.16).

...

Var

Right, Left: Adres1;

Bykva: Char;

Begin

Read (Bykva);

{1} New (Left);

{2} Left^.Adrcled := Nil;

{3} Left^.Element := Bykva;

{4} Right := Left;

Read (Bykva);

While Bykva <>’.’ Do

Begin

Dobavl (Right, Bykva);

Read (Bykva)

End

End.

Рисунок 7 .71 содержит схематические пояснения к примерам 7.16 – 7.18. Номерами на данном рисунке обозначены действия над очередью FIFO, соответствующие номерам операторов в данных примерах.

Рисунок 7.71 – Схематические пояснения к примерам 7.16 – 7.18

Таблицы