Prednáška 17

Oznamy

• Budúci týždeň budú cvičenia v utorok a v piatok iba online, nebude rozcvička, iba príklady, ktoré môžete riešiť do ďalšieho utorka
• Na testovači pribudlo zadanie tretej (a poslednej) domácej úlohy s odovzdaním do 6. decembra, 22:00.
• Tento piatok sa ešte dá prísť na cvičenia osobne, v prípade záujmu si dajte pozor, aby ste boli zapísaní v tabuľke
• Blíži sa semestrálny test
  • Treba z neho získať aspoň 50% bodov, inak známka Fx
  • Opravný termín bude v januári (iba jeden)
  • Pôvodne bola písomka ohlásená na stredu 8.12. večer, ale presúvame ju na piatok 10.12. počas doplnkových cvičení o 11:30
  • Ak máte s týmto presunom problém, dajte nám vedieť dnes alebo zajtra
  • Večerné termíny bývajú pre študentov náročné
  • Ak bude umožnená prezenčná výučba, písomka bude na fakukulte, inak online

Abstraktný dátový typ

Abstraktný dátový typ (ADT) je abstrakcia dátovej štruktúry nezávislá od samotnej implementácie.

• Býva zadaný pomocou množiny operácií (hlavičiek funkcií), ktoré poskytuje
• Jeden abstraktný dátový typ môže byť implementovaný pomocou viacerých dátových štruktúr.

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).

Videli sme implementácie (pre jednoduchosť bez operácie remove) pomocou neutriedeného poľa, utriedeného poľa, spájaného zoznamu, priameho adresovania a hašovania.

Podobne by sa za ADT dalo považovať dynamické pole s operáciami add, length, get a set.

Výhodou abstraktných dátových typov je 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 sú dva nové abstraktné dátové typy.

Rad a zásobník

• Zásobník (angl. stack) a rad alebo front (angl. queue) sú jednoduché abstraktné dátové typy, ktoré udržiavajú postupnosť nejakých prvkov.
• Typicky ide o úlohy alebo dáta čakajúce na spracovanie.
• Rad aj zásobník poskytujú funkciu, ktorá vkladá nový prvok.
• Druhou základnou funkciou je výber jedného prvku, pričom rad sa od zásobníka líši tým, ktorý prvok sa vyberá.

Prvky radu a zásobníka 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.
• Taká istá úprava by sa dala spraviť aj pri ADT množina a dynamické pole.

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.

Abstraktný dátový typ pre rad poskytuje 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ý.
• Môžeme si ho predstaviť ako stĺpec tanierov, kde umyté taniere dávame na vrch stĺpca a tiež z vrchu aj berieme taniere na použitie.
• 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 poskytuje tieto operácie (stack je názov štruktúry reprezentujúcej zásobník):

/* 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>

typedef int dataType;
const int maxN = 1000;

struct stack {
    // Alokovane pole prvkov zasobnika.
    dataType *items; 
    // Index vrchu zasobnika v poli items, -1 ak prazdny
    int top;         
};

/* 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);
    }
}

Rad pomocou spájaného zoznamu

Pri implementácii radu pomocou spájaného zoznamu rozšírime spájané zoznamy zo 14. prednášky o smerník last na posledný prvok zoznamu. Bude tak možné jednoducho vkladať prvky na koniec zoznamu, ako aj odoberať prvky zo začiatku zoznamu.

Výhodou oproti implementácii radu pomocou poľa bude, podobne ako pri zásobníkoch, eliminácia obmedzenia na maximálny počet prvkov v rade.

#include <cassert>

// ...

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

struct queue {
    node *first; // Smernik na prvy prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
    node *last;  // Smernik na posledny prvok radu (spajaneho zoznamu). Ak je rad prazdny, ma hodnotu NULL.
};

/* Inicializuje prazdny rad */
void init(queue &q) {
    q.first = NULL;
    q.last = NULL;
}

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

/* Prida prvok item na koniec radu */
void enqueue(queue &q, dataType item) {
    node *tmp = new node;
    tmp->data = item;
    tmp->next = NULL;
    if (isEmpty(q)) {
        q.first = tmp;
        q.last = tmp;
    } else {
        q.last->next = tmp;
        q.last = tmp;
    }
} 

/* Odoberie prvok zo zaciatku radu a vrati jeho hodnotu */
dataType dequeue(queue &q) {
    assert(!isEmpty(q));
    dataType result = q.first->data;
    node *tmp = q.first->next;
    delete q.first;
    if (tmp == NULL) {
        q.first = NULL; 
        q.last = NULL;
    } else {
        q.first = tmp;
    } 
    return result;
}

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

/* Uvolni pamat */
void destroy(queue &q) {
    while (!isEmpty(q)) {
        dequeue(q);
    }
}