Pakka

Käytettävissä olevat tyypit:

Yleinen pakka:

Yleistä pakkaa käytetään, kun ei tiedetä etukäteen käytettäviä tyyppejä. Pakkaa luotaessa on käytettävä DESCRIPTOR -kuvaajaa, jolla tyyppi määritellään.

Kokonaislukupakka:

Pakkaan voidaan tallettaa kokonaislukuja (integer). Funktioiden eteen on lisättävä INT_ tai lyhenne ID_ (INT_DEQUE).

Liukulukupakka / reaalilukupakka:

Pakkaan voidaan tallettaa liukulukuja/reaalilukuja (float). Funktioiden eteen on lisättävä FLOAT_ tai lyhenne FD_ (FLOAT_DEQUE).

Merkkijonopakka:

Pakkaan voidaan tallettaa merkkijonoja (char). Funktioiden eteen on lisättävä CHARP_ tai lyhenne CD_ (CHARP_DEQUE).

Osoitinpakka:

Pakkaan voidaan tallettaa osoittimia. Funktioiden eteen on lisättävä VOIDPTR_ tai lyhenne PD_ (VOIDPTR_DEQUE).

Funktiot:

Uuden pakan luominen:
DEQUE_CREATE(D, desc)

Muodostaa tyhjän pakan D, ja asettaa pakan kuvaajaksi kuvaajan desc. Mikäli pakka D ei ole tyhjä pakka, kaikki pakassa ollut tieto menetetään, ja se jää varamaan muistia turhaan.
Aikavaativuus O(1).

void DEQUE_CREATE (DEQUE D, DESCRIPTOR desc)
void INT_DEQUE_CREATE(DEQUE D)
void FLOAT_DEQUE_CREATE(DEQUE D)
void CHARP_DEQUE_CREATE(DEQUE D)
void VOIDPTR_DEQUE_CREATE(DEQUE D)

Pakasta poistaminen:
DEQUE_DEQUEUE(D, dir)

Poistaa pakasta D alkion. Parametri dir (top,bottom) määrää kumpaan pakan päähän operaatio kohdistuu.
Aikavaativuus O(1).

void DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir)
void INT_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir)
void FLOAT_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir)
void CHARP_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir)
void VOIDPTR_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir)

Pakkaan lisääminen:
DEQUE_ENQUEUE (D, dir, x)

Lisää alkion x pakkaan D. Parametri dir (top,bottom) määrää kumpaan pakan päähän operaatio kohdistuu.
Aikavaativuus: O(1)

void DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, ELEMENT x)
void INT_DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, INT_TYPE x)
void FLOAT_DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, FLOAT_TYPE x)
void CHARP_DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, CHARP_TYPE x)
void VOIDPTR_DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, void* x)

Palauttaa pakan päällimmäisen arvon:
DEQUE_FRONT(D)

Palauttaa pakan D päällimmäisen alkion arvon. Yleinen pakka palauttaa ELEMENT-tyypin, tyypitetyt funktiot palauttavat pakan omaa tyyppiä olevan arvon.
Aikavaativuus: O(1)

ELEMENT DEQUE_FRONT(DEQUE D)
INT_TYPE INT_DEQUE_FRONT(DEQUE D)
FLOAT_TYPE FLOAT_DEQUE_FRONT(DEQUE D)
CHARP_TYPE CHARP_DEQUE_FRONT(DEQUE D)
void* VOIDPTR_DEQUE_FRONT(DEQUE D)

Palauttaa pakan alimmaisen arvon:
DEQUE_REAR(D)

Palauttaa pakan D alimmaisen alkion arvon. Yleinen pakka palauttaa ELEMENT-tyypin, tyypitetyt funktiot palauttavat pakan omaa tyyppiä olevan arvon.
Aikavaativuus: O(1)

ELEMENT DEQUE_REAR(DEQUE D)
INT_TYPE INT_DEQUE_REAR(DEQUE D)
FLOAT_TYPE FLOAT_DEQUE_REAR(DEQUE D)
CHARP_TYPE CHARP_DEQUE_REAR(DEQUE D)
void* VOIDPTR_DEQUE_REAR(DEQUE D)

Kertoo onko pakka tyhjä:
DEQUE_EMPTY(D)

Palauttaa tiedon siitä onko pakka D tyhjä pakka. C-kielessä palautusarvo on siis !=0, jos pakka on tyhjä, ja 0 mikäli pakka ei ole tyhjä.
Aikavaativuus: O(1)

int DEQUE_EMPTY(DEQUE D)
int INT_DEQUE_EMPTY(DEQUE D)
int FLOAT_DEQUE_EMPTY(DEQUE D)
int CHARP_DEQUE_EMPTY(DEQUE D)
int VOIDPTR_DEQUE_EMPTY(DEQUE D)

Vapauttaa pakan varaaman tilan:
DEQUE_FREE(D)

Vapauttaa kaiken pakan D varaaman tilan ja asettaa pakan D määrittelemättömäksi pakaksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Jos void*- tai char*-pakassa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi pakan tuhoamisen jälkeen, täytyy ennen DEQUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta.
Aikavaativuus: O(n)

void DEQUE_FREE(DEQUE D)
void INT_DEQUE_FREE(DEQUE D)
void FLOAT_DEQUE_FREE(DEQUE D)
void CHARP_DEQUE_FREE(DEQUE D)
void VOIDPTR_DEQUE_FREE(DEQUE D)

Vertailee pakan alkioita:
DEQUE_LESS(D, x, y)
DEQUE_SAME(D, x, y)

Palauttavat tiedon siitä ovatko pakan D 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 pakan D alkiot (muttei niiden ole pakko olla pakan D alkioita). Jos x=y, niin DEQUE_SAME palauttaa siis TRUE (!=0), ja jos x<y niin DEQUE_LESS palauttaa TRUE (!=0). Merkkijonopakassa vertaillaan merkkijonojen välistä aakkosjärjestystä.
Aikavaativuus : yksinkertaisille tyypeille O(1)

int DEQUE_LESS(D, x, y)
int DEQUE_SAME(D, x, y)

Palauttaa pakan tyypin:
DEQUE_TYPE(D)

Palauttaa pakan D kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen pakka joudutaan luomaan.
Aikavaativuus: O(1)

DESCRIPTOR DEQUE_TYPE DEQUE_TYPE(D)

Luo satunnaisesti pakan:
DEQUE_CONSTRUCT_RANDOM(D, count, min, max)

Muodostaa pakan D, jossa on count-määrä alkioita. Pakka täytyy olla alustettu jonkin tyyppiseksi pakaksi (XXX_DEQUE_CREATE(D)). Mikäli pakka on kokonaislukupakka, min on pakan alkioiden minimiarvo ja max maksimi, liukulukupakalla samoin. Merkkijonopakalla DEQUE_CONSTRUCT_RANDOM (D, count, min, max)  vie pakkaan count kappaletta merkkijonoja, jotka sisältävät min..max merkkiä. C:ssä merkkijonon pituus on kuitenkin vähintään 1 ('\0'-merkki). Merkkijonot koostuvat pelkästään pienistä kirjaimista väliltä 'a'..'z'. Merkkijonon maksimipituus on rajoitettu vakion RANDOM_STR_MAX suuruiseksi.
Aikavaativuus: O(count)

void DEQUE_CONSTRUCT_RANDOM(D, count, min, max)