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 fakulte, 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() {
    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);
}

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() {
    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);
}

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 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 budeme interpretovať ako nasledujúce za posledným prvkom poľa.

#include <cassert>

typedef int dataType;

const int maxN = 1000;

struct queue {
    dataType *items; // Alokovane pole obsahujuce 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.
• Na rozdiel 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 je v tom, že maximálny počet prvkov v zásobníku nebude obmedzený konštantou maxN. Podobný efekt je možné docieliť aj dynamického poľa, tam však dochádza k realokácii.

#include <cassert>

typedef int dataType;

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é efektívne vkladať prvky na koniec zoznamu, ako aj odoberať prvky zo začiatku zoznamu.
• Výhodou oproti implementácii radu pomocou poľa je, podobne ako pri zásobníkoch, eliminácia obmedzenia na maximálny počet prvkov v rade.

#include <cassert>

typedef int dataType;

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

struct queue {
    // Smernik na prvy uzol. Ak je rad prazdny, ma hodnotu NULL.
    node *first; 
    // Smernik na posledny uzol. Ak je rad prazdny, ma hodnotu NULL.
    node *last;  
};

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

Použitie zásobníka a radu

Zásobník aj rad často uchovávajú dáta určené na spracovanie, zoznamy úloh, atď. Rad sa zvyčajne používa v prípadoch, keď je žiadúce zachovať ich poradie. Typicky môže ísť o situácie, keď jeden proces generuje úlohy spracúvané iným procesom, napríklad:

• Textový procesor pripravuje strany na tlač a vkladá ich do radu, z ktorého ich tlačiareň (resp. jej ovládač) postupne vyberá.
• Sekvenčne vykonávané výpočtové úlohy čakajú v rade na spustenie.
• Zákazníci čakajú na zákazníckej linke na voľného operátora.
• Pasažieri na standby čakajú na voľné miesto v lietadle.

Zásobník sa, ako o niečo implementačne jednoduchší koncept, zvyčajne používa v situáciách, keď na poradí spracúvania nezáleží, alebo keď je žiadúce vstupné poradie obrátiť. Najvýznamnejší príklad situácie druhého typu je nasledujúci:

• Operačný systém ukladá lokálne premenné volaných funkcií na tzv. zásobníku volaní (angl. call stack), čo umožňuje používanie rekurzie.
• Rekurzívne programy sa dajú prepísať na nerekurzívne pomocou „ručne vytvoreného” zásobníka (nižšie si napríklad ukážeme nerekurzívnu verziu triedenia Quick Sort).

Príklad: kontrola uzátvorkovania

Ako jednoduchý príklad na použitie zásobníka uvažujme nasledujúcu situáciu: na vstupe je daný reťazec pozostávajúci (okrem prípadných ďalších znakov, ktoré možno ignorovať) zo zátvoriek (,),[,],{,}. Úlohou je zistiť, či je tento reťazec dobre uzátvorkovaný. To znamená, že:

• Pre každú uzatváraciu zátvorku musí byť posledná dosiaľ neuzavretá otváracia zátvorka rovnakého typu, pričom musí existovať aspoň jedna dosiaľ neuzavretá zátvorka.
• Každá otváracia zátvorka musí byť niekedy neskôr uzavretá.

Príklady očakávaného vstupu a výstupu:

()
Retazec je dobre uzatvorkovany

nejaky text bez zatvoriek
Retazec je dobre uzatvorkovany

[((({}[])[]))]()
Retazec je dobre uzatvorkovany

[[#))
Retazec nie je dobre uzatvorkovany

())(
Retazec nie je dobre uzatvorkovany

((
Retazec nie je dobre uzatvorkovany

((cokolvek
Retazec nie je dobre uzatvorkovany

• Nasledujúci program postupne prechádza cez vstupný reťazec, pričom pre každú otváraciu zátvorku si na zásobník pridá uzatváraciu zátvorku rovnakého typu.
• Ak narazí na uzatváraciu zátvorku, výraz môže byť dobre uzátvorkovaný len v prípade, že je na zásobníku aspoň jedna zátvorka, pričom zátvorka na vrchu zásobníka sa zhoduje so zátvorkou na vstupe.
• V prípade úspešného prechodu cez celý vstup je reťazec dobre uzátvorkovaný práve vtedy, keď na zásobníku nezostala žiadna zátvorka.

#include <iostream>
#include <cassert>
using namespace std;

typedef char dataType;

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

int main() {
    char vyraz[100];
    cin.getline(vyraz, 100);
    
    stack s;
    init(s);
    
    bool dobre = true;
    
    for (int i = 0; vyraz[i] != 0; i++) {
        switch (vyraz[i]) {
            case '(':
                push(s, ')');
                break;
            case '[':
                push(s, ']');
                break;
            case '{':
                push(s, '}');
                break;
            case ')':
            case ']':
            case '}':
                if (isEmpty(s)) {
                    dobre = false;
                } else {
                    char c = pop(s);
                    if (c != vyraz[i]) {
                        dobre = false;
                    }
                }
                break;
        }
    }
    
    dobre = dobre && isEmpty(s);
        
    destroy(s);
    
    if (dobre) {
        cout << "Retazec je dobre uzatvorkovany." << endl;
    } else {
        cout << "Retazec nie je dobre uzatvorkovany." << endl;
    }

}

Cvičenie: Prepíšte program na kontrolu zátvoriek do rekurzívnej podoby. Použite pritom iba premenné typu char; špeciálne nepoužívajte žiadne polia. Reťazec načítavajte pomocou funkcií getc a ungetc. Môžete predpokladať, že je ukončený koncom riadku.

Príklad: nerekurzívny Quick Sort

Pripomeňme si triedenie Quick Sort z 11. prednášky:

void swap (int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int partition(int a[], int left, int right) {
    int pivot = a[left];     
    int lastSmaller = left;
    
    for (int unknown = left + 1; unknown <= right; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }   
    swap(a[left],a[lastSmaller]); 
    return lastSmaller;
}

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return; 
    }
    
    int middle = partition(a, left, right);
        
    quicksort(a, left, middle-1);  
    quicksort(a, middle+1, right);   
}

int main() {
  // ...
  quicksort(a, 0, N-1);
  // ...
}

Namiesto rekurzie môžeme použiť aj zásobník úsekov, ktoré ešte treba dotriediť.

struct usek {
    int left;
    int right;
};

typedef usek dataType;

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

/* Sem pridu funkcie swap a partition rovnake ako vyssie. */

void quicksort(int a[], int n) {
    stack s;
    init(s);
    
    usek u;
    u.left = 0;
    u.right = n-1;
    push(s,u);
    
    while (!isEmpty(s)) {
        u = pop(s);
        // vynechame useky dlzky 0 a 1
        if (u.left >= u.right) {
            continue;
        }
        
        int middle = partition(a, left, right);
        
        usek u1;
        u1.left = u.left;
        u1.right = middle - 1;
        usek u2;
        u2.left = middle + 1;
        u2.right = u.right;
        push(s,u2);
        push(s,u1);
    }
    
    destroy(s);
}

int main() {
  // ...
  quicksort(a, N);
  // ...
}

• Tento program triedi úseky v rovnakom poradí, ako rekurzívny Quick Sort, lebo po rozdelení poľa na dve časti dá na vrch zásobníka úsek zodpovedajúci jeho ľavej časti. Až keď sa táto ľavá časť a všetky podúlohy, ktoré z nej vzniknú, spracuje, dôjde na spracovanie pravej časti poľa.
• Pri triedení Quick Sort však na tomto poradí nezáleží, takže by sme mohli jednotlivé úseky vkladať na zásobník aj v opačnom poradí.
• Alebo by sme namiesto zásobníka mohli použiť rad. Potom by najskôr rozdelil ľavú aj pravú časť na ďalšie podčasti a potom by delil každú z týchto podčastí atď.

Na zamyslenie: ako by mohla vyzerať nerekurzívna verzia triedenia Merge Sort? Prečo sa nedá použiť rovnaký prístup ako pri triedení Quick Sort?