Очередь FIFO

Для очередей типа FIFO вводят понятия начального ("головы") и последнего ("хвоста") элемента. Добавляемые элементы помещаются в "хвост" очереди, а выборка осуществляется с «головы». Таким образом, для создания этой очереди и выборки из нее нужно иметь указатели на начало, конец и текущий элемент.

Общий алгоритм формирования работы с такой очередью может быть таким же, как для LIFO.

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

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

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

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

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

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

Уточненный алгоритм можно получить, приняв во внимание способ формирования и выборки из очереди типа FIFO,описанный выше.

1.1. Указатель_из_первого_элемента (головы) = Nil.

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

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

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

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

2.3. Записать в «хвост» очереди Nil.

2.4. Если Элемент_очереди – первый (головной), то

Запомнить его адрес (Fp)

Иначе

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

2.5. Передвинуть «хвост» очереди (Lp) на один элемент.

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

3.1. Указатель_Текущего_элемента = Указатель_Первого_элемента очереди.

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

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

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

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

Соответствующая программа будет иметь вид

Program Fifo;

Type

Ptr = ^El;

El = Record

Buk : Char;

Sl : Ptr;

End;

Var

Fp,Lp,Tp : Ptr; {Указатели на первый, последний и текущий элемент}

C : Char;

Begin

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

Fp := Nil; { Очередь пустая}

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

Readln(C);

While C <> ’*’ do

Begin

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

Tp^.Buk := C; {Заполнение информационного поля}

Tp^.Sl := Nil; {Очередной элемент – последний в очереди}

If Fp = Nil then {Если в очереди только один элемент}

Fp := Tp {Указатель на "голову" очереди}

Else

Lp^.Sl := Tp; {Ссылка из предпоследнего элемента на последний}

Lp := Tp; {Указатель на "хвост" очереди}

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

Readln(C);

End;

{ Просмотр очереди с "головы" }

Tp := Fp; {Tекущий указатель теперь указывает на первый элемент}

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

While Tp <> Nil do

Begin

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

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

End;

WriteLn;

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

Readln;

End.