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) при добавлении в
