Jono (tietojenkäsittelytiede)
- Matematiikassa lukujonoa kutsutaan usein jonoksi.
Jono (engl. queue) on tietojenkäsittelytieteessä käytetty abstrakti tietotyyppi, jonka lisäys- ja poisto-operaatiot toimivat niin sanotulla FIFO-periaatteella (First In First Out). Tämä vastaa todellisuutta: jonolla on kaksi päätä, ja alkio pääsee pois 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 käsittelyä odottavia alkioita.
Operaatiot[muokkaa | muokkaa wikitekstiä]
Jonon rajapinta koostuu ainakin seuraavista operaatioista:
- enqueue: lisää alkion jonon viimeiseksi
- dequeue: poimii (eli poistaa ja palauttaa) jonon ensimmäisen alkion
- empty: tarkistaa, onko jono tyhjä
Edellä mainitut jono-operaatiot saadaan suoriutumaan vakioajassa.
Toteutus[muokkaa | muokkaa wikitekstiä]
Jono toteutetaan yleensä joko linkitettynä listana tai taulukkona. Linkitetyn rakenteen etuna on se, että jonon pituus voi muuttua vapaasti ilman rakenteen uusimista. 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 kiertää vaihtamalla käyttöön isompi taulukko aina ylärajan tullessa vastaan, mutta tämä on suhteellisen raskas operaatio. Taulukko vie myös käytännössä aina hieman hukkatilaa.
Käyttökohteita[muokkaa | muokkaa wikitekstiä]
- Puskurimuisti 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.
Katso myös[muokkaa | muokkaa wikitekstiä]
Lähteet[muokkaa | muokkaa wikitekstiä]
- Matti Luukkainen ja Matti Nykänen: 58131: Tietorakenteet 8. tammikuuta 2007. Helsingin yliopisto. Arkistoitu 13.6.2007. Viitattu 13. syyskuuta 2007.
- Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: ”Section 10.1: Stacks and queues”, Introduction to Algorithms – 2nd ed., s. 200–204. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7.