Prednáška 17

Abstraktný dátový typ

Abstraktné dátové typy (ADT) sú abstrakciami dátových štruktúr nezávislými od samotnej implementácie. Zvyčajne bývajú dané prostredníctvom množiny operácií (hlavičiek funkcií), ktoré daný abstraktný dátový typ poskytuje na prácu s dátami používateľovi. Témou 14. prednášky bol napríklad abstraktný dátový typ dynamická množina, ktorý poskytuje tri základné operácie:

• Zistenie príslušnosti prvku do množiny (contains).
• Pridanie prvku do množiny (add).
• Odobranie prvky z množiny (remove).

Jeden abstraktný dátový typ môže byť implementovaný pomocou viacerých dátových štruktúr. Na 14. prednáške bol napríklad abstraktný dátový typ dynamická množina (presnejšie jeho operácie contains a add) implementovaný pomocou neutriedeného poľa, utriedeného poľa, spájaného zoznamu, priameho adresovania a hešovania.

Výhodou abstraktných dátových typov je predovšetkým oddelenie implementácie dátovej štruktúry od programu, ktorý ju používa. Napríklad program pracujúci s dynamickou množinou prostredníctvom funkcií contains, add a remove možno rovnako dobre použiť pri implementácii množiny pomocou neutriedených polí, ako pri jeho implementácii pomocou hešovania.

Témou dnešnej prednášky budú dva nové abstraktné dátové typy: zásobník (angl. stack) a rad alebo front (angl. queue).

Rad a zásobník

Rad (často aj front; angl. queue) a zásobník (angl. stack) sú jednoduché abstraktné dátové typy umožňujúce udržiavať postupnosť nejakých prvkov (typicky môže ísť o úlohy alebo dáta čakajúce na spracovanie). Rad aj zásobník poskytujú funkciu umožňujúcu vložiť do nich používateľom zadaný prvok. Druhou základnou funkciou poskytovanou oboma týmito abstraktnými dátovými typmi je výber jedného prvku z radu resp. zo zásobníka. Rad sa od zásobníka líši najmä správaním tejto druhej operácie.

Rad

Z radu sa zakaždým vyberie ten jeho prvok, ktorý doň bol vložený ako prvý spomedzi jeho aktuálnych prvkov – možno ho tak pripodobniť k radu pri pokladni v obchode. Takáto metóda manipulácie s dátami sa v angličtine označuje skratkou FIFO, podľa first in, first out.

Prvky radu môžu byť ľubovoľného typu. Namiesto konkrétneho typu (ako napríklad int alebo char) tak budeme pracovať so všeobecným typom, ktorý nazveme dataType. Za ten možno dosadiť ľubovoľný konkrétny typ – napríklad int dosadíme za dataType takto:

typedef int dataType;

Pri využití tohto prístupu tak napríklad bude možné získať z radu prvkov typu int rad prvkov typu char zmenou v jedinom riadku programu.

Abstraktný dátový typ pre rad môže poskytovať napríklad tieto operácie (kde queue je názov štruktúry reprezentujúcej rad):

/* Inicializuje prazdny rad */
void init(queue &q);

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q);

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item);

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q);

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q);

/* Uvolni pamat */
void destroy(queue &q);

Zásobník

Zo zásobníka sa naopak zakaždým vyberie ten prvok, ktorý doň bol vložený ako posledný. Táto metóda manipulácie s dátami sa v angličtine označuje skratkou LIFO, podľa last in, first out.

Abstraktný dátový typ pre zásobník tak môže poskytovať napríklad nasledujúce operácie (stack je názov štruktúry reprezentujúcej zásobník a opäť pracujeme s prvkami všeobecného typu dataType):

/* Inicializuje prazdny zasobnik */
void init(stack &s);

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s);

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item);

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s);

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */
dataType peek(stack &s);

/* Uvolni pamat */
void destroy(stack &s);

Programy využívajúce rad a zásobník

Bez ohľadu na samotnú implementáciu vyššie uvedených funkcií vieme písať programy, ktoré ich využívajú. Napríklad nasledujúci program pracuje s radom:

#include <iostream>
using namespace std;

typedef int dataType;


/* Sem pride definicia struktury queue a vsetkych potrebnych funkcii. */


int main(void) {
    queue q;
    init(q);
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    cout << dequeue(q) << endl;  // Vypise 1
    cout << dequeue(q) << endl;  // Vypise 2
    cout << dequeue(q) << endl;  // Vypise 3
    destroy(q);
    return 0;
}

Podobne nasledujúci program pracuje so zásobníkom:

#include <iostream>
using namespace std;

typedef int dataType;


/* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */


int main(void) {
    stack s;
    init(s);
    push(s, 1);
    push(s, 2);
    push(s, 3);
    cout << pop(s) << endl;  // Vypise 3
    cout << pop(s) << endl;  // Vypise 2
    cout << pop(s) << endl;  // Vypise 1
    destroy(s);
    return 0;
}

Implementácia zásobníka a radu

Zásobník pomocou poľa

