Очереди
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
Люди также интересуются этой лекцией: 7. Статья.
DelQueue(pBegin,sC);
writeln(sC);
until pBegin=NIL
end.
