Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в 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)?