Энциклопедия Turbo Pascal. Главы 1-4 - Очереди

ОГЛАВЛЕНИЕ

Очереди

Очередь представляет собой линейный список данных,  доступ к которому осуществляется по принципу "первый вошел,  первый вышел"
/иногда сокращенно его называют методом доступа  FIFO/.  Элемент, который был первым поставлен в очередь,  будет первым получен при поиске.  Элемент, поставленный в очередь вторым, при поиске будет получен также вторым и т.д. Этот способ является единственным при постановке элементов в очередь и при поиске элементов в очереди.
Применение очереди не позволяет делать прямой доступ к любому конкретному элементу.

В повседневной жизни очереди встречаются часто.  Например, очередь в банке или очередь в кафетериях с быстрым обслуживанием являются очередью в  указанном выше смысле /исключая те случае, когда человек пытается добиться обслуживания вне очереди!/.  Для того,  чтобы лучше понять работу очереди, рассмотрим две процедуры:  постановка в очередь и выборка из очереди.  При выполнении процедуры постановки в очередь элемент помещается в конец очереди.  При выполнении процедуры выборки из очереди из нее удаляется первый элемент,  который является результатом выполнения данной процедуры.  Работа очереди проиллюстрирована на рис.4.  Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент.  Если этот элемент нигде не будет сохранен, то в последствии к нему нельзя будет осуществить доступ.

Операция                 Содержимое очереди
     1 Qstore(A)                A
     1 Qstore(B)                A B
     1 Qstore(C)                A B C
     2 Qretrieve returns A      B C
     1 Qstore(D)                B C D
     2 Qretrieve returns B      C D
     2 Qretrieve returns C      D

Рис.4. Работа очереди:
    1 - постановка в очередь;
    2 - выборка из очереди элемента А, В, С.

Очереди в программировании используются во многих случаях, например,  при моделировании (обсуждается ниже в соответствующей главе),  при планировании работ (метод ПЕРТ или графики Гатта), при буферизации ввода-вывода.

В качестве примера рассмотрим простую программу планирования предписаний,  которая позволяет обращаться к нескольким предписаниям.  При каждом обращении предписание удаляется из списка и на экран выводится следующее предписание.  Для простоты в программе используется массив символьных строк для управления событиями.
Описание предписания ограничивается 80 символами и число предписаний не должно превышать 100. Прежде всего в этой программе планирования должны быть предусмотрены процедура постановки в очередь и процедура выборки из очереди.  Эти процедуры приводятся ниже и даются необходимые описания глобальных переменных и типов данных.

     const
       MAX_EVENT = 100;

     type
       EvtType = string[80];
       var
         event: array[1..MAX_EVENT] of EvtType;
         spos, rpos: integer;

       {добавить в очередь}
       procedure Qstore(q:EvtType);
       begin
         if spos=MAX_EVENT then
           WriteLn('List full')
         else
         begin
           event[spos]:=q;
           spos:=spos+1;
         end;
     end; {конец процедуры постановки в очередь}

     { выборка объекта из очереди }
     function Qretrieve:EvtType;
     begin
       if rpos=spos then
       begin
         WriteLn('No appointments scheduled.');
         Qretrieve := '';
       end else
       begin
         rpos:=rpos+1;
         Qretrieve := event[rpos-1];
       end;
     end; { конец процедуры выборки из очереди }

В работе этих функций используются три глобальные переменные:  "spos",  которая содержит индекс следующего свободного элемента;  "rpos",  которая содержит индекс следующего выбираемого элемента и "event",  которая представляет собой массив символьных строк с описанием предписаний.  Переменные "spos" и "rpos" должны быть установлены в нулевое значение до первого обращения к процедурам постановки в очередь и выборки из очереди.

В этой программе процедура постановки в очередь помещает новые события в конец списка и делает проверку заполнения списка.
Функция выборки из очереди выбирает события из очереди при необходимости их обработки. Когда планируется новое событие, переменная "spos" увеличивается на единицу, а когда событие завершается, то увеличивается на единицу переменная "rpos".  Фактически переменная "rpos" преследует переменную "spos" в проходах по очереди.
Этот процесс иллюстрируется на рис.5.  Если значение указателя свободного места совпадает со значением указателя выбираемого элемента,  то это означает,  что в очереди нет событий.  Следует помнить,  что хотя функция выборки элемента из очереди в действительности не нарушает информацию в очереди,  повторный доступ к ней невозможен и фактически она исчезает.

Ниже приводится целиком программа,  осуществляющая простое планирование предписаниями. Вы можете усовершенствовать эту программу по собственному желанию.