# 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)

**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)$