SHPORA.net :: PDA

[ Back ]

Järjekord (queue)

FIFO - First In First Out

Järjekorra omadused:

1. dünaamiline struktuur (elementide arv on muutuv)

2. elemendid on sama tüüpi

3. elementide järjestus on oluline

4. juurdepääs on ainult esimesena lisatud elemendile (front); "lisamine" lisab lõppu ja "võtmine" eemaldab algusest (järjekorra metafoor)

5. tavaliselt realiseeritavad operatsioonid: tühja järjekorra loomine, lisamine, võtmine, alatäitumise (underflow) kontroll (et vältida tühjast järjekorrast võtmist), mõne realisatsiooni korral ka ületäitumise (overflow) kontroll (kas on "ruumi" lisamiseks), vahendid järjekorra läbivaatamiseks (näit. iteraatorid vms.)



Keeles Java võib järjekorra realisatsiooni luua klassi java.util.LinkedList spetsialiseerides (baseerub topeltseotud ahelal).



Näiteid järjekorra kasutamise kohta: ressursside jagamine (printer), tegevuste planeerimine, graafi läbimine

Eelistusjärjekord



Järjekord, milles on olulised elementide (võtmete) väärtused. Prioriteetidega järjekord. "Lisamine" on sisuliselt hulgateoreetiline lisamine ja "võtmine" on vähima (suurima) võtmeväärtusega elemendi eemaldamine. Kui prioriteedid on staatilised (ei muutu elemendi järjekorras olemise ajal), siis saab "lisamise" teha pistemeetodi abil "Õigesse kohta".

Muutuvate eelistustega järjekord



Kui elemendi prioriteet võib elemendi järjekorras olemise ajal dünaamiliselt muutuda (niisugust järjekorda nim. muutuvate eelistustega järjekorraks), siis tuleb "võtmine" realiseerida järjekorra läbivaatusena ("lisamine" on selle eest lihtne). Teine võimalus on kajastada iga prioriteedimuutust kohe järjekorras, aga see ei pruugi olla hea lahendus (näiteks kui muutusi on palju, aga võtmisi vähe).