Eilė (duomenų struktūra)

Eilė – duomenų struktūra, veikianti FIFO principu. Į eilę elementai dedami ta pačia tvarka, kuria yra iš jos imami. Savo veikimu primena eilę parduotuvėje: pirmas prie kasos atėjęs žmogus aptarnaujamas pirmiausiai, o paskutinis į eilę atsistojęs – paskiausiai.

Eilės veikimo principas

Eilės veikimo pavyzdįs, kai į ją pirma įdedami skaičiai 1, 2, 3, 4, 5, 6, o tada jie paimami

Eilės plačiai naudojamos programavime, kai reikia buferizuoti duomenis arba tiesiog vykdyti asinchroninį duomenų apdirbimą (pvz., tinklo programose).

Įprastinė eilė vadinama garbinga (angl. fair), nes ji pirmiausia grąžina „aptarnauti“ ilgiausiai laukusį (seniausiai padėtą) elementą. Kartais naudojamos ir „negarbingos“ realizacijos, kur elementų grąžinimo tvarka nėra garantuota. Griežtą grąžinimo tvarką sunku užtikrinti konkurentinėse eilėse, kurių algoritmai turi būti neblokuojant vienu metu vykdomi keleto lygiagrečių gijų.

Eilė gali turėti maksimalią leistiną talpą. Jei naujai pridedamas elementas viršija šios talpos ribas, paprastos realizacijos tai gali iškart interpretuoti kaip klaidą, tačiau yra lygiagretaus programavimo algoritmai, kurie numatytą laiką laukia, jog galbūt tuo metu kita gija vieną eilės elementų pašalins, sukurdama vietos naujam.

Jei eilė tuščia, reikšmės paėmimo metodas gali grąžinti sutartą reikšmę „joks“ (null). Tačiau lygiagrečiam programavimui skirtos eilės gali turėti metodą, skirtą pristabdyti elemento klausiančią giją tol, kol kitos gijos eilės nepapildys vienu ar daugiau naujais elementais.

Įprastinė eilė paprastai gali veikti tik jei ja vienu metu manipuliuoja viena gija. Sinchronizuota eilė pati užtikrina, jog visomis esminėmis jos duomenų stuktūromis vienu metu manipuliuos tik viena gija (kol vienoje gijoje vykdomas tokios eilės metodas, kitos gijos, besikreipiančios į eilės metodus, pristabdomos). Konkurentinės eilės algoritmas yra toks, jog duomenų struktūromis gali vienu metu saugiai manipuliuoti ir daug gijų.

Eilės neretai realizuojamos tiesinių sąrašų pagrindu. Fiksuotos didžiausios talpos eilės taip pat kuriamos žiedinio buferio pagrindu, kurį galima įsivaizduoti kaip žiedo pavidalo duomenų struktūrą kur yra duomenų turinti sritis. Nauji elementai pridedami viename srities gale, jau perskaitytų (ir iš eilės pašalintų) elementų vietos kitame gale laikomos laisvais. Naudojama sritis nuolat juda žiediniame buferyje ratu.

Šaltiniai

Šiame straipsnyje naudojami diskutuotini terminai. Daugiau apie kompiuterinius terminus skaitykite žodynėlyje.

Vikižodynas