Jono on abstrakti tietotyyppi, jossa on ensimmäinen sisään ensimmäinen ulos -elementtien käyttökuri ( FIFO , englanniksi first in, first out ). Elementin lisääminen (jota yleensä merkitään sanalla enqueue - laita jonoon) on mahdollista vain jonon lopussa, näytteenotto - vain jonon alusta (jota kutsutaan yleisesti sanaksi dequeue - poista jonosta), kun valittu elementti poistetaan jonosta.
On olemassa useita tapoja toteuttaa jono ohjelmointikielissä.
Ensimmäinen tapa edustaa jonoa taulukkona ja kaksi kokonaislukumuuttujaa alkavat ja lopettavat.
Yleensä startosoittaa jonon päähän, end elementtiä, joka täytetään, kun uusi elementti tulee jonoon. Kun elementti lisätään jonoon, q[end]uusi jonoelementti kirjoitetaan ja endsitä vähennetään yhdellä. Jos lopun arvo tulee pienemmäksi kuin 1, niin teemme silmukan taulukon ympäri ja muuttujan arvoksi tulee yhtä suuri kuin n. Elementin purkaminen jonosta tapahtuu samalla tavalla: kun elementti q[start]on purettu jonosta, muuttuja startpienennetään yhdellä. Tällaisilla algoritmeilla yksi solu jonosta non aina vapaa (koska nelementtejä sisältävää jonoa ei voida erottaa tyhjästä), jonka kompensoi algoritmien yksinkertaisuus.
Tämän menetelmän edut: pieni muistin säästö on mahdollista verrattuna toiseen menetelmään; helpompi kehittää.
Haitat: Elementtien enimmäismäärää jonossa rajoittaa taulukon koko. Kun se vuotaa yli, se vaatii muistin uudelleenallokoinnin ja kaikkien elementtien kopioimisen uuteen taulukkoon.
Toinen menetelmä perustuu työskentelyyn dynaamisen muistin kanssa. Jono on esitetty lineaarisena listana , jossa elementtien lisääminen/poisto tulee tarkasti sen vastaavista päistä.
Tämän menetelmän edut: jonon kokoa rajoittaa vain muistin määrä.
Haitat: vaikeampi kehittää; tarvitaan enemmän muistia; kun työskentelet tällaisen jonon kanssa, muisti on pirstoutunut; jonotus on hieman hitaampaa.
Jonomenetelmät voidaan toteuttaa kahden pinon S1 pohjalta ja S2alla olevan kuvan mukaisesti:
proseduurijono ( x ): S1.push( x ) dequeue()-funktio: jos S2 on tyhjä: jos S1 on tyhjä: ilmoita virheestä: jono on tyhjä kunnes S1 on tyhjä: S2.push(S1.pop()) return S2.pop()Tämä toteutustapa on kätevin perusta jatkuvan jonon rakentamiseen. .
Jonot on toteutettu lähes kaikissa kehitetyissä ohjelmointikielissä. CLI tarjoaa tätä varten System.Collections.Queue -luokan Enqueue- ja Dequeue-menetelmillä. STL : ssä on myös luokkajono<>, joka on määritetty otsikkotiedoston jonossa. Se käyttää samaa terminologiaa (push ja pop) kuin pinot .
Ohjelmoinnin jonoa käytetään, kuten todellisessa elämässä, kun sinun on suoritettava joitain toimintoja niiden saapumisjärjestyksessä, suorittamalla ne peräkkäin. Esimerkki on tapahtumien järjestäminen Windowsissa. Kun käyttäjä suorittaa jonkin toiminnon sovellukselle, vastaavaa toimintoa ei kutsuta sovelluksessa (tällä hetkellä sovellus voi kuitenkin suorittaa muita toimintoja), vaan hänelle lähetetään viesti, joka sisältää tiedot tehdystä toimenpiteestä, tämä viesti on jonossa, ja vasta kun aiemmin tulleet viestit käsitellään, sovellus suorittaa tarvittavat toiminnot.
BIOS - näppäimistöpuskuri on järjestetty rengastaulukkona, joka on yleensä 16 konesanaa pitkä ja jossa on kaksi osoitinta: sen seuraavaan elementtiin ja ensimmäiseen tyhjään elementtiin.
| Tietorakenteet | |
|---|---|
| Luettelot | |
| puut | |
| Laskee | |
| muu | |