Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 17: Rozdiel medzi revíziami
d |
|||
(24 medziľahlých úprav od 2 ďalších používateľov nie je zobrazených) | |||
Riadok 1: | Riadok 1: | ||
== Oznamy == | == Oznamy == | ||
− | * | + | * Domácu úlohu 3 odovzdávajte do 5. decembra, 22:00. |
− | + | * Zajtrajšia rozcvička bude zo súborov, pozrite si prednášky z minulého týždňa. | |
− | * | + | * Piatkové cvičenia sú povinné pre tých, ktorí nevyriešia v utorok počas cvičení úspešne rozcvičku. |
− | * Blíži sa '''semestrálny test''' | + | * Blíži sa '''semestrálny test'''. |
− | ** Treba z neho získať aspoň 50% bodov, inak známka Fx | + | ** Bude sa konať v stredu v stredu 13.12. o 18:10. |
− | ** Opravný termín bude v januári (iba jeden) | + | ** Treba z neho získať aspoň 50% bodov, inak známka Fx. |
− | ** | + | ** Opravný termín bude v januári (iba jeden). |
− | + | ** Viac podrobností zverejníme budúci týždeň. | |
− | |||
− | |||
== Abstraktný dátový typ == | == Abstraktný dátový typ == | ||
Riadok 32: | Riadok 30: | ||
== Rad a zásobník == | == 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 <tt>int</tt> alebo <tt>char</tt>) tak budeme pracovať so všeobecným typom, ktorý nazveme <tt>dataType</tt>. Za ten možno dosadiť ľubovoľný konkrétny typ – napríklad <tt>int</tt> dosadíme za <tt>dataType</tt> takto: | |
− | |||
− | |||
− | |||
− | Prvky radu môžu byť ľubovoľného typu. Namiesto konkrétneho typu (ako napríklad <tt>int</tt> alebo <tt>char</tt>) tak budeme pracovať so všeobecným typom, ktorý nazveme <tt>dataType</tt>. Za ten možno dosadiť ľubovoľný konkrétny typ – napríklad <tt>int</tt> dosadíme za <tt>dataType</tt> takto: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
typedef int dataType; | typedef int dataType; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Pri využití tohto prístupu tak napríklad bude možné získať z radu prvkov typu <tt>int</tt> rad prvkov typu <tt>char</tt> zmenou v jedinom riadku programu. | + | * Pri využití tohto prístupu tak napríklad bude možné získať z radu prvkov typu <tt>int</tt> rad prvkov typu <tt>char</tt> zmenou v jedinom riadku programu. |
+ | * Taká istá úprava by sa dala spraviť aj pri ADT množina a dynamické pole. | ||
− | Abstraktný dátový typ pre rad | + | |
+ | ===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 <tt>queue</tt> je názov štruktúry reprezentujúcej rad): | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
/* Inicializuje prazdny rad */ | /* Inicializuje prazdny rad */ | ||
Riadok 67: | Riadok 72: | ||
===Zásobník=== | ===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''. | + | * 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 | + | Abstraktný dátový typ pre zásobník poskytuje tieto operácie (<tt>stack</tt> je názov štruktúry reprezentujúcej zásobník): |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
/* Inicializuje prazdny zasobnik */ | /* Inicializuje prazdny zasobnik */ | ||
Riadok 103: | Riadok 110: | ||
− | int main( | + | int main() { |
queue q; | queue q; | ||
init(q); | init(q); | ||
Riadok 113: | Riadok 120: | ||
cout << dequeue(q) << endl; // Vypise 3 | cout << dequeue(q) << endl; // Vypise 3 | ||
destroy(q); | destroy(q); | ||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Riadok 123: | Riadok 129: | ||
typedef int dataType; | typedef int dataType; | ||
− | |||
/* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */ | /* Sem pride definicia struktury stack a vsetkych potrebnych funkcii. */ | ||
− | + | int main() { | |
− | int main( | ||
stack s; | stack s; | ||
init(s); | init(s); | ||
Riadok 138: | Riadok 142: | ||
cout << pop(s) << endl; // Vypise 1 | cout << pop(s) << endl; // Vypise 1 | ||
destroy(s); | destroy(s); | ||
− | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | Poznámka: | ||
+ | * V objektovo-orientovanom programovaní (budúci semester) sa namiesto napr. <tt>push(s,10)</tt> píše niečo ako <tt>s.push(10)</tt> | ||
==Implementácia zásobníka a radu== | ==Implementácia zásobníka a radu== | ||
===Zásobník pomocou poľa=== | ===Zásobník pomocou poľa=== | ||
− | + | * Na úvod implementujeme zásobník pomocou poľa <tt>items</tt>, ktoré budeme alokovať na fixnú dĺžku <tt>maxN</tt> (rovnako dobre by sme však mohli použiť aj dynamické pole). | |
− | Na úvod implementujeme zásobník pomocou poľa <tt>items</tt>, ktoré budeme alokovať na fixnú dĺžku <tt>maxN</tt> (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 <tt>0</tt> a jeho vrch na pozícii <tt>top</tt>. V prípade, že je zásobník prázdny, bude hodnota premennej <tt>top</tt> rovná <tt>-1</tt>. | + | * Spodok zásobníka pritom bude v tomto poli uložený na pozícii <tt>0</tt> a jeho vrch na pozícii <tt>top</tt>. |
+ | * V prípade, že je zásobník prázdny, bude hodnota premennej <tt>top</tt> rovná <tt>-1</tt>. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cassert> | #include <cassert> | ||
− | + | typedef int dataType; | |
− | |||
const int maxN = 1000; | const int maxN = 1000; | ||
struct stack { | struct stack { | ||
− | + | // Alokovane pole prvkov zasobnika. | |
− | + | dataType *items; | |
+ | // Index vrchu zasobnika v poli items, -1 ak prazdny | ||
+ | int top; | ||
}; | }; | ||
Riadok 199: | Riadok 208: | ||
===Rad pomocou poľa=== | ===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 | + | * 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 <tt>0</tt>, 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 <tt>first</tt> poľa <tt>items</tt>. | ||
+ | * Pole <tt>items</tt> pritom budeme chápať ako cyklické – prvky s indexom menším ako <tt>first</tt> budeme implementovať ako nasledujúce za posledným prvkom poľa. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cassert> | #include <cassert> | ||
− | + | typedef int dataType; | |
const int maxN = 1000; | const int maxN = 1000; | ||
struct queue { | struct queue { | ||
− | dataType *items; // | + | dataType *items; // Alokovane pole obsahujuce prvky radu. |
int first; // Index prveho prvku radu v poli items. | int first; // Index prveho prvku radu v poli items. | ||
int count; // Pocet prvkov v rade. | int count; // Pocet prvkov v rade. | ||
Riadok 257: | Riadok 269: | ||
===Zásobník pomocou spájaného zoznamu=== | ===Zásobník pomocou spájaného zoznamu=== | ||
− | Zásobník teraz | + | * Zásobník teraz implementujeme 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 | + | * 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 <tt>maxN</tt>. Podobný efekt je možné docieliť aj dynamického poľa, tam však dochádza k realokácii. |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cassert> | #include <cassert> | ||
− | + | typedef int dataType; | |
struct node { | struct node { | ||
Riadok 317: | Riadok 331: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | ==Rad pomocou spájaného zoznamu== | + | ===Rad pomocou spájaného zoznamu=== |
− | |||
− | |||
− | Výhodou oproti implementácii radu pomocou poľa | + | * Pri implementácii radu pomocou spájaného zoznamu rozšírime spájané zoznamy zo [[Prednáška_14#Sp.C3.A1jan.C3.A9_zoznamy|14. prednášky]] o smerník <tt>last</tt> 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. | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cassert> | #include <cassert> | ||
− | + | typedef int dataType; | |
struct node { | struct node { | ||
Riadok 334: | Riadok 348: | ||
struct queue { | struct queue { | ||
− | + | // Smernik na prvy uzol. Ak je rad prazdny, ma hodnotu NULL. | |
− | node * | + | node *first; |
+ | // Smernik na posledny uzol. Ak je rad prazdny, ma hodnotu NULL. | ||
+ | node *last; | ||
}; | }; | ||
Riadok 391: | Riadok 407: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | == 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 (neskôr si 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 <tt>(,),[,],{,}</tt>. Ú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: | ||
+ | <pre> | ||
+ | () | ||
+ | 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 | ||
+ | </pre> | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | #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; | ||
+ | } | ||
+ | |||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ''Cvičenie:'' Prepíšte program na kontrolu zátvoriek do rekurzívnej podoby. Použite pritom iba premenné typu <tt>char</tt>; špeciálne nepoužívajte žiadne polia. Reťazec načítavajte pomocou funkcií <tt>getc</tt> a <tt>ungetc</tt>. Môžete predpokladať, že je ukončený koncom riadku. |
Aktuálna revízia z 10:19, 20. november 2023
Obsah
Oznamy
- Domácu úlohu 3 odovzdávajte do 5. decembra, 22:00.
- Zajtrajšia rozcvička bude zo súborov, pozrite si prednášky z minulého týždňa.
- Piatkové cvičenia sú povinné pre tých, ktorí nevyriešia v utorok počas cvičení úspešne rozcvičku.
- Blíži sa semestrálny test.
- Bude sa konať v stredu v stredu 13.12. o 18:10.
- Treba z neho získať aspoň 50% bodov, inak známka Fx.
- Opravný termín bude v januári (iba jeden).
- Viac podrobností zverejníme budúci týždeň.
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);
}
Poznámka:
- V objektovo-orientovanom programovaní (budúci semester) sa namiesto napr. push(s,10) píše niečo ako s.push(10)
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 implementovať 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 implementujeme 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 (neskôr si 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.