Author: Tapani Katainen

# Pinon funktioiden esittelyt

Pinoa voidaan käsitellä yleisen pinon avulla tietämättä pinon oikeaa tyyppiä, aivan kuten esimerkiksi listan tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä pinotyyppiä : kokonaislukupino, joka sisältää int / integer - arvoja, liukulukupino (sisältää float / real - tyyppistä tietoa), merkkijonopino (char* / string[ ]) ja osoitinpino (void* / pointer - tyyppistä tietoa).

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

Pino on tietorakenteena ikään kuin lista jonka operaatiot kohdistuvat aina listan ensimmäiseen alkioon.

- STACK_CREATE (S, D)
- STACK_PUSH (S, x)
- STACK_TOP (S)
- STACK_POP (S)
- STACK_PRINT (S)
- STACK_FREE (S)
- STACK_CONSTRUCT_RANDOM (S, count, min, max)
- STACK_TYPE (S)
- STACK_LESS (S, x, y)
- STACK_SAME (S, x, y)
- STACK_EMPTY (S)

Yleisen pinon käsittely

> Yleisen pinon funktioita tarvitaan silloin, kun pitää käsitellä pinoa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä pinoa luotaessa määritellään pinon tyyppi kuvaajan DESCRIPTOR avulla. Funktio STACK_TYPE(S) palauttaa pinon S kuvaajan jota voidaan käyttää pinoa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten pinon alkioita vertaillaan, käsitellään ja tulostetaan.

Int / integer - pinon käsittely

> Kokonaislukupinon 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_STACK_XXX - aliohjelmat voidaan lyhentää IS_XXX; INT_STACK_CREATE(S) voidaan siis kutsua myös IS_CREATE(S).

Float / real - pinon käsittely

> Liukulukupinon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukupinon kohdalla. FLOAT_STACK_XXX voidaan lyhentää koodissa FS_XXX.

Char* / string[ ] - pinon käsittely

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

## Funktioiden esittelyt

STACK_CREATE (S, D)

> void STACK_CREATE (STACK S, DESCRIPTOR D);

> void INT_STACK_CREATE(STACK S);

> void FLOAT_STACK_CREATE(STACK S);

> void CHARP_STACK_CREATE(STACK S);

> void VOIDPTR_STACK_CREATE(STACK S);

> procedure STACK_CREATE (var S:STACK; D:DESCRIPTOR);

> procedure INT_STACK_CREATE (var S:STACK);

> procedure FLOAT_STACK_CREATE (var S:STACK);

> procedure CHARP_STACK_CREATE (var S:STACK);

> procedure VOIDPTR_STACK_CREATE (var S:STACK);

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

Aikavaativuus : O(1)

STACK_PUSH (S, x)

> void STACK_PUSH (STACK S, ELEMENT x);

> void INT_STACK_PUSH(STACK S, INT_TYPE x);

> void FLOAT_STACK_PUSH(STACK S, FLOAT_TYPE x);

> void CHARP_STACK_PUSH(STACK S, CHARP_TYPE x);

> void VOIDPTR_STACK_PUSH(STACK S, void* x);

> procedure STACK_PUSH (S:STACK; x:ELEMENT);

> procedure INT_STACK_PUSH (S:STACK; x:INT_TYPE);

> procedure FLOAT_STACK_PUSH (S:STACK; x:FLOAT_TYPE);

> procedure CHARP_STACK_PUSH (S:STACK; x:CHARP_TYPE);

> procedure VOIDPTR_STACK_PUSH (S:STACK; x:pointer);

Lisää alkion x pinoon S päällimmäiseksi. Tyypitetyt operaatiot vievät pinoon omaa tyyppiään olevan alkion.

Aikavaativuus : O(1)

STACK_TOP (S)

> ELEMENT STACK_TOP (STACK S);

> INT_TYPE INT_STACK_TOP (STACK S);

> FLOAT_TYPE FLOAT_STACK_TOP (STACK S);

> CHARP_TYPE CHARP_STACK_TOP (STACK S);

> void VOIDPTR_STACK_POP(STACK S);

> function STACK_TOP (S:STACK) : ELEMENT;

> function INT_STACK_TOP(S:STACK) : INT_TYPE;

> function FLOAT_STACK_TOP(S:STACK) : FLOAT_TYPE;

> function CHARP_STACK_TOP(S:STACK) : CHARP_TYPE;

> function VOIDPTR_STACK_TOP(S:STACK) : pointer;

Palauttaa pinon S päällimmäisen alkion arvon. Yleinen pino palauttaa ELEMENT-tyypin, tyypitettyjen listojen funktiota palauttavat pinon omaa tyyppiä olevan arvon. Jos pino on tyhjä, jää tulos määrittelemättömäksi.

