1.2 KiB
1.2 KiB
Fronta
- abstraktní datová struktura
- podobá se zásobníku
- FIFO - first in, first out
Operace
- přidání prvku na konec
- vybrání prvku na začátku
- odebrání prvku na začátku
Implementace spojovým prvkem
- velmi podobná zásobníku
- kromě odkazu na první prvek uchovává i odkaz na poslední prvek
Složitost operací
- všechny
\Theta(1) - vyšší náročnost na paměť
Implementace polem
- velmi podobná zásobníku
- po odebrání vznikají prázdná místa v poli
- je možné je využít pro přidávání
- struktura obsahuje:
- index prvního prvku
- počet obsazených indexů
- při přidávání prvku:
- kontrolujeme, jestli se prvek do pole vejde
- pokud je místo na začátku, vložíme prvek na začátek pole
- pokud je pole plné zvětšíme pole a zkopírujeme od indexu prvního prvku až do délky pole
- využijeme modula - pomocí něj index "přeteče" na začátek pole
- máme pole o 5 prvcích
- vkládáme na index 5, nicméně 5 % 5 je 0 (začátek pole)
- kontrolujeme, jestli se prvek do pole vejde
Složitost operací
- vybrání/odebrání prvního prvku
\Theta(1) - přidání prvku na konec:
- většinou
\Theta(1) - při zvětšení pole
\Theta(n) - v průměru
\Theta(1)
- většinou