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

Очереди

При динамической реализацииосновой очереди является линейный односвязный список. Однако, в отличие от динамического стека, который определяется одним указателем (на вершину), для работы с очередью необходимы два указателя: на голову очереди и на ее хвост. Поэтому для определения очереди возьмем запись (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;

Дата добавления: 2014-01-20