Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Зная, как реализуется очередь на основе связного списка, первым желанием может быть, для имитации операции постановки в очередь, добавлять элементы в конец экземпляра массива TList с помощью метода Add, а для имитации снятия с очереди - удалять первый элемент с помощью метода метод Delete (или наоборот, вставлять в начало массива, а удалять с конца). Тем не менее, давайте посмотрим, что при этом будет происходить с массивом. При выполнении метода Add ничего интересного не происходит, за исключением тех случаев, когда приходится увеличивать размер массива. Это операция класса O(1) - как раз то, что требуется. Что же касается Delete, то здесь все не так безоблачно. Для реализации операции снятия с очереди из массива TList потребуется удалить первый элемент, что приведет к тому, что все элементы массива переместятся на одну позицию вперед. Такая операция зависит от количества элементов в массиве, т.е. принадлежит к классу O(n). Вот и дождались плохих новостей. Мы не можем поменять местами операции постановки в очередь и снятия с очереди, т.е. мы добавляем только в начало списка и удаляем с его конца. Другими словами, мы все равно получаем операцию класса O(n) при добавлении в начало списка.
-------
В некоторых источниках описанный принцип все же используется для реализации очереди. Более того, класс TQueue в модуле Contnrs, возможно, основан на таком принципе.
-------
В некоторых источниках описанный принцип все же используется для реализации очереди. Более того, класс TQueue в модуле Contnrs, возможно, основан на таком принципе.
Рисунок 3.10. Использование массива для организации очереди
Каким образом можно реализовать очередь на основе массива, чтобы обе базовых операции принадлежали к классу O(1)?
Решение заключается в использовании кольцевой очереди. Представьте себе приемную у стоматолога. Как правило, это комната со стульями вдоль стен. В отличие от очереди в супермаркете, где вы подходите к началу очереди, толкая тележку, в приемной вы сидите на стуле. При вызове очередного пациента все остальные не встают и не переходят на соседний стул. Просто начало очереди - какой-то тяжело объяснимый атрибут (ага, такое впечатление, что в Америке нет очередей к стоматологу...) - переходит к другому человеку. При вызове пациента этот атрибут передается следующему пациенту, и он становится "началом" очереди. Таким образом, никто не встает со стульев, просто некоторым образом (возможно, с помощью ассистента стоматолога) определяется первый пациент в очереди. Подобного рода организация называется круговой очередью.
Для реализации круговой очереди на основе массива введем переменную, которая будет содержать индекс первого элемента в очереди. Кроме того, введем еще одну переменную, которая будет указывать на конец очереди. Начнем с массива с некоторым определенным количеством элементов (размер будем определять на основе максимально возможного количества элементов в очереди) и установим индекс начального элемента равным индексу конечного элемента. Фактически, это равенство означает, что очередь пуста.
Постановка элемента в очередь эквивалентна установке значения элемента, на который указывает индекс конца очереди, равным значению записываемого в очередь элемента. После этого значение индекса конца очереди нужно увеличить на 1. Если после увеличения индекса он будет превышать размер массива, необходимо установить его равным 0, т.е. индексу первого элемента.
Снятие элемента с очереди означает возврат значения элемента, на который указывает индекс начала очереди. После этого значение индекса начала очереди увеличивается на 1. Если после увеличения индекса он будет превышать размер массива, установить его равным 0. Очевидно, что перед снятием элемента с очереди необходимо убедиться, что очередь не пуста. Для этого следует проверить, равны ли индексы начала и конца очереди (в случае равенства индексов, очередь пуста).
И нам осталось рассмотреть еще одну проблему: при постановке элемента в очередь необходимо убедиться, что новое значение индекса конца очереди не равно значению индекса начала очереди. Если равенство соблюдается, значит, очередь полностью заполнена элементами. К сожалению, такая ситуация также означает (по крайней мере, для процедуры снятия с очереди), что очередь пуста. Таким образом, если такая достаточно абсурдная ситуация возникает - пустая очередь эквивалентна заполненной - необходимо увеличить размер массива, перемещая все имеющиеся в массиве элементы и изменяя значения индексов начала и конца очереди.
Интерфейс класса TtdArrayQueue выглядит точно так же, как и интерфейс класса TtdQueue.
Листинг 3.31. Класс TtdArrayQueue
TtdArrayQueue = class private
FCount : integer;
FDispose : TtdDisposeProc;
FHead : integer;
FList : TList;
FName : TtdNameString;
FTail : integer;
protected
procedure aqError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure aqGrow;
public
constructor Create(aDispose : TtdDisposeProc;
aCapacity : integer);
destructor Destroy; override;
procedure Clear;
function Dequeue : pointer;
procedure Enqueue(altem : pointer);
function Examine : pointer;
function IsEmpty : boolean;
property Count : integer read FCount;
property Name : TtdNameString read FName write FName;
end;
Конструктор и деструктор мало чем отличаются от соответствующих методов класса TtdArrayStack.
Листинг 3.32. Конструктор и деструктор класса TtdArrayQueue
constructor TtdArrayQueue.Create( aDispose : TtdDisposeProc;
aCapacity : integer);
begin
inherited Create;
{сохранить процедуру удаления}
FDispose := aDispose;
{создать внутренний массив TList и установить его размер равным aCapacity элементов}
FList := TList.Create;
if (aCapacity <= 1) then
aCapacity := 16;
FList.Count := aCapacity;
end;
destructor TtdArrayQueue.Destroy;
begin
FList.Free;
inherited Destroy;
end;
Самое интересное происходит в методах Enqueue и Dequeue.
Листинг 3.33. Методы Enqueue и Dequeue класса TtdArrayQueue
function TtdArrayQueue.Dequeue : pointer;
begin
{убедиться, что очередь не пуста}
if (Count = 0) then
aqError(tdeQueueIsEmpty, 'Dequeue');
{элемент, снимаемый с очереди, находится в ее начале}
Result := FList[FHead];
{переместить индекс начала очереди и убедиться, что он все еще действителен; уменьшить количество элементов на 1}
FHead := (FHead + 1) mod FList.Count;
dec(FCount);
end;
procedure TtdArrayQueue.Enqueue(aItem : pointer);
begin
{добавить элемент в конец очереди}
FList[FTail] := aItem;
{переместить индекс конца очереди и убедиться, что он все еще действителен; увеличить количество элементов на 1}
FTail := (FTail + 1) mod FList.Count;
inc(FCount);
{если после добавления очередного элемента мы обнаруживаем, что значения индексов начала и конца очереди равны, увеличить размер массива}
if (FTail = FHead) then
aqGrow;
end;
Как видите, снятие элемента с очереди включает возврат элемента, находящегося в позиции с индексом начала очереди, а затем увеличение индекса на 1. Постановка в очередь включает запись элемента в позицию с индексом конца очереди и увеличение индекса на 1. Если конец очереди достигает ее начала, размер массива увеличивается с помощью метода aqGrow:
Листинг 3.34. Расширение размера экземпляра класса TtdArrayQueue
procedure TtdArrayQueue.aqGrow;
var
i : integer;
ToInx : integer;
begin
{увеличить размер списка}
FList.Count := (FList.Count * 3) div 2;
{теперь элементы находятся в конце списка, необходимо восстановить корректный порядок элементов в кольцевой очереди}
if (FHead = 0) then
FTail := FCount else begin
ToInx := FList.Count;
for i := pred(Count) downto FHead do begin
dec(ToInx);
FList[ToInx] := FList[i];
end;
FHead := ToInx;
end;
end;
Приведенный метод является наиболее сложным методом во всем классе. При его вызове очередь заполнена, индекс конца очереди временно равен индексу начала (не забывайте, что это также означает, что очередь пуста), причем необходимо увеличить размер массива TList. Первое, что мы делаем, - увеличиваем размер массива на 50%. После этого нужно исправить кольцевую очередь таким образом, чтобы она правильно учитывала свободное место. Если значение индекса начала очереди равно 0, кольцевая очередь была не круговой, и все что требуется сделать - изменить значение индекса конца очереди. Если же значение индекса начала не равно 0, очередь была "закольцована" внутри массива. Чтобы переходить по элементам в правильном порядке, мы начинаем с индекса начала очереди, доходим до старого конца массива, переходим к началу массива и идем до индекса конца очереди (который равен индексу начала очереди). Теперь у нас имеются дополнительные элементы, которые находятся между старым и новым концом массива. Следовательно, мы должны поместить элементы, находящиеся между началом очереди и старым концом массива таким образом, чтобы они занимали место до нового конца массива. После этого мы получим правильный порядок элементов в кольцевой очереди.
Полный код класса TtdArrayQueue можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStkQue.pas.
Резюме
Эта глава была посвящена связным спискам: как односвязным, так и двухсвязным. Были описаны некоторые проблемы, касающиеся работы стандартного связного списка, и показано, что использование диспетчера узлов повысило быстродействие обеих версий списков. В конце главы мы рассмотрели стеки и очереди и реализовали их на основе связных списков и массивов.
