Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 17
Obsah
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(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 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(void) {
// ...
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 Prednáška_11#Triedenie_zlu.C4.8Dovan.C3.ADm_.28Merge_Sort.29 Merge Sort? Prečo sa nedá použiť rovnaký prístup ako pri triedení Quick Sort?