Fronty a zásobníky
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Zásobník – ADT (Abstraktní Datový Typ)
•Obsahuje libovolné objekty
•Vkládání a mazaní probíhá pomocí principu LIFO (Last In First Out)
•Příklad:
•Talíře vyskládané na sobě
•Operace se zásobníkem:
•push(object) vložení objektu
•pop(object) vrácení a odebrání posledního vloženého objektu
•Pomocné operace:
•object top() integer size() boolean isEmpty()
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Zásobník
•Výjimky
•EmptyStackException – operace pop a top na prázdném zásobníku
•Aplikace
•Přímé
•Historie prohlížeče webových stránek
•Undo sekvence
•Řetězec volání jednotlivých procedur
•Nepřímé
•Pomocné datové struktury pro algoritmy
•Části jiných datových struktur
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Zásobník – implementace pomocí pole
•Nejjednodušší způsob implementace zásobníku
•Přidáváme prvky zleva doprava
•Proměnná drží index posledního prvku (top element)
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
S
0
1
2
t
…
Algorithm size()
return t + 1
Algorithm pop()
if isEmpty() then
throw EmptyStackException
 else
t ¬ t - 1
return S[t + 1]

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Zásobník založený na poli – vlastnosti
•Vlastnosti
•n – počet prvků v zásobníku
•Paměťová náročnost - O(n)
•Časová náročnost každé operace – O(1)
•Omezení
•Na začátku musíme definovat velikost zásobníku
•Velikost zásobníku nelze jednoduše změnit
•Přidání prvku do plného zásobníku vyvolá výjimku specifickou pro implementaci

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Fronta
•Obsahuje libovolné objekty
•Vkládání a odebírání prvků probíhá pomocí principu FIFO (First In First Out)
•Operace s frontou
•enqueue(object) vložení objektu na konec fronty
•object dequeue() odebrání objektu zepředu fronty
•Pomocné operace
•object front() integer size() boolean isEmpty()

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Fronta
•Výjimky
•EmptyQueueException – operace dequeue a front na prázdné frontě
•Aplikace
•Přímé
•Pořadníky, fronty na úřadech
•Přístup ke sdíleným zdrojům (tiskárny…)
•Multiprogramování
•Nepřímé
•Pomocné datové struktury pro algoritmy
•Části jiných datových struktur

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Fronta – implementace pomocí pole
•Použití kruhového pole
•Dvě proměnné
•f – index prvního prvku
•r – index posledního prvku +1
Q
0
1
2
r
f
Normální konfigurace
Q
0
1
2
f
r
Kruhová konfigurace

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Fronta – implementace pomocí pole
Algorithm size()
return (N - f + r) mod N
Algorithm isEmpty()
return (f = r)
Algorithm enqueue(o)
if size() = N - 1 then
throw FullQueueException
 else
Q[r] ¬ o
r ¬ (r + 1) mod N
Algorithm dequeue()
if isEmpty() then
throw EmptyQueueException
 else
o ¬ Q[f]
f ¬ (f + 1) mod N
return o