Aikavaativuus : O(1)

STACK_POP (S)

> void STACK_POP (STACK S);

> void INT_STACK_POP(STACK S);

> void FLOAT_STACK_POP(STACK S);

> void CHARP_STACK_POP(STACK S);

> procedure STACK_POP (S:STACK);

> procedure INT_STACK_POP (S:STACK);

> procedure FLOAT_STACK_POP (S:STACK);

> procedure CHARP_STACK_POP (S:STACK);

Poistaa pinosta S päällimmäisen alkion. Jos pino on tyhjä, jää tulos määrittelemättömäksi.

Aikavaativuus : O(1)

STACK_PRINT (S)

> void STACK_PRINT (STACK S);

> procedure STACK_PRINT (S:STACK);

Tulostaa pinon S 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ä pinon käytön kannalta, mutta helpottavat yleisten aliohjelmien tekemistä ja testaamista:

STACK_FREE (S)

> void STACK_FREE (STACK S);

> void INT_STACK_FREE (STACK S);

> void FLOAT_STACK_FREE (STACK S);

> void CHARP_STACK_FREE (STACK S);

> void VOIDPTR_STACK_FREE(STACK S);

> procedure STACK_FREE (var S:STACK);

> procedure INT_STACK_FREE (var S:STACK);

> procedure FLOAT_STACK_FREE (var S:STACK);

> procedure CHARP_STACK_FREE (var S:STACK);

> procedure VOIDPTR_STACK_FREE (var S:STACK);

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

Aikavaativuus : O(n)

STACK_CONSTRUCT_RANDOM (S, count, min, max)

> void STACK_CONSTRUCT_RANDOM (STACK S, int count, INT_TYPE min, INT_TYPE max);

> procedure STACK_CONSTRUCT_RANDOM (S:STACK; count:integer; min,max:INT_TYPE);

Muodostaa pinon S, jossa on count-määrä alkioita. Pino täytyy olla alustettu jonkin tyyppiseksi pinoksi (XXX_STACK_CREATE(S)). Mikäli pino on kokonaislukupino, min on pinon alkioiden minimiarvo ja max maksimi, liukulukupinolla samoin. Merkkijonopinolla STACK_CONSTRUCT_RANDOM (S, count, min, max) vie pinoon 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ä. STACK_CONSTRUCT_RANDOM (S, 10, 2, 4) arpoo siis kokonaislukupinolle 10 kappaletta kokonaislukuja, jotka saavat arvoja 2..4, liukulukupinolle 10 kpl. liukulukuja välillä 2.00 - 4.00, merkkijonopinolle 10 merkkijonoa välillä 'aa'..'zzzz'. Esimerkki 2 : Pascal / C

Aikavaativuus : O(count)

STACK_TYPE (S)

> DESCRIPTOR STACK_TYPE (STACK S);

> function STACK_TYPE (S:STACK) : DESCRIPTOR;

Palauttaa pinon S kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen pino joudutaan luomaan. Uusi pino M, joka on samaa tyyppiä kuin pino S, luodaan komennolla STACK_CREATE(M, STACK_TYPE(S));.

Aikavaativuus : O(1)

STACK_LESS (S, x, y)

STACK_SAME (S, x, y)

> int STACK_LESS (STACK S, ELEMENT x, ELEMENT y);

> int STACK_SAME (STACK S, ELEMENT x, ELEMENT y);

> function STACK_LESS (S:STACK; x,y:ELEMENT) : boolean;

> function STACK_SAME (S:STACK; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko pinon S 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 pinon S alkiot (muttei niiden ole pakko olla pinon S alkioita). Jos x=y, niin STACK_SAME palauttaa siis TRUE (!=0), ja jos x<y niin STACK_LESS palauttaa TRUE (!=0). Merkkijonopinossa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

STACK_EMPTY (S)

> int STACK_EMPTY (STACK S);

> int INT_STACK_EMPTY (STACK S);

> int FLOAT_STACK_EMPTY (STACK S);

> int CHARP_STACK_EMPTY (STACK S);

> int VOIDPTR_STACK_EMPTY(STACK S);

> function STACK_EMPTY (S:STACK) : boolean;

> function INT_STACK_EMPTY (S:STACK) : boolean;

> function FLOAT_STACK_EMPTY (S:STACK) : boolean;

> function CHARP_STACK_EMPTY (S:STACK) : boolean;

> function VOIDPTR_STACK_EMPTY (S:STACK) : boolean;

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

Aikavaativuus : O(1)