====== 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 =====

  * **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 ====


=== 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.

viz. diagram: 

{{ :informatika:maturita:circularqueuediagram.png?nolink |}}

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:circular_queue.png?600|}}


=== Pomocí ukazatelů (Linked list) ===

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 ====

=== 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|}}