Мова програмування Pascal

Очереди

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

 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.

Зверніть увагу на додаткові посилання

Головний розділ

Мова програмування Pascal