Динамическая реализация очереди

При динамической реализацииосновой очереди является линейный односвязный список. Однако, в отличие от динамического стека, который определяется одним указателем (на вершину), для работы с очередью необходимы два указателя: на голову очереди и на ее хвост. Поэтому для определения очереди возьмем запись (record), содержащую в качестве полей эти два указателя. И тогда при работе с очередью последняя будет характеризоваться только одним параметром. Это описание очереди и основные операции приведены в листинге 9.16.

Листинг 9.16. Очередь, реализованная динамически

type

TInfo = integer;

PNode = ^TNode;

TNode = record

Info: TInfo;

Next: PNode

end;

TQueue=record

Head, // голова очереди

Tail: PNode // хвост очереди

end;

TFile = text;

procedure InitQueue(var q: TQueue); // инициализация очереди

begin

q.Head:=Nil;

end;

function QueueIsEmpty(q: TQueue): Boolean;

// проверка на пустоту

begin

Result:=q.Head=Nil

end;

procedure InQueue(var q: TQueue; x: TInfo);

var

p: PNode;

begin

New(p);

with p^ do begin

Info:=x;

Next:=Nil

end;

if QueueIsEmpty(q) then // если очередь пуста

with q do begin // создаем первый элемент очереди

Head:=p; Tail:=p

end

else // добавляем элемент в конец очереди

with q do begin

Tail^.Next:=p;

Tail:=p

end;

end;

function OutQueue(var q: TQueue):TInfo; // взять из очереди

var

p: PNode;

begin

with q do begin

Result:=Head.Info;

p:=Head;

Head:=Head.Next;

Dispose(p)

end;

end;

Примечание

Функция OutQueue — взятия элемента из очереди — вызывается только в том случае, если очередь не пуста. Обработка пустой очереди производится в вызывающем контексте.

В качестве примера использования очереди рассмотрим следующую задачу.

Завод скоропортящейся продукции, например, глазированных сырков, имеет склад, куда поступает готовая продукция: коробки с сырками. В магазин по заявке следует отправить первой ту коробку, которая раньше всех поступила на склад. Но если заявок поступило много и склад опустел, то вывозить сырки можно сразу из цеха, минуя склад. Незаявленная продукция остается на складе. В отчете требуется представить характеристики коробок, отправленных на продажу.

Рассмотрим модель этой задачи: дан файл целых чисел, положительные (коробки с сырками) и отрицательные (заявки из магазинов) распределены произвольно, однако известно, что отрицательных чисел меньше, чем положительных. Напечатать в порядке следования столько положительных чисел из файла, сколько в нем отрицательных.

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

Блок-схема алгоритма обработки числа, поступившего из файла, приведена на рис. 9.13.

Рис. 9.13. Блок-схема алгоритма обработки числа, поступившего из файла

Полностью алгоритм обработки чисел, поступающих из файла, с использованием очереди, реализован в виде процедуры PositivePrint и приведен в листинге 9.17

Листинг 9.17. Использование очереди при обработке чисел, поступающих из файла

type

Tfile: file of integer;

procedure PositivePrint(var f:TFile);

var q: TQueue;

i, // число из файла

iq : TInfo; // число из очереди

cnt: integer;

begin

InitQueue(q); // инициализация очереди

cnt:=0; // инициализация счетчика

reset(f);

while not eof(f) do begin // пока не конец файла

read(f,i);

if i<0 then begin // число отрицательное (заявка)

if QueueIsEmpty(q) then cnt:=cnt+1

else write(OutQueue(q))

end

else // число положительное (коробка с продукцией)

if cnt=0 then InQueue(q,i)

else begin

write(i); cnt:=cnt-1;

end;

end;

end;