Author: Tapani Katainen

# Jonon funktioiden esittelyt

Jonoa voidaan käsitellä yleisen jonon avulla tietämättä jonon oikeaa tyyppiä, aivan kuten esimerkiksi listan tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä jonotyyppiä : kokonaislukujono, joka sisältää int / integer - arvoja, liukulukujono (sisältää float / real - tyyppistä tietoa), merkkijonojono (char* / string[ ]) ja osoitinjono (void* / pointer - tyyppistä tietoa).

Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonojonon funktiot. Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että jono on määritelty. Mikäli parametrina annettava jono Q on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin QUEUE_CREATE:a joka määrittelee jonon.

Jono on tietorakenteena kuin lista jonka lisäysoperaatiot kohdistuvat aina listan loppuun ja poisto- sekä retrieve-operaatiot listan alkuun.

- QUEUE_CREATE (Q, D)
- QUEUE_ENQUEUE (Q , x)
- QUEUE_FRONT (Q)
- QUEUE_DEQUEUE (Q)
- QUEUE_PRINT (Q)
- QUEUE_FREE (Q)
- QUEUE_CONSTRUCT_RANDOM (Q, count, min, max)
- QUEUE_TYPE (Q)
- QUEUE_LESS (Q, x, y)
- QUEUE_SAME (Q, x, y)
- QUEUE_EMPTY (Q)

Yleisen jonon käsittely

> Yleisen jonon funktioita tarvitaan silloin, kun pitää käsitellä jonoa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä jonoa luotaessa määritellään jonon tyyppi kuvaajan DESCRIPTOR avulla. Funktio QUEUE_TYPE(Q) palauttaa jonon Q kuvaajan jota voidaan käyttää jonoa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten jonon alkioita vertaillaan, käsitellään ja tulostetaan. Kuvaajasta ja yleisen jonon alkioiden tyypistä ELEMENT enemmän luvussa "Tietorakenteiden kuvaukset".

Int / integer - jonon käsittely

> Kokonaislukujonon esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on toteutuskohtaisesti määritelty. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (max. 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (2^32). Kaikki INT_QUEUE_XXX - aliohjelmat voidaan lyhentää IQ_XXX; INT_QUEUE_CREATE(Q) voidaan siis kutsua myös IQ_CREATE(Q).

Float / real - jonon käsittely

> Liukulukujonon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukujonon kohdalla. FLOAT_QUEUE_XXX voidaan lyhentää koodissa FQ_XXX.

Char* / string[ ] - jonon käsittely

> Merkkijonojonon tyyppinä on C:ssä char*, osoitin merkkijonoon. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä. Kaikki CHARP_QUEUE_XXX - aliohjelmat voidaan lyhentää koodissa CQ_XXX.

## Funktioiden esittelyt

QUEUE_CREATE (Q, D)

> void QUEUE_CREATE (QUEUE Q, DESCRIPTOR D);

> void INT_QUEUE_CREATE(QUEUE Q);

> void FLOAT_QUEUE_CREATE(QUEUE Q);

> void CHARP_QUEUE_CREATE(QUEUE Q);

> void VOIDPTR_QUEUE_CREATE(QUEUE Q);

> procedure QUEUE_CREATE (var Q:QUEUE; D:DESCRIPTOR);

> procedure INT_QUEUE_CREATE (var Q:QUEUE);

> procedure FLOAT_QUEUE_CREATE (var Q:QUEUE);

> procedure CHARP_QUEUE_CREATE (var Q:QUEUE);

> procedure VOIDPTR_QUEUE_CREATE (var Q:QUEUE);

Yleinen QUEUE_CREATE(Q, D) muodostaa tyhjän jonon Q, ja asettaa jonon kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}. Mikäli jono Q ei ole tyhjä jono, kaikki jonossa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan jonon Q. Esimerkki 1 : Pascal / C.

Aikavaativuus : O(1)

QUEUE_ENQUEUE (Q, x)

> void QUEUE_ENQUEUE (QUEUE Q, ELEMENT x);

> void INT_QUEUE_ENQUEUE(QUEUE Q, INT_TYPE x);

> void FLOAT_QUEUE_ENQUEUE(QUEUE Q, FLOAT_TYPE x);

> void CHARP_QUEUE_ENQUEUE(QUEUE Q, CHARP_TYPE x);

