Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу:
FIFO (First-In, First-Out) -
поступивший первым, обслуживается первым.
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая - конец очереди, третья - вспомогательная.
Описание компоненты очереди и переменных типа указатель дадим следующим образом:
type
PComp=^Comp;
Comp=record
D:T;
pNext:PComp
end;
var
pBegin, pEnd, pAux: PComp;
где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель.
Тип Т определяет тип данных компоненты очереди.
Начальное формирование очереди выполняется следующими операторами.
Добавление компоненты в очередь производится в конец очереди.
Добавление последующих компонент производится аналогично.
Выборка компоненты из очереди осуществляется из начала очереди, одновременно компонента исключается из очереди. Пусть в памяти ЭВМ сформирована очередь, состоящая из трех элементов.
Выборка компоненты выполняется следующими операторами.
Пример. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов 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.