О Ч Е Р Е Д И

39. О Ч Е Р Е Д И

Очередью называется динамическая структура данных, добавление ком-

поненты в которую производится в один конец, а выборка осуществляется

с другого конца. Очередь работает по принципу:

FIFO (First-In, First-Out) -

поступивший первым, обслуживается первым.

Для формирования очереди и работы с ней необходимо иметь три пере-

менные типа указатель, первая из которых определяет начало очереди,

вторая - конец очереди, третья - вспомогательная.

Описание компоненты очереди и переменных типа указатель дадим сле-

дующим образом:

type

PComp=^Comp;

Comp=record

D:T;

pNext:PComp

end;

var

pBegin, pEnd, pAux: PComp;

где pBegin - указатель начала очереди, pEnd - указатель конца очере-

ди, pAux - вспомогательный указатель.

Тип Т определяет тип данных компоненты очереди.

Начальное формирование очереди выполняется следующими операторами:

 г=====¬ г=====¬ г=====¬

 New(pBegin); ¦ *--¦---¬ ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ ¦ pEnd

L=====-

г=====¬ г=====¬ г=====¬

 pBegin^.pNext:=NIL; ¦ *--¦---¬ ¦ ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦ pEnd

 L=====-

г=====¬ г=====¬ г=====¬

 pBegin^.D:=D1; ¦ *--¦---¬ ¦ D1 ¦ ¦ ¦

L=====- ¦ ¦=====¦ L=====-

pBegin L-->¦ NIL ¦  pEnd

L=====-

г=====¬ г=====¬ г=====¬

 pEnd:=pBegin; ¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====-

 pBegin L-->¦ NIL ¦<--- pEnd

L=====-

Добавление компоненты в очередь производится в конец очереди:

 New(pAux);

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ ¦<--- pAux

L=====- L=====-

 pAux^.pNext:=NIL;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ NIL ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

 pBegin^.pNext:=pAux;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦<--- pEnd ¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

 pEnd:=pAux;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ L=====- ¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ * ¦ pEnd L-->¦ NIL ¦<--- pAux

L=====- L=====-

¦ ^

¦ ¦

L----------------------------

 pEnd^.D:=D2;

г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦-------------------->¦ NIL ¦<--- pEnd

L=====- L=====-

Добавление последующих компонент производится аналогично.

Выборка компоненты из очереди осуществляется из начала очереди,

одновременно компонента исключается из очереди. Пусть в памяти ЭВМ

сформирована очередь, состоящая из трех элементов:

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦  ¦=====¦ ¦=====¦ ¦ L=====-

pBegin L-->¦ *--¦------>¦ *--¦------>¦ NIL ¦<--- pEnd

L=====- L=====- L=====-

Выборка компоненты выполняется следующими операторами:

 D1:=pBegin^.D;

 pBegin:=pBegin^.pNext;

г=====¬ г=====¬ г=====¬ г=====¬ г=====¬

¦ *--¦---¬ ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦

L=====- ¦ ¦=====¦  ¦=====¦ ¦=====¦ ¦ L=====-

pBegin ¦ ¦ ¦ --->¦ *--¦------>¦ NIL ¦<--- pEnd

¦ L=====- ¦ L=====- L=====-

¦ ¦

L--------------

Пример. Составить программу, которая формирует очередь, добавляет

в нее произвольное количество компонент, а затем читает все компонен-

ты и выводит их на экран дисплея. В качестве данных взять строку сим-

волов. Ввод данных - с клавиатуры дисплея, признак конца ввода -

строка символов END.

Program QUEUE;

uses Crt;

type

Alfa= String[10];

PComp= ^Comp;

Comp= record

sD:Alfa;

pNext:PComp

end;

var

pBegin, pEnd: PComp;

sC: Alfa;

Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);

begin

New(pBegin);

pBegin^.pNext:=NIL;

pBegin^.sD:=sC;

pEnd:=pBegin

end;

Procedure AddQueue(var pEnd:PComp; var sC:Alfa);

var pAux: PComp;

begin

New(pAux);

pAux^.pNext:=NIL;

pEnd^.pNext:=pAux;

pEnd:=pAux;

pEnd^.sD:=sC

end;

Procedure DelQueue(var pBegin: PComp; var sC: Alfa);

begin

sC:=pBegin^.sD;

pBegin:=pBegin^.pNext

end;

begin

Clrscr;

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

CreateQueue(pBegin,pEnd,sC);

repeat

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

AddQueue(pEnd,sC)

until sC='END';

writeln(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');

repeat

DelQueue(pBegin,sC);

writeln(sC);

until pBegin=NIL

end.