Модели и структуры данных



Машинное представление очереди FIFO и реализация операций - часть 2


Когда этот "зазор" сокращается до одного элемента, очередь считается заполненной и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (не обязательно начального) значения в оба указателя. Определение размера состоит в вычислении разности указателей с учетом кольцевой природы очереди.

Программный пример 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




Содержание  Назад  Вперед