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