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 
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 
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 
 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 
 Pino
 Pakka
 Prioriteettijono

 Lähteet 



Luokka:Ohjelmointi
Luokka:Tietorakenteet