Fronta a zásobník

Tyto datové struktury si lze vyzkoušet na této 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.

• push(objekt) – vkládá nová data do řady
• pop() nebo také pull() – získá data, která jsou právě na řadě

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)

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:

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:

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.

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)

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 videu

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

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