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.17]
xmrnustik
+++ 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: @@
 ====== 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 dříve(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á.
+{{ :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|}}

GMLWiki

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku