GMLWiki

Uživatelské nástroje

Nástroje pro tento web

Historie:
informatika:maturita:21a

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Následující verze 		Předchozí verze
informatika:maturita:21a [16. 02. 2015, 16.17]
xmrnustik vytvořeno 		informatika:maturita:21a [16. 03. 2020, 13.57] (aktuální)
xbures1 Přidána cyklická fronta a též přidány příklady reálné implementace fronty.
Řádek 1: Řádek 1:
-Mrnuštík+====== Fronta a zásobník ====== 
 + 
 +Fronta i zásobník jsou 2 principiálně velmi podobné způsoby dočasného uložení dat v rámci programu. Používají se v případech,​ kdy je třeba postupně projít všechny prvky dat, a to právě jednou. 
 + 
 +===== Základní funkce ===== 
 + 
 +  * **push(objekt)** – vkládá nová data do řady 
 +  * **pop()** nebo také **pull()** – získá data, která jsou právě na řadě 
 + 
 +===== Fronta (queue) ===== 
 + 
 +Funguje na principu **FIFO** (first in first out), to znamená, že si frontu můžeme představit třeba jako frontu na úřadu práce. Lidé (data) se řadí po příchodu do fronty a ve stejném pořadí se i dostanou na řadu (data jsou tedy dříve vrácena). 
 + 
 +Jsou potřeba dva ukazatele: front (zde jsou odebírána data) a rear (zde jsou data vkládána)  
 + 
 +==== Metody Implementace ==== 
 + 
 +=== Pomocí statického pole === 
 + 
 +Existují dva způsoby statické implementace – klasická a cyklická frotna:  
 + 
 +U obou variant začínáme tím, že si vytvoříme danou frontu jako **pole**. V rámci funkce push(objekt) pak postupně vkládáme data do pole pomocí ukazatele rear a funkcí pop() získáváme data pomocí ukazatele front. Nyní se dva zmíněné způsoby implementace začínají lišit:  
 + 
 +** klasická fronta **: Při volání funkce pop() získáme data, snížíme hodnotu rear ukazatele a všechny položky posuneme o jedno dopředu. 
 + 
 +zde ukázka klasické varianty statické implementace fronty v jazyce Java: 
 + 
 +{{ :​informatika:​maturita:​staticarrayqueue.png?​nolink |}} 
 + 
 +V rámci konstruktoru vkládáme do fronty čísla 7 a 8 a text "​nine",​ když poté čtyřikrát voláme funkci pop() – zde metoda deQueue() a necháváme vypsat její výstup, finální výstup vypadá takto: 
 + 
 +{{ :​informatika:​maturita:​queueoutput.png?​nolink |}} 
 + 
 +** cyklická fronta **: Při volání funkce pop() opět získáme data, ale tentokrát hodnotu rear ukazatele ponecháváme a naopak se zvyšuje hodnota ukazatele front. Celá fronza je navíc skutečně cyklická, takže v situaci kdy se uvolní prostor z původního "​začátku"​ fronty, může být znova zaplňen na jejím konci. 
 + 
 +viz. diagram:  
 + 
 +{{ :​informatika:​maturita:​circularqueuediagram.png?​nolink |}} 
 + 
 +Nevýhodou statické implementace je, že jsme **omezeni velikostí** námi vytvořeného pole. Výhodou zase naopak je, že za všech okolností **víme, kolik máme na data místa**. 
 + 
 +=== Pomocí ukazatelů === 
 + 
 +Metodu řešení pomocí **ukazatelů** můžeme vidět na níže uvedeném diagramu. Výhoda tohoto řešení je zároveň i jeho nevýhodou – jsme už sice schopni přidávat do fronty příspěvky až do konce paměti, zároveň ale (při špatné implementaci) může dojít k **přehlcení nebo až přetečení paměti**, což může vést k nestabilitě systému. 
 + 
 +{{:​informatika:​maturita:​queuepointerdiagram.png|}} 
 + 
 + 
 +Zde můžeme vidět implementaci pomocí ukazatelů v jazyce Java a to konkrétně s využitím kolekce LinkedList. Všimněme si též těla metody deQueue(), kde musíme zachytávat vyjímku chybějícího ukazatele, je-li fronta prázdná. 
 + 
 +{{ :​informatika:​maturita:​dynamicqueue.png?​nolink |}} 
 + 
 +===== Zásobník (stack) ===== 
 + 
 +Funguje na principu **LIFO** (last in first out), to znamená, že funguje stejně **jako zásobník v samopalu**. Při nabíjení samopalu (vkládání dat) skládáme vždy náboje na spodek zásobníku a vršíme je na sebe, při výstřelu (výběru dat) se náboje berou svrchu – poslední vložený je tedy vystřelen jako první. 
 + 
 +==== Metody Implementace ==== 
 + 
 +=== Pomocí statického pole === 
 + 
 +Řešení zásobníku pomocí statického pole je stejné jako u **fronty**, jediný rozdíl je v tom, že si v další proměnné musíme držet index posledních vložených dat a při zavolání funkce pop() vezmeme data z indexu posledních vložených data a index snížíme o jedna. 
 + 
 +Výhody a nevýhody jsou stejné jako u fronty. 
 + 
 +=== Pomocí ukazatelů === 
 + 
 +Řešení pomocí ukazatelů je také podobné jako u **fronty** (viz diagram níže). 
 + 
 +Výhody a nevýhodu jsou opět naprosto stejné jako u fronty. 
 + 
 +{{:​informatika:​maturita:​stackpointerdiagram.png|}}
informatika/maturita/21a.1424099836.txt.gz · Poslední úprava: 16. 02. 2015, 16.17 autor: xmrnustik

Nástroje pro stránku

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki