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