Lineární datové struktury
Fronta
 Tisk

Fronta


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



Implementace fronty polem

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;


Implementace zřetězenými dynamickými proměnnými

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.