> void VOIDPTR_QUEUE_ENQUEUE(QUEUE Q, void* x);

> procedure QUEUE_ENQUEUE (Q:QUEUE; x:ELEMENT);

> procedure INT_QUEUE_ENQUEUE (Q:QUEUE; x:INT_TYPE);

> procedure FLOAT_QUEUE_ENQUEUE (Q:QUEUE; x:FLOAT_TYPE);

> procedure CHARP_QUEUE_ENQUEUE (Q:QUEUE; x:CHARP_TYPE);

> procedure VOIDPTR_QUEUE_ENQUEUE (Q:QUEUE; x:pointer);

Lisää alkion x jonon Q loppuun. Tyypitetyt operaatiot vievät jonoon omaa tyyppiään olevan alkion.

Aikavaativuus : O(1)

QUEUE_ FRONT (Q)

> ELEMENT QUEUE_FRONT (QUEUE Q);

> INT_TYPE INT_QUEUE_FRONT (QUEUE Q);

> FLOAT_TYPE FLOAT_QUEUE_FRONT (QUEUE Q);

> CHARP_TYPE CHARP_QUEUE_FRONT (QUEUE Q);

> void* VOIDPTR_QUEUE_FRONT(QUEUE Q);

> function QUEUE_FRONT (Q:QUEUE) : ELEMENT;

> function INT_QUEUE_FRONT(Q:QUEUE) : INT_TYPE;

> function FLOAT_QUEUE_FRONT(Q:QUEUE) : FLOAT_TYPE;

> function CHARP_QUEUE_FRONT(Q:QUEUE) : CHARP_TYPE;

> function VOIDPTR_QUEUE_FRONT(Q:QUEUE) : pointer;

Palauttaa jonon Q ensimmäisen alkion arvon. Yleinen jono palauttaa ELEMENT-tyypin, tyypitettyjen listojen funktiota palauttavat jonon omaa tyyppiä olevan arvon.

Aikavaativuus : O(1)

QUEUE_DEQUEUE (Q)

> void QUEUE_DEQUEUE (QUEUE Q);

> void INT_QUEUE_DEQUEUE (QUEUE Q);

> void FLOAT_QUEUE_DEQUEUE (QUEUE Q);

> void CHARP_QUEUE_DEQUEUE (QUEUE Q);

> void VOIDPTR_QUEUE_DEQUEUE(QUEUE Q);

> procedure QUEUE_DEQUEUE (Q:QUEUE);

> procedure INT_QUEUE_DEQUEUE (Q:QUEUE);

> procedure FLOAT_QUEUE_DEQUEUE (Q:QUEUE);

> procedure CHARP_QUEUE_DEQUEUE (Q:QUEUE);

> procedure VOIDPTR_QUEUE_DEQUEUE (Q:QUEUE);

Poistaa jonosta Q ensimmäisen alkion.

Aikavaativuus : O(1)

QUEUE_PRINT (Q)

> void QUEUE_PRINT (QUEUE Q);

> procedure QUEUE_PRINT (Q:QUEUE);

Tulostaa jonon Q kuvaajassa määritellyllä tavalla. Tyypitetyillä funktioilla ei ole eroa tämän toiminnan kanssa.

Aikavaativuus : O(n)

Seuraavat aliohjelmat eivät ole välttämättömiä jonon käytön kannalta, mutta helpottavat yleisten aliohjelmien tekemistä ja testaamista:

QUEUE_FREE (Q)

> void QUEUE_FREE (QUEUE Q);

> void INT_QUEUE_FREE (QUEUE Q);

> void FLOAT_QUEUE_FREE (QUEUE Q);

> void CHARP_QUEUE_FREE (QUEUE Q);

> void VOIDPTR_QUEUE_FREE(QUEUE Q);

> procedure QUEUE_FREE (var Q:QUEUE);

> procedure INT_QUEUE_FREE (var Q:QUEUE);

> procedure FLOAT_QUEUE_FREE (var Q:QUEUE);

> procedure CHARP_QUEUE_FREE (var Q:QUEUE);

> procedure VOIDPTR_QUEUE_FREE (var Q:QUEUE);

