Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Листинг 3.28. Метод Enqueue класса TtdQueue

procedure TtdQueue.Enqueue(aItem : pointer);

var

Temp : PslNode;

begin

Temp := PslNode(SLNodeManager.AllocNode);

Temp^.slnData := aItem;

Temp^.slnNext := nil;

{добавить новый узел в конец списка и переместить указатель конечного узла на только что вставленный узел}

FTail^.slnNext := Temp;

FTail := Temp;

inc(FCount);

end;

Метод Dequeue ничуть не сложнее. Сначала он проверяет список на наличие в нем элементов, а затем, пользуясь алгоритмом "удалить после" фиктивного начального узла FHead, удаляет из списка первый узел. Перед освобождением узла с помощью диспетчера узлов метод Dequeue возвращает данные. После выполнения метода количество элементов в списке уменьшается на единицу. Вот здесь и начинается самое интересное. Представьте себе, что из очереди снимается один единственный имеющийся в ней элемент. До выполнения операции Dequeue указатель FTail указывал на последний узел списка, который был одновременно и первым. После снятия элемента с очереди первый узел будет отсутствовать, но указатель FTail все еще указывает на него. Нам нужно сделать так, чтобы после удаления узла в списке FTail указывал на фиктивный начальный элемент. Если же в списке до удаления присутствовало несколько элементов, указатель будет указывать на действительный последний узел.

Листинг 3.29. Метод Dequeue класса TtdQueue

function TtdQueue.Dequeue : pointer;

var

Temp : PslNode;

begin

if (Count = 0) then

qError(tdeQueueIsEmpty, 'Dequeue');

Temp := FHead^.slnNext;

Result := Temp^.slnData;

FHead^.slnNext := Temp^.slnNext;

SLNodeManager.FreeNode(Temp);

dec(FCount);

{если после удаления элемента очередь опустела, переместить указатель последнего элемента на фиктивный начальный узел}

if (Count = 0) then

FTail := FHead;

end;

Остальные методы, Clear, Examine и IsEmpty, еще проще.

Листинг 3.30. Методы Clear, Examine и IsEmpty класса TtdQueue

procedure TtdQueue.Clear;

var

Temp : PslNode;

begin

{удалить все узлы за исключением начального; при возможности освободить все данные}

Temp := FHead^.slnNext;

while (Temp <> nil) do

begin

FHead^.slnNext := Temp^.slnNext;

if Assigned(FDispose) then

FDispose(Temp^.slnData);

SLNodeManager.FreeNode(Temp);

Temp := FHead^.slnNext;

end;

FCount := 0;

{теперь очередь пуста, установить указатель последнего элемента на начальный узел}

FTail := FHead;

end;

function TtdQueue.Examine : pointer;

begin

if (Count = 0) then

qError(tdeQueueIsEmpty, 'Examine');

Result := FHead^.slnNext^.slnData;

end;

function TtdQueue.IsEmpty : boolean;

begin

Result := (Count = 0);

end;

Полный код класса TtdQueue можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStkQue.pas.

А теперь давайте рассмотрим реализацию очереди на основе массива. Как и раньше, для простоты воспользуемся массивом TList. По крайней мере, в этом случае нам не придется беспокоиться о распределении памяти и увеличении размера массива.

Зная, как реализуется очередь на основе связного списка, первым желанием может быть, для имитации операции постановки в очередь, добавлять элементы в конец экземпляра массива TList с помощью метода Add, а для имитации снятия с очереди - удалять первый элемент с помощью метода метод Delete (или наоборот, вставлять в начало массива, а удалять с конца). Тем не менее, давайте посмотрим, что при этом будет происходить с массивом. При выполнении метода Add ничего интересного не происходит, за исключением тех случаев, когда приходится увеличивать размер массива. Это операция класса O(1) - как раз то, что требуется. Что же касается Delete, то здесь все не так безоблачно. Для реализации операции снятия с очереди из массива TList потребуется удалить первый элемент, что приведет к тому, что все элементы массива переместятся на одну позицию вперед. Такая операция зависит от количества элементов в массиве, т.е. принадлежит к классу O(n). Вот и дождались плохих новостей. Мы не можем поменять местами операции постановки в очередь и снятия с очереди, т.е. мы добавляем только в начало списка и удаляем с его конца. Другими словами, мы все равно получаем операцию класса O(n) при добавлении в начало списка.

-------

В некоторых источниках описанный принцип все же используется для реализации очереди. Более того, класс TQueue в модуле Contnrs, возможно, основан на таком принципе.

-------

В некоторых источниках описанный принцип все же используется для реализации очереди. Более того, класс TQueue в модуле Contnrs, возможно, основан на таком принципе.

Рисунок 3.10. Использование массива для организации очереди

Каким образом можно реализовать очередь на основе массива, чтобы обе базовых операции принадлежали к классу O(1)?

Решение заключается в использовании кольцевой очереди. Представьте себе приемную у стоматолога. Как правило, это комната со стульями вдоль стен. В отличие от очереди в супермаркете, где вы подходите к началу очереди, толкая тележку, в приемной вы сидите на стуле. При вызове очередного пациента все остальные не встают и не переходят на соседний стул. Просто начало очереди - какой-то тяжело объяснимый атрибут (ага, такое впечатление, что в Америке нет очередей к стоматологу...) - переходит к другому человеку. При вызове пациента этот атрибут передается следующему пациенту, и он становится "началом" очереди. Таким образом, никто не встает со стульев, просто некоторым образом (возможно, с помощью ассистента стоматолога) определяется первый пациент в очереди. Подобного рода организация называется круговой очередью.

Для реализации круговой очереди на основе массива введем переменную, которая будет содержать индекс первого элемента в очереди. Кроме того, введем еще одну переменную, которая будет указывать на конец очереди. Начнем с массива с некоторым определенным количеством элементов (размер будем определять на основе максимально возможного количества элементов в очереди) и установим индекс начального элемента равным индексу конечного элемента. Фактически, это равенство означает, что очередь пуста.

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

Снятие элемента с очереди означает возврат значения элемента, на который указывает индекс начала очереди. После этого значение индекса начала очереди увеличивается на 1. Если после увеличения индекса он будет превышать размер массива, установить его равным 0. Очевидно, что перед снятием элемента с очереди необходимо убедиться, что очередь не пуста. Для этого следует проверить, равны ли индексы начала и конца очереди (в случае равенства индексов, очередь пуста).