Jono

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
• Prioriteettijono

Lähteet