Cyklická fronta

Cyklická fronta je jeden ze způsobů, jakým bývá datová struktura fronta v praxi často implementována.

Při představě prvního prvku pole navazujícího na poslední odpovídá abstrakce kruhové paměti

Zeleně obsazené pozice, modře volné, červeně ukazatel čtení a žlutě ukazatel zápisu

Animace: Cyklická fronta jako vyrovnávací paměť obsluhy klávesnice

Její podstatou je zacyklené pole, ve kterém po posledním prvku znovu následuje první, takže pohyb v poli může být nekonečný. Po zápisu na poslední prvek se zapisuje znovu do prvního – za předpokladu, že z prvního už byl mezitím obsah odebrán. Ke správě cyklické fronty slouží kromě pole dva ukazatele – jeden na pozici, kam se má zapisovat nový prvek, druhý na pozici, ze které se má číst nejstarší vložený prvek. Pokud ukazují na stejnou pozici, je fronta prázdná, pokud by se takového stavu mělo dosáhnout změnou ukazatele zapisování, pak naopak dochází k tomu, že do plné fronty se už další prvek nevejde.

Ve srovnání s implementací prostým polem je cyklická implementace podstatně rychlejší – v prostém poli by bylo nutné všechny obsazené pozice posouvat, v cyklické frontě se nic posouvat nemusí, pouze jsou potřeba dva ukazatele na konec a začátek vloženého obsahu. Na rozdíl od implementace fronty spojovým seznamem je ale provozní velikost cyklické fronty omezena a náhodný požadavek na její okamžité zvětšení znamená přebudovat ji množstvím přesunů. Na druhou stranu paměťové nároky spojového seznamu jsou výrazně vyšší a spojový seznam mívá navíc horší lokálnost dat.

Při některých využitích, kdy je cyklická fronta využívána k realizaci vyrovnávací paměti, je navíc jasné, že příliš stará data jsou tak jako tak již nepotřebná a pokud tedy začne zápisový ukazatel dohánět čtecí ukazatel, posune se i čtecí ukazatel – stará data se jen přepíší, aniž by byla přečtena.

Externí odkazy

• Obrázky, zvuky či videa k tématu cyklická fronta na Wikimedia Commons