Шрифт:
Листинг 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)?
Решение заключается в использовании кольцевой очереди. Представьте себе приемную у стоматолога. Как правило, это комната со стульями вдоль стен. В отличие от очереди в супермаркете, где вы подходите к началу очереди, толкая тележку, в приемной вы сидите на стуле. При вызове очередного пациента все остальные не встают и не переходят на соседний стул. Просто начало очереди - какой-то тяжело объяснимый атрибут (ага, такое впечатление, что в Америке нет очередей к стоматологу...) - переходит к другому человеку. При вызове пациента этот атрибут передается следующему пациенту, и он становится "началом" очереди. Таким образом, никто не встает со стульев, просто некоторым образом (возможно, с помощью ассистента стоматолога) определяется первый пациент в очереди. Подобного рода организация называется круговой очередью.
Для реализации круговой очереди на основе массива введем переменную, которая будет содержать индекс первого элемента в очереди. Кроме того, введем еще одну переменную, которая будет указывать на конец очереди. Начнем с массива с некоторым определенным количеством элементов (размер будем определять на основе максимально возможного количества элементов в очереди) и установим индекс начального элемента равным индексу конечного элемента. Фактически, это равенство означает, что очередь пуста.