42 lines
1.2 KiB
Markdown
42 lines
1.2 KiB
Markdown
# 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)$ |