Постановка элемента в очередь эквивалентна установке значения элемента, на который указывает индекс конца очереди, равным значению записываемого в очередь элемента. После этого значение индекса конца очереди нужно увеличить на 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: