Rozdíly

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

--- informatika:maturita:21a [16. 03. 2020, 13.57] – Přidána cyklická fronta a též přidány příklady reálné implementace fronty. xbures1
+++ 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]].
 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.
+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.
 ===== Základní funkce =====
@@ Řádek 16: / Řádek 19: @@
 ==== Metody Implementace ====
-=== Pomocí statického pole ===
-Existují dva způsoby statické implementace – klasická a cyklická frotna:
+=== 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.
-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:
+viz. diagram:
-** 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.
+{{ :informatika:maturita:circularqueuediagram.png?nolink |}}
-zde ukázka klasické varianty statické implementace fronty v jazyce Java:
+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:staticarrayqueue.png?nolink |}}
+{{:informatika:maturita:circular_queue.png?600|}}
-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 |}}
+=== Pomocí ukazatelů (Linked list) ===
-** 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|}}
+{{: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 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á.
+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:dynamicqueue.png?nolink |}}
+{{: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 ====