Fronta je základní datová typ, který nám umožňuje vkládat prvky a vybírat prvky v pořadí, v jakém byly vkládány. Tomuto principu se říká FIFO - first in, fist out. Fungování fronty je velice intuitivn a chová stejně jako fronta, se kterou se setkáváme v každodenním životě (v obchodě u pokladny).
Operace
Typickými operacemi jsou
| Operace | Popis | Složitost |
|---|---|---|
| enqueue (Push) | vložení nového prvku (na konec fronty) | O(1) |
| dequeue (Pop) | odebrání prvku (z čela fronty), | O(1) |
| isEmpty | zjištění, zda je fronta prázdná, | O(1) |
| front | čtení prvního prvku fronty | O(1) |
| size | zjištění počtu prvků ve frontě. | O(1) |
Implementace pomocí pole
Abychom udrželi konstantní dobu vložení nového prvku a konstantní dobu vybrání jednoho prvku, nesmíme prvky v poli posunovat a tak do pole budeme evidovat dva ukazatele. Jeden bude ukazovat na nejdříve vložený prvek (abychom jej mohli v případě požadavku odebrat) a druhý bude ukazovat na první volné místo. Pokud se pole naplní, budeme jej opět plnit odpředu, použijeme tzv. cyklický buffer.
Implementace pomocí spojového seznamu
Tato implementace má větší režii než pole. Pro zachování jednotkové složitosti vložení a odebrání prvku je nutné uchovávat dva ukazatele, jeden na začátek a druhý na konec fronty. Abychom nemuseli procházet frontu při každém požadavku na zjištění její velikosti, je dobré si její aktuální délku pamatovat jako jednu z vlastností fronty a tuto hodnotu aktualizovat ve funkcích pro přidání a odebrání prvku.
Složitost
Pokud je fronta dobře implementována, pak každá operace s ní má konstantní složitost.