Операций

При представлении очереди вектором в статической памяти в

дополнение к обычным для дескриптора вектора параметрам в нем

должны находиться два указателя: на начало очереди (на первый

элемент в очереди) и на ее конец (первый свободный элемент в оче-

реди). При включении элемента в очередь элемент записывается по

адресу, определяемому указателем на конец, после чего этот указа-

тель увеличивается на единицу. При исключении элемента из очереди

выбирается элемент, адресуемый указателем на начало, после чего

этот указатель уменьшается на единицу.

Очевидно, что со временем указатель на конец при очередном

включении элемента достигнет верхней границы той области памяти,

которая выделена для очереди. Однако, если операции включения че-

редовались с операциями исключения элементов, то в начальной час-

ти отведенной под очередь памяти имеется свободное место. Для то-

го, чтобы места, занимаемые исключенными элементами, могли быть

повторно использованы, очередь замыкается в кольцо: указатели (на

начало и на конец), достигнув конца выделенной области памяти,

переключаются на ее начало. Такая организация очереди в памяти

называется кольцевой очередью. Возможны, конечно, и другие вари-

анты организации: например, всякий раз, когда указатель конца

достигнет верхней границы памяти, сдвигать все непустые элементы

очереди к началу области памяти, но как этот, так и другие вари-

анты требуют перемещения в памяти элементов очереди и менее эф-

фективны, чем кольцевая очередь.

В исходном состоянии указатели на начало и на конец указыва-

ют на начало области памяти. Равенство этих двух указателей (при

любом их значении) является признаком пустой очереди. Если в про-

цессе работы с кольцевой очередью число операций включения превы-

шает число операций исключения, то может возникнуть ситуация, в

которой указатель конца "догонит" указатель начала. Это ситуация

заполненной очереди, но если в этой ситуации указатели сравняют-

ся, эта ситуация будет неотличима от ситуации пустой очереди. Для

различения этих двух ситуаций к кольцевой очереди предъявляется

требование, чтобы между указателем конца и указателем начала ос-

тавался "зазор" из свободных элементов. Когда этот "зазор" сокра-

щается до одного элемента, очередь считается заполненной и даль-

нейшие попытки записи в нее блокируются. Очистка очереди сводится

к записи одного и того же (не обязательно начального) значения в

оба указателя. Определение размера состоит в вычислении разности

указателей с учетом кольцевой природы очереди.

Программный пример 4.3 иллюстрирует организацию очереди и

операции на ней.

{==== Программный пример 4.3 ====}

unit Queue; { Очередь FIFO - кольцевая }

Interface

const SIZE=...; { предельный размер очереди }

type data = ...; { эл-ты могут иметь любой тип }

Procesure QInit;

Procedure Qclr;

Function QWrite(a: data) : boolean;

Function QRead(var a: data) : boolean;

Function Qsize : integer;

Implementation { Очередь на кольце }

var QueueA : array[1..SIZE] of data; { данные очереди }

top, bottom : integer; { начало и конец }

Procedure QInit; {** инициализация - начало=конец=1 }

begin top:=1; bottom:=1; end;

Procedure Qclr; {**очистка - начало=конец }

begin top:=bottom; end;

Function QWrite(a : data) : boolean; {** запись в конец }

begin

if bottom mod SIZE+1=top then { очередь полна } QWrite:=false

else begin

{ запись, модификация указ.конца с переходом по кольцу }

Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;

end; end; { QWrite }

Function QRead(var a: data) : boolean; {** выборка из начала }

begin

if top=bottom then QRead:=false else

{ запись, модификация указ.начала с переходом по кольцу }

begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;

end; end; { QRead }

Function QSize : integer; {** определение размера }

begin

if top<=bottom then QSize:=bottom-top

else QSize:=bottom+SIZE-top;

end; { QSize }

END.