В этом случае для хранения значений элементов очереди используется массив размерностью SizeQueue. Необходимо еще два указателя: Голова, указывающая на первый элемент в очереди, и Хвост — на элемент массива, в который можно поместить очередное значение. Если очередь пуста, то Голова и Хвост указывают на один и тот же элемент массива. Поскольку в процессе работы при помещении значений в очередь массив заполняется с правой стороны, а при извлечении из очереди — освобождается слева, то имеет смысл сделать массив кольцевым. Это означает, что когда значение помещается в последний элемент массива, указатель Хвост перемещается к первому элементу массива (аналогично для Головы). Таким образом, Хвост может быть левее Головы.
Очередь пуста — это значит, что в массиве не содержится ни одного значения. Очередь может стать пустой в процессе работы, при этом Голова и Хвост будут указывать на один и тот же элемент, но не обязательно на первый элемент массива. Поэтому для проверки очереди на пустоту необходим еще счетчик элементов очереди, который равен нулю, если очередь пуста, и имеет значение SizeQueue, если очередь забита полностью.
В листинге 9.18 приведен модуль работы с очередью, реализованной с помощью массива.
Листинг 9.18. Очередь, реализованная с помощью массива
const
SizeQueue=6; // размер очереди
type
Index = 0..SizeQueue-1;
TInfo = integer;
TQu = array[0..SizeQueue-1] of TInfo;
TQueue=record
Head, // указатель на голову очереди
Tail : Index; // указатель на хвост очереди
Queue: TQu; // очередь
full : integer; // количество элементов в очереди
end;
procedure InitQueue(var q:TQueue);
//инициализация очереди: голова и хвост совпадают, элементов нет
begin
with q do begin
Head:=0; Tail:=0; full:=0;
end;
end;
function QueueIsEmpty(q:TQueue): Boolean;
// проверка очереди на пустоту
begin
Result:=q.full=0;
end;
procedure InQueue(var q:TQueue; x:TInfo);
// добавление в очередь:
// Tail указывает на элемент в массиве, куда поместить
begin
with q do begin
Queue[Tail]:=x; full:=full+1;
Tail:=(Tail+1) mod SizeQueue // переход к следующему
// элементу с учетом кольца
end
end;
function OutQueue(var q:TQueue): TInfo;
// взять из очереди: Head указывает на элемент, который брать
begin
with q do begin
Result:=Queue[Head]; full:=full-1;
Head:=(Head+1)mod SizeQueue // смещение головы очереди
// с учетом кольца
end;
end;
Теперь создадим проект, иллюстрирующий работу очереди на массиве. Форма проекта приведена на рис. 9.14.
Рис. 9.14. Форма для иллюстрации очереди, реализованной с помощью массива
На форме выставлены компоненты:
q компонент Edit для ввода целого значения;
q кнопка В очередь; помещающая число в очередь;
q компонент StringGrid, в верхней строке которого отображается содержимое очереди, а в нижней показаны положения указателей очереди. Если очередь пуста, то указатели показывают на одну и ту же ячейку;
q компонент Memo, в которое выводятся значения, взятые из очереди;
q кнопка Из очереди, при нажатии на которую из очереди берется элемент и выводится в поле Memo;
q кнопка Очистить, очищающая ячейки StringGrid и инициализирующая очередь для новой работы.
q Рассмотрим обработчики событий при работе с формой Очередь.
q Обработчик события Click кнопки Очистить инициализирует очередь, очищает ячейки таблицы и компоненты Edit и панель вывода:
