Abstraktní představa fronty je na obr. .
Sémantický význam
Dynamická lineární homogenní datová struktura, která se používá tehdy, chceme-li dočasně uložit informační položky, které budeme později zpracovávat ve stejném pořadí, v jakém byly uloženy. Lze ji charakterizovat výrokem „První dovnitř, první ven“, anglicky „First In First Out“, odtud FIFO, lidově pravidlo mlynáře ("První přijde, první mele").
Povolené operace:
Implementace fronty
Frontu lze implementovat polem i zřetězeným seznamem. Při implementaci polem musíme velikost pole staticky omezit (ukazatel na/za poslední prvek) a je jasné, že během práce s frontou se aktivní část fronty neustále posouvá směrem k vyšším hodnotám indexů, takže skoro určitě jednou dojde k vyčerpání pole. Tento konflikt se řeší např. cyklickým bufferem. Představa cyklického bufferu je na obr. , C ... ukazatel čela fronty, Z ... ukazatel konce fronty, I ... rozlišuje plný a prázdný buffer.
Operace s frontou se navrhnou tak, že pole se svými indexy funguje cyklicky, tzn. že po dosažení maximální hodnoty se začne znovu od začátku. Zvolí-li se velikost pole dostatečná vzhledem k maximálnímu počtu prvků, které se mohou do fronty dostat, je toto opatření vyhovující.
Pro realizaci fronty se může zavést následující definice, pro kterou se pak navrhnou operace.
Const
Max : ... ; { Největší možná délka fronty }
Type
TP : ... ; { Typ prvků, ukládaných do fronty }
TF = record
POLE : array[1 .. Max] of TP; { Pole pro prvky }
cteni: 1 .. Max; { Index prvku v čele fronty }
zapis: 1 .. Max; { Index prvého neobsazeného místa }
indikace:boolean { rozlišení plné a prázdné fronty }
end;
Není-li známa délka fronty, je lépe implementovat frontu pomocí dynamicky alokované paměti. Potíže, vznikající při implementaci fronty polem, odpadají. V podstatě jde o spojový seznam, nad kterým jsou definovány příslušné operace tak, aby se choval jako požadovaná fronta.
Type
TP = ... ;
UKAZ = ^Prvek;
Prvek = record
Hodnota: TP; { Hodnota uloženého prvku }
spoj: UKAZ { Ukazatel na další prvek ve frontě. }
end;
TF = record
prvni: UKAZ; { Ukazatel na první prvek }
posledni:UKAZ; { Ukazatel na poslední prvek }
pocet: Integer { Počet prvků ve frontě }
end;
Prvky mohou být do fronty zařazovány, případně vybírány i podle jiných kritérií, např. podle priorit. (Takové atributy se pak přidají do záznamu Prvek).
Mají-li se do fronty zařazovat nebo z fronty vyjímat prvky jinak než z konce fronty, na př. podle určité priority, je nejvhodnějším způsobem implementace obousměrně propojený spojový seznam.