Jono
Wikipedia
- Matematiikassa lukujonoa kutsutaan usein jonoksi.
Jono (engl. queue) on tietojenkäsittelytieteessä käytetty yksiulotteinen listamainen tietorakenne, joka toimii niin sanotulla FIFO-periaatteella (First In First Out). Jono toimii siis samalla tavalla kuin reaalimaalmassakin: sillä on kaksi päätä ja alkion poisto tapahtuu aina toisesta päästä kuin mistä se on lisätty. Näin alkiot käsitellään vuorotellen siten, että kauimmin jonossa ollut alkio käsitellään ensimmäisenä. Jonoa voi verrata esimerkiksi kaupan kassajonoon. Yleensä jonoa käytetäänkin varastoimaan prosessointia odottavia alkioita.
Sisällysluettelo |
[muokkaa] Toteutus
Jono toteutetaan yleensä joko linkitettynä listana tai taulukkona. Linkitetyn rakenteen etuna on se, että jonon pituus voi muuttua vapaasti ilman rakenteen uusimista. Toisaalta haittapuolena jatkuva muistinvaraaminen saattaa heikentää suorituskykyä. Lisäksi linkit alkiosta toiseen vievät jonkin verran tilaa.
Taulukolla toteutetun jonon pituudella on taulukon koosta johtuva yläraja, mikä monissa tapauksissa ei haittaa mutta voi joskus koitua ongelmaksi. Ongelma voidaan myös kiertää vaihtamalla käyttöön isompi taulukkoa aina ylärajan tullessa vastaan, mutta tämän on suhteellisen raskas operaatio. Taulukko vie myös käytännössä aina jonkin verran hukkatilaa.
[muokkaa] Operaatiot
Jonon rajapinta koostuu seuraavista operaatioista:
- enqueue: lisää alkion jonon viimeiseksi
- dequeue: poimii jonon ensimmäisen alkion
- empty: tarkistaa, onko jono tyhjä
Edellä mainitut jono-operaatiot suoriutuvat yleensä vakioajassa.
[muokkaa] Käyttökohteita
- Puskurinmuisti toteutetaan usein jonona. Puskureita käytetään yleensä sisään tulevan (tai ulos menevän) viestiliikenteen väliaikaiseen tallentamiseen.
- Verkkojen läpikäyntialgoritmeissa jonoa saatetaan käyttää seuraavaksi käsittelyä odottavien solmujen tallentamiseen.
