ОЧЕРЕДИ

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

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.