Rozdíly

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

--- informatika:maturita:21a [21. 02. 2015, 17.33] – xmrnustik
+++ informatika:maturita:21a [16. 03. 2020, 13.57] (aktuální) – Přidána cyklická fronta a též přidány příklady reálné implementace fronty. xbures1
@@ Řádek 1: / Řádek 1: @@
 ====== Fronta a zásobník ======
-= způsoby dočasného uložení dat v rámci  programu
+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 obou =====
+===== Základní funkce =====
-**push(co)** - slouží k vložení dat
+  * **push(objekt)** – vkládá nová data do řady
+  * **pop()** nebo také **pull()** – získá data, která jsou právě na řadě
-**pop()** nebo také **pull()** - slouží k získání dat, 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).
-===== Fronta =====
+Jsou potřeba dva ukazatele: front (zde jsou odebírána data) a rear (zde jsou data vkládána)
-(anglicky 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), kteří příjdou dříve, přijdou na řadu první(jsou vrácena dříve).
 ==== Metody Implementace ====
@@ Řádek 19: / Řádek 18: @@
 === Pomocí statického pole ===
-Řešení pomocí statického pole funguje tak, že si vytvoříme **pole** a v rámci funkce push dáváme data do pole a ve funkci pop vždy vezmeme první položku a ostatní posuneme o jedno místo dopředu.
+Existují dva způsoby statické implementace – klasická a cyklická frotna:
-Nevýhodou tohoto způsobu implementace je, že jsme **omezení velikostí** námi vytvořeného pole. Výhodou tohoto řešení je, že vždy za všech okolností **víme, kolik nám zbývá místa** na další data.
+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ůžete vidět na níže uvedeném diagramu. Výhoda tohoto řešení je zároveň i jeho nevýhodou, jsme totiž schopni přidávat do fronty příspěvky dokud máme místo v paměti, nevýhodou je, že 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.
+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|}}
-===== Zásobník =====
+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á.
-(anglicky 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ěr dat) se náboje berou odvrchu, z toho plyne, že poslední vložený je první vystřelený.
+{{ :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 ====
@@ Řádek 41: / Řádek 61: @@
 Ř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ýhodu jsou stejné jako u fronty.
+Výhody a nevýhody jsou stejné jako u fronty.
 === Pomocí ukazatelů ===
-Řešení pomocí ukazatelů je také podobné jako u **fronty**, znázroněné ho máte na diagramu níže.
+Řešení pomocí ukazatelů je také podobné jako u **fronty** (viz diagram níže).
-Výhody a nevýhodu jsou stejné jako u fronty.
+Výhody a nevýhodu jsou opět naprosto stejné jako u fronty.
 {{:informatika:maturita:stackpointerdiagram.png|}}