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.

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)