Untitled

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); є *ДДєДДДї є є є є

ИНННННј і єНННННє ИНННННј

pBegin АДД>є є pEnd

ИНННННј

ЙННННН» ЙННННН» ЙННННН»

pBegin^.pNext:=NIL; є *ДДєДДДї є є є є

ИНННННј і єНННННє ИНННННј

pBegin АДД>є NIL є pEnd

ИНННННј

ЙННННН» ЙННННН» ЙННННН»

pBegin^.D:=D1; є *ДДєДДДї є D1 є є є

ИНННННј і єНННННє ИНННННј

pBegin АДД>є NIL є pEnd

ИНННННј

ЙННННН» ЙННННН» ЙННННН»

pEnd:=pBegin; є *ДДєДДДї є D1 є ЪДДДєДД* є

ИНННННј і єНННННє і ИНННННј

pBegin АДД>є NIL є<ДДЩ pEnd

ИНННННј

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

New(pAux);

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є

ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј

pBegin АДД>є NIL є<ДДЩ pEnd є є<ДДЩ pAux

ИНННННј ИНННННј

pAux^.pNext:=NIL;

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є

ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј

pBegin АДД>є NIL є<ДДЩ pEnd є NIL є<ДДЩ pAux

ИНННННј ИНННННј

pBegin^.pNext:=pAux;

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є ЪДДДєДД* є є є ЪДДДєДД* є

ИНННННј і єНННННє і ИНННННј єНННННє і ИНННННј

pBegin АДД>є * є<ДДЩ pEnd є NIL є<ДДЩ pAux

ИНННННј ИНННННј

і ^

і і

АДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ

pEnd:=pAux;

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є є *ДДєДДДї є є ЪДДДєДД* є

ИНННННј і єНННННє ИНННННј і єНННННє і ИНННННј

pBegin АДД>є * є pEnd АДД>є NIL є<ДДЩ pAux

ИНННННј ИНННННј

і ^

і і

АДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ

pEnd^.D:=D2;

ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є є D2 є ЪДДДєДД* є

ИНННННј і єНННННє єНННННє і ИНННННј

pBegin АДД>є *ДДєДДДДДДДДДДДДДДДДДДДД>є NIL є<ДДЩ pEnd

ИНННННј ИНННННј

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

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

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

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

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є є D2 є є D3 є ЪДДДєДД* є

ИНННННј і єНННННє єНННННє єНННННє і ИНННННј

pBegin АДД>є *ДДєДДДДДД>є *ДДєДДДДДД>є NIL є<ДДЩ pEnd

ИНННННј ИНННННј ИНННННј

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

D1:=pBegin^.D;

pBegin:=pBegin^.pNext;

ЙННННН» ЙННННН» ЙННННН» ЙННННН» ЙННННН»

є *ДДєДДДї є D1 є є D2 є є D3 є ЪДДДєДД* є

ИНННННј і єНННННє єНННННє єНННННє і ИНННННј

pBegin і є є ЪДД>є *ДДєДДДДДД>є NIL є<ДДЩ pEnd

і ИНННННј і ИНННННј ИНННННј

і і

АДДДДДДДДДДДДДЩ

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

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

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

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

строка символов 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.