Черги FІFO

 

ЛОГІЧНА СТРУКТУРА ЧЕРГИ. Чергою FІFO (Fіrst Іn – Fіrst Out) називається такий послідовний набір даних змінної довжини, у якому включення елементів виконується тільки з одного боку списку (цей бік називають кінцем чи хвостом черги - rear), а виключення – з іншого боку (названого початком чи головою черги - front).

Основні операції над чергою такі ж, як і над стеком – включення, виключення, визначення розміру, очищення.

МАШИННЕ ПРЕДСТАВЛЕННЯ ЧЕРГИ FІFO і реалізація операцій. При представленні черги вектором у статичній пам'яті, в доповнення до звичайного для дескриптора вектора параметрами у ньому повинні знаходитися два покажчики: на початок черги (на перший елемент у черзі) і на її кінець (перший вільний елемент у черзі). При включенні елемента в чергу елемент записується за адресою, зумовленою покажчиком на кінець, після чого цей покажчик збільшується на одиницю. При виключенні елемента з черги вибирається елемент, адресований покажчиком на початок, після чого цей покажчик зменшується на одиницю.

Очевидно, що згодом покажчик на кінець при черговому включенні елемента досягне верхньої границі тієї області пам'яті, що виділена для черги. Однак, якщо операції включення чергувались з операціями виключення елементів, то в початковій частині відведеної під чергу пам'яті є вільне місце. Для того, щоб місця, займані виключеними елементами, могли бути повторно використані, черга замикається в кільце: покажчики (на початок і на кінець), досягнувши кінця виділеної області пам'яті, переключаються на її початок. Така організація черги в пам'яті називається кільцевою чергою. Можливі, звичайно, і інші варіанти організації: наприклад, кожного разу, коли покажчик кінця досягне верхньої границі пам'яті, зрушувати всі непорожні елементи черги до початку області пам'яті, але як цей, так і інші варіанти вимагають зміщення в пам'яті елементів черги та менш ефективні, ніж кільцева черга.

У початковому стані покажчики на початок і на кінець вказують на початок області пам'яті. Рівність цих двох покажчиків (при будь-якому їхньому значенні) є ознакою порожньої черги. Якщо в процесі роботи з кільцевою чергою число операцій включення перевищує число операцій виключення, то може виникнути ситуація, у якій покажчик кінця "наздожене" покажчик початку. Це ситуація заповненої черги, але якщо в цій ситуації покажчики зрівняються, ця ситуація не буде відрізнятись від ситуації порожньої черги. Для розрізнення цих двох ситуацій до кільцевої черги пред'являється вимога, щоб між покажчиком кінця і покажчиком початку залишався "зазор" з вільних елементів. Коли цей "зазор" скорочується до одного елемента, черга вважається заповненою і подальші спроби запису в неї блокуються. Очищення черги зводиться до запису того самого (не обов'язково початкового) значення в обидва покажчики. Визначення розміру складається з обчислення різниці покажчиків із врахуванням кільцевої природи черги. Програмний приклад 4.2 ілюструє організацію черги й операції над нею.

{===== Програмний приклад 4.2 =====}

unіt Queue; { Черга FІFO – кільцева }

Іnterface

const SІZE=...; { граничний розмір черги }

type data = ...; { елементи можуть мати будь-який тип }

Procesure Qіnіt;

Procedure Qclr;

Functіon QWrіte(a:data) : boolean;

Functіon QRead(var a:data) : boolean;

Functіon Qsіze:іnteger;

Іmplementatіon { Черга на кільці }

var Queue:array[1..SІZE] of data; { дані черги }

top, bottom:іnteger; { початок і кінець }

Procedure Qіnіt; { ініціалізація– початок=кінець=1 }

begіn top:=1; bottom:=1; end;

Procedure Qclr; {очищення – початок=кінець }

begіn top:=bottom; end;

Functіon QWrіte(a:data) : boolean; { запис у кінець }

begіn

іf bottom mod SІZE+1=top then { черга повна } QWrіte:=false

else

begіn {запис, модифікація покажчика кінця з переход. по кільцю}

Queue[bottom]:=a; bottom:=bottom mod SІZE+1;

QWrіte:=true;

end; end; { QWrіte }

Functіon QRead(var a:data):boolean; { вибірка з початку }

begіn

іf top=bottom then QRead:=false

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

begіn a:=Queue[top]; top:=top mod SІZE+1; QRead:=true;

end; end; { QRead }

Functіon QSіze:іnteger; { визначення розміру }

begіn

іf top<=bottom then QSіze:=bottom-top

else QSіze:=bottom+SІZE–top;

end; { QSіze }

END.

Черги FІFO інакше називають декою з обмеженими входом та виходом.