Na úvod implementujeme zásobník pomocou poľa items, ktoré budeme alokovať na fixnú dĺžku maxN (rovnako dobre by sme však mohli použiť aj dynamické pole). Spodok zásobníka pritom bude v tomto poli uložený na pozícii 0 a jeho vrch na pozícii top. V prípade, že je zásobník prázdny, bude hodnota premennej top rovná -1.

#include <cassert>

// ...

const int maxN = 1000;

struct stack {
    dataType *items; // Alokujeme na pole reprezentujuce jednotlive prvky zasobnika.
    int top;         // Index vrchu zasobnika v poli items. Ak je zasobnik prazdny, ma hodnotu -1.
};

/* Inicializuje prazdny zasobnik */
void init(stack &s) {
    s.items = new dataType[maxN];
    s.top = -1; 
}

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s) {
    return s.top == -1;
}

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item) {
    assert(s.top <= maxN - 2);
    s.top++;
    s.items[s.top] = item;
} 

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s) {
    assert(!isEmpty(s));
    s.top--;
    return s.items[s.top + 1];
}

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */          
dataType peek(stack &s) {
    assert(!isEmpty(s));
    return s.items[s.top];
}

/* Uvolni pamat */
void destroy(stack &s) {
    delete[] s.items;
}

Rad pomocou poľa

Rad sa od zásobníka líši tým, že prvky sa z neho vyberajú z opačnej strany, než sa doň vkladajú. Keby sa teda prvý prvok radu udržiaval na pozícii 0, museli by sa po každom výbere prvku tie zvyšné posunúť o jednu pozíciu „doľava”, čo je časovo neefektívne. Rad teda implementujeme tak, aby jeho začiatok mohol byť na ľubovoľnej pozícii first poľa items. Pole items pritom budeme chápať ako cyklické – prvky s indexom menším ako first pritom budeme interpretovať ako nasledujúce za posledným prvkom poľa.

#include <cassert>

// ...

const int maxN = 1000;

struct queue {
    dataType *items; // Alokujeme na pole reprezentujuce jednotlive prvky radu.
    int first;       // Index prveho prvku radu v poli items.
    int count;       // Pocet prvkov v rade. 
};

/* Inicializuje prazdny rad */
void init(queue &q) {
    q.items = new dataType[maxN];
    q.first = 0;
    q.count = 0;
}

/* Zisti, ci je rad prazdny */
bool isEmpty(queue &q) {
    return q.count == 0;
}

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item) {
    assert(q.count < maxN);
    int index = (q.first + q.count) % maxN;
    q.items[index] = item;
    q.count++;
} 

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q) {
    assert(!isEmpty(q));
    dataType result = q.items[q.first];
    q.first = (q.first + 1) % maxN;
    q.count--;
    return result;
}

/* Vrati prvok zo zaciatku radu, ale necha ho v rade */
dataType peek(queue &q) {
    assert(!isEmpty(q));
    return q.items[q.first];
}         

/* Uvolni pamat */
void destroy(queue &q) {
    delete[] q.items;
}

Zásobník pomocou spájaného zoznamu

Zásobník teraz interpretujeme pomocou spájaného zoznamu. Narozdiel od implementácie pomocou poľa bude výhodnejšie uchovávať vrch zásobníka ako prvý prvok zoznamu (pri jednosmerne spájaných zoznamoch je totiž jednoduchšie vkladať a odoberať prvky na jeho začiatku).

Výhoda tohto prístupu oproti implementácii pomocou poľa bude spočívať predovšetkým v tom, že maximálny počet prvkov v zásobníku už nebude obmedzený konštantou maxN. Podobný efekt síce možno docieliť použitím dynamického poľa, jeho realokácia je však časovo neefektívna.

#include <cassert>

// ...

struct node {
    dataType data;
    node *next;
};

struct stack {
    node *top; // Smernik na vrch zasobnika (zaciatok spajaneho zoznamu). Ak je zasobnik prazdny, ma hodnotu NULL.
};

/* Inicializuje prazdny zasobnik */
void init(stack &s) {
    s.top = NULL;
}

/* Zisti, ci je zasobnik prazdny */
bool isEmpty(stack &s) {
    return s.top == NULL;
}

/* Prida prvok item na vrch zasobnika */
void push(stack &s, dataType item) {
    node *tmp = new node;
    tmp->data = item;
    tmp->next = s.top;
    s.top = tmp;  
} 

/* Odoberie prvok z vrchu zasobnika a vrati jeho hodnotu */
dataType pop(stack &s) {
    assert(!isEmpty(s));
    dataType result = s.top->data;
    node *tmp = s.top->next;
    delete s.top;
    s.top = tmp;
    return result;
}

/* Vrati prvok na vrchu zasobnika, ale necha ho v zasobniku */          
dataType peek(stack &s) {
    assert(!isEmpty(s));
    return s.top->data;
}

/* Uvolni pamat */
void destroy(stack &s) {
    while (!isEmpty(s)) {
        pop(s);
    }
}