jonorakenteita

Jonorakenteita ovat tietorakenteita, joiden keskeinen ominaisuus on että alkioiden käsittely noudattaa FIFO-periaatetta: ensimmäisenä sisään tullut alkio poistuu ensimmäisenä. Tämä tekee jonoista luotettavan työkalun tehtävien tasaiselle käsittelylle, dataa bufferöidessä sekä tapahtumien ja viestien järjestämisessä. Jonorakenne voidaan toteuttaa useilla tavoilla, yleisimpiä ovat linkitetty lista ja taulukko, usein kiertäen tai rengasbufferina (circular buffer), mikä mahdollistaa tehokkaan tilankäytön ja nopeat operoinnit.

Tyyppejä ja muunnelmia ovat FIFO-jonot, joissa lisäys ja poisto tapahtuvat päistä varten, sekä deque (double-ended queue), joka sallii alkioiden sekä lisäyksen että poiston molemmista päistä. Prioriteettijono (priority queue) poistaa kuitenkin alkiot prioriteetin mukaan, ei ainoastaan saapumisjärjestyksen mukaan; tällöin korkeamprioriteettiset elementit voivat poistua ennen matalampia. Toteutuksina voivat olla sekä linkitettyjä listoja että taulukoita, ja ne voivat olla kiinteäkapasiteettisia tai dynamiikkaa skaalavia.

Perusoperaatiot muodostuvat enqueue- eli lisäys-, dequeue- eli poisto-, sekä peek/first, size ja isEmpty -toiminnoista. Aikavaativuus riippuu toteutuksesta: monissa tarkoituksissa enq/deq ovat O(1) aikaisia, erityisesti rengasbufferissa tai yhdistetyssä listassa; taulukkoon pohjautuvissa ratkaisuissa kapasiteetin hallinta voi aiheuttaa tilapäistä uudelleenvarastointia. Monimutkaisemmissa käyttötapauksissa, kuten monisäikeisissä ympäristöissä, tarvitaan synkronointia ja mahdollisesti estäviä tai epästehenden ratkaisuja.

Sovelluksia ovat tehtävien aikataulutus, I/O- ja verkkovirtojen hallinta, tulostusjonot sekä laajentuneet virta- ja tapahtumajärjestelmät sekä laajat hakumenetelmät kuten BFS.