4.6. Черга

Черга — це другий окремий випадок лінійного списку: нові вузли додаються в список тільки в її хвіст (в кінець) і віддаляються тільки з її голови (або начала). Чергу називають структурою даних типу FIFO (first-in, first-out — «першим ввійшов, першим вийшов»). Елемент-посилання кінця черги встановлюється в nil, відзначаючи її кінець

Примітка. Черги знаходять широке вживання в комп'ютерних системах. В більшості комп'ютерів є тільки один процесор, тому в кожний момент часу виконується тільки одна програма. Програма, якій потрібен процесорний час, поміщається в чергу. Та програма, що знаходиться в голові черги, отримає час процесора першою. Кожна програма поступово переміщається до початку черги у міру того, як процесор обслуговує програми, що знаходяться перед нею.

Черзі використовується при пакетному друці (print spooling). Наприклад, всіх користувачів мережі може обслуговувати один принтер. Посилати завдання на принтер могти відразу декількох користувачів, навіть якщо принтер вже зайнятий. В цьому випадку завдання на друк поміщаються в чергу до тих пір, поки принтер не звільниться. Чергою управляє програма, звана менеджером друку (print spooler), який направляє на принтер наступне завдання, коли завершується поточне.

В черзі, через її визначення, доступні дві позиції: її кінець, куди заносяться нові елементи, і її початок, звідки витягуються елементи. Елементи черги описуються так само, як і елементи стека (при одно направленій черзі):

type ptr=^s;

s=record

data:integer;

next:ptr

end;

var u,sl:ptr; d : integer;

де u — відповідає початку черги і використовуватиметься для виводу елемента з черги, sl - відповідає кінцю черги і використовуватиметься для додавання нових елементів в чергу.

Графічно чергу можна представити так:

sl

u

.. .

Формування черги здійснюється за допомогою наступної процедури:

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

var rab:ptr; i: integer;

begin

i:=1;

Write(i,'-й элемент: '); Read(d); {Чтение первого элемента }

New(rab); {Резервируется память под первый элемент очереди}

rab^.next:=nil; {Первый элемент не имеет ссыпки}

rab^.data:=d; {Занесение в очередь первого элемента}

u :=rab; sl:=rab;

while true do {Безконечный цикл до d=0}

begin

inc(i);

Write(i,'-й элемент: ');

Read(d); {Значения очередного элемента}

if d=0 then exit; {Выход из цикла при d=0}

New(rab);

rab^.next:=nil;

rab^.data:=d;

sl^. next:=rab; {Указатель с предпоследнего на последний элемент}

sl:=rab; {Указатель на последний элемент}

end;

end;

Видалення елемента з початку черги проводиться за допомогою наступної процедури:

procedure Ud(rab:ptr);{Удаление элемента из начала очереди}

begin

u:=u^.next;

Writeln(' Удален первый элемент очереди --> ',rab^.data);

Dispose(rab);

end;

Процедура додавання елемента в кінець черги має вигляд:

procedure Dob; {добавления элемента в конец очереди}

var rab:ptr;

begin

Write('Добавление элемента: '); Read(d);

New(rab); rab^.data:=d; rab^.next:=nil;

sl^.next:=rab;

sl:=rab;

Writeln('Новый элемент ',d,' помещен в очередь');

end;

Процедура виводу на екран елементів черги має вигляд:

procedure print(s:string;first:ptr);

begin

if first=nil

then writeln('Очередь пустая !!!')

else write(s,' очередь -> ');

while first<>nil do

begin write(first^.data,' '); first:=first^.next; end;

writeln;

end;

З використанням цих процедур розділ основної програми має вигляд:

Begin

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

print(' Сформована ',u);

Dob; {добавления элемента в конец очереди}

print(' Додана ',u);

Ud(u); {Удаление элемента из начала очереди}

print('Підсумкова ',u);

End. { Протокол работы программы

1-й элемент: 1

2-й элемент: 2

3-й элемент: 3

4-й элемент: 4

5-й элемент: 5

6-й элемент: 0

С ф о р м и р о в а н а очередь -> 1 2 3 4 5

Добавление элемента: 6

Новый элемент 6 помещен в очередь

Д о б а в л е н н а я очередь -> 1 2 3 4 5 6

Удален первый элемент очереди --> 1

И т о г о в а я очередь -> 2 3 4 5 6 }

Задание: Для самоконтроля усвоения рассмотренного материала прорисуйте изменение значений элементов очереди и переменных: u, sl, first и rab