Linijinė ir ciklinė eilė: struktūra, veikimo principai ir praktinis taikymas

Eilės – tai bet kurio skysčio srauto modeliai, tačiau informatikos kontekste dažniausiai aptinkamos linijinės ir ciklinės eilės. Šių dviejų tipų struktūra ir našumas skiriasi, todėl, pavyzdžiui, kuriant didelės apimties interneto serverių klasterį, architektas turi apsispręsti, ar naudoti linijinę, ar ciklinę eilę. Sprendimas įtakoja, kaip nukreipiamos užklausos į serverius ir kaip šie serveriai yra sujungti.

Kasdieniai pavyzdžiai

Norint greitai suprasti pagrindinį skirtumą tarp linijinės ir ciklinės eilės, įsivaizduokime eilę restorane. Kai stalas yra paruoštas, žmonės eilės pradžioje sėdi, o nauji lankytojai stovi gale – tai linijinė eilė. Ciklinė eilė primena muzikos kėdes: nauji dalyviai gali užimti bet kurią laisvą vietą, kol yra laisva kėdė.

Eilių struktūros palyginimas

Linijinė eilė – tai tiesiška linija, kurioje elementai išsidėsto vienas po kito, turėdami aiškų pradžios ir pabaigos tašką. Užduotys atliekamos FIFO (pirmas įėjo – pirmas išėjo) principu.

Ciklinė eilė – elementai sujungti į apskritimą: paskutinis elementas susijungia su pirmuoju, sudarydamas uždarą ciklą. Ši struktūra nereiškia, kad užduotys bus vykdomos tą pačią tvarka, kaip jos įdėtos.

Įterpimas ir šalinimas

Linijinėje eilėje nauja užduotis pridedama gale, o šalinama priekyje. Sistema nuolat tikrina, ar eilė neperpildyta („queue full“) ir ar ji nėra tuščia („queue empty“). Ciklinėje eilėje įterpimas ir šalinimas gali vykti bet kurioje vietoje, nepriklausomai nuo sekos.

Prižiūrėjimo kaštai ir laikas

Linijinėje eilėje, kad įterptume elementą gale, reikia atlaisvinti vietą priekyje ir perkelti visus tarpinius elementus viena vieta į priekį – tai laiko ir skaičiavimo išteklių sąnaudų reikalauja. Ciklinėje eilėje įterpimas ir šalinimas gali vykti vienu metu, todėl procesas yra efektyvesnis.