Vapauttaa kaiken jonon Q varaaman tilan ja asettaa jonon Q määrittelemättömäksi jonoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila.Jos void*- tai char*-jonossa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi jonon tuhoamisen jälkeen, täytyy ennen QUEUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta. Esimerkki 1 : Pascal / C

Aikavaativuus : O(n)

QUEUE_CONSTRUCT_RANDOM (Q, count, min, max)

> void QUEUE_CONSTRUCT_RANDOM (QUEUE Q, int count, INT_TYPE min, INT_TYPE max);

> procedure QUEUE_CONSTRUCT_RANDOM (Q:QUEUE; count:integer; min,max:INT_TYPE);

Muodostaa jonon Q, jossa on count-määrä alkioita. Jono täytyy olla alustettu jonkin tyyppiseksi jonoksi (XXX_QUEUE_CREATE(Q)). Mikäli jono on kokonaislukujono, min on jonon alkioiden minimiarvo ja max maksimi, liukulukujonolla samoin. Merkkijonojonolla QUEUE_CONSTRUCT_RANDOM (Q, count, min, max) vie jonoon count kappaletta merkkijonoja, jotka sisältävät min..max merkkiä. C:ssä merkkijonon pituus on kuitenkin vähintään 1 ('\0'-merkki), Pascalissa pituus voi olla 0 merkkiä. Merkkijonot koostuvat pelkästään pienistä kirjaimista väliltä 'a'..'z'. Merkkijonon maksimipituus on rajoitettu vakion RANDOM_STR_MAX suuruiseksi, ainakin cs:n toteutuksessa 16 merkkiä. QUEUE_CONSTRUCT_RANDOM (Q, 10, 2, 4) arpoo siis kokonaislukujonolle 10 kappaletta kokonaislukuja, jotka saavat arvoja 2..4, liukulukujonolle 10 kpl. liukulukuja välillä 2.00 - 4.00, merkkijonojonolle 10 merkkijonoa välillä 'aa'..'zzzz'. Esimerkki : Pascal / C

Aikavaativuus : O(count)

QUEUE_TYPE (Q)

> DESCRIPTOR QUEUE_TYPE (QUEUE Q);

> function QUEUE_TYPE (Q:QUEUE) : DESCRIPTOR;

Palauttaa jonon Q kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen jono joudutaan luomaan. Uusi jono M, joka on samaa tyyppiä kuin jono Q, luodaan komennolla QUEUE_CREATE(M, QUEUE_TYPE(Q));.

Aikavaativuus : O(1)

QUEUE_LESS (Q, x, y)

QUEUE_SAME (Q, x, y)

> int QUEUE_LESS (QUEUE Q, ELEMENT x, ELEMENT y);

> int QUEUE_SAME (QUEUE Q, ELEMENT x, ELEMENT y);

> function QUEUE_LESS (Q:QUEUE; x,y:ELEMENT) : boolean;

> function QUEUE_SAME (Q:QUEUE; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko jonon Q määräämää tyyppiä olevat elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin jonon Q alkiot (muttei niiden ole pakko olla jonon Q alkioita). Jos x=y, niin QUEUE_SAME palauttaa siis TRUE (0), ja jos x<y niin QUEUE_LESS palauttaa FALSE (!=0). Merkkijonojonossa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

QUEUE_EMPTY (Q)

> int QUEUE_EMPTY (QUEUE Q);

> int INT_QUEUE_EMPTY (QUEUE Q);

> int FLOAT_QUEUE_EMPTY (QUEUE Q);

> int CHARP_QUEUE_EMPTY (QUEUE Q);

> int VOIDPTR_QUEUE_EMPTY(QUEUE Q);

> function QUEUE_EMPTY (Q:QUEUE) : boolean;

> function INT_QUEUE_EMPTY (Q:QUEUE) : boolean;

> function FLOAT_QUEUE_EMPTY (Q:QUEUE) : boolean;

> function CHARP_QUEUE_EMPTY (Q:QUEUE) : boolean;

> function VOIDPTR_QUEUE_EMPTY (Q:QUEUE) : boolean;

Palauttaa tiedon siitä onko jono Q tyhjä jono. C-kielessä palautusarvo on siis !=0, jos jono on tyhjä, ja 0 mikäli jono ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos jono on tyhjä ja FALSE, jos jono ei ole tyhjä.

Aikavaativuus : O(1)