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.