====== Fronta a zásobník ======

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

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

=== Pomocí statického pole ===

Existují dva způsoby statické implementace – klasická a cyklická frotna: 

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ůž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|}}


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