Pinon funktioiden esittelyt

Pinoa voidaan käsitellä yleisen pinon operaatioiden 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 määritelty toteutuskohtaisesti. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (enintään 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 päällimmäiseksi pinoon S. Tyypitetyt operaatiot vievät pinoon omaa tyyppiään olevan alkion. Esimerkki 1 : Pascal / C

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 pinojen funktiot palauttavat pinon omaa tyyppiä olevan arvon. Jos pino on tyhjä, jää tulos määrittelemättömäksi. Esimerkki 1 : Pascal / C

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 pinon S päällimmäisen alkion. Jos pino on tyhjä, jää tulos määrittelemättömäksi. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

STACK_PRINT (S)
void STACK_PRINT (STACK S);

procedure STACK_PRINT (S:STACK);

Tulostaa pinon S kuvaajassa määritellyllä tavalla. Esimerkki 1 : Pascal / C

Aikavaativuus : O(n)

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)

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

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 kukin 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 1 : 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));. Esimerkki 1 : Pascal / C

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ä. Esimerkki 1 : Pascal / C

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ä. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)