Eilė (duomenų struktūra)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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 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ų.

Kartais eilės realizuojamos tiesinių sąrašų pagrindu.

[taisyti] Realizacija naudojant masyvą

Tai gana paprasta realizacija. Dažniausiai naudojamas fiksuoto dydžio masyvas. Tuo atveju atminties naudojimas yra gana neefektyvus. Reikalingi šie kintamieji:

• masyvas M, bei jo dydis N
• eilės pradžios indeksas H bei pabaigos indeksas T

Pradžia:

 H ← 0
 T ← 0

Tikrinimas ar eilė tuščia:

 if T = H then
   eilė tuščia

Reikšmės V įdėjimas į eilę:

 M[T] ← V
 T ← T+1
 if T = N then
   T ← 0

Reikšmės V išėmimas iš eilės:

 V ← M[H]
 H ← H+1
 if H = N then
   H ← 0

Naudojant T ir H saugoma atmintis, leidžiant eilės pabaigai atsidurti prieš pradžią. Taip pat reikėtų tikrinti ar eilė nepersipildo, t.y. ar po T padidinimo, T „neperlipa“ H.

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