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.30] – [Zásobník] xmrnustik
+++ informatika:maturita:21a [17. 02. 2026, 21.03] (aktuální) – xwolf4
@@ Řádek 1: / Řádek 1: @@
 ====== Fronta a zásobník ======
+Tyto datové struktury si lze vyzkoušet na této [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|stránce]].
-= 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 =====
+Fronta a zásobník jsou centrální datové struktury algoritmů vyhledávání do šířky (BFS) a vyhledávání do hloubky (DFS). Jediným rozdílem mezi těmito algoritmy je použitá datová struktura.
-**push(co)** - slouží k vložení dat
+===== Základní funkce =====
-**pop()** nebo také **pull()** - slouží k získání dat, které jsou právě na řadě
+  * **push(objekt)** – vkládá nová data do řady
+  * **pop()** nebo také **pull()** – získá data, která jsou právě na řadě
+===== Fronta (queue) =====
-===== Fronta =====
+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).
-(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).
+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 ===
-Ř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.
+=== Cyklické pole ===
+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á fronta 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.
-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.
+viz. diagram:
-=== Pomocí ukazatelů ===
+{{ :informatika:maturita:circularqueuediagram.png?nolink |}}
-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.
+Výhody:
+  * O(1) přečtení libovolné hodnoty ve frontě (ne pouze na začátku nebo konci)
+  * rychlejší než linked list
+    * výhodnější pro CPU cache
+    * menší "object overhead"
+  * umí využít informaci o maximální velikosti (viz kód)
+Nevýhody:
+  * O(1)* amortizovaná časová složitost přidání hodnoty
+    * téměř vždy O(1)
+    * O(n) v případě naplnění fronty - musíme celé pole zkopírovat do nového pole s větší velikostí (viz kód)
+    * může být pomalejší než linked list, když musí často zvětšovat velikost pole
+  * neumí zmenšit svou velikost (může plýtvat pamětí)
+  * fronta je omezená velikostí ukazatelů - například v Javě má maximální velikost Integer.MAX_VALUE - 8 = 2 147 483 439
+Implementací cyklického pole je například kolekce ArrayDeque v jazyce Java, tady je její zjednodušená verze:
-{{:informatika:maturita:queuepointerdiagram.png|}}
+{{:informatika:maturita:circular_queue.png?600|}}
-===== Zásobník =====
+=== Pomocí ukazatelů (Linked list) ===
-(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ý.
+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:queue_linked_list_animation.gif?|}}
+Výhody:
+  * O(1) složitost přidání hodnoty
+  * neomezená velikost
+  * dynamicky se zvětšuje a zmenšuje - neplýtvá pamětí
+Nevýhody:
+  * pomalejší než cyklické pole
+Zde je zjednodušená verze kolekce LinkedList v jazyce Java. (V jazyce Java je LinkedList obousměrně vázaný seznam, ale pro jednoduchost je níže implementovaný jako jednosměrně vázaný seznam)
+{{:informatika:maturita:linked_list_implementation.png?600|}}
+===== 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í.
+Bez zásobníku by v programování nefungovalo volání funkcí. Detailně je to popsáno v tomto [[https://www.youtube.com/watch?v=7YyALikxAlU&t=2s|videu]]
 ==== Metody Implementace ====
@@ Řádek 39: / Řádek 72: @@
 === 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.
+Ř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|}}