Lab03 - Kruhová fronta

Napište program, který bude reprezentovat cyklickou frontu uchovávající hodnoty typu String. Kapacita fronty bude parametrem konstruktoru. Pokud bude použit bezparametrický konstruktor, vytvořte frontu o konstantní velikosti 5. Dále naimplementujte metody do připravené třídy CircularArrayQueue. Co mají jednotlivé metody dělat dozvíte v dokumentaci v interface Queue.java. Všimněte si, že dokumentace některých metod je velmi podobná (někdy i stejná) dokumentaci metod ve třídě Queue ve standardním java frameworku. Toto není náhoda, autoři úkolu se tímto javadocem inspirovali .

Ve třídě Start je připraven kód, na kterém můžete funkčnost implementace kruhové fronty vyzkoušet

--- Příklad očekávaného výstupu programu
size: 6
value dequeued from CircularArrayQueue: Starkiller
printing all elements: 
C-3PO
Jabba the Hutt
HK-47
Darth Nihilus
Count Dooku
size: 6

Fronta je dynamická množina (datová struktura), u které jsou specificky definovány operace výběru a vložení prvku. Operace výběr z fronty vybere prvek, který jsme vložili do fronty jako první. Při vkládání prvků do fronty se vkládaná položka vloží na jeho konec. (anglicky enqueue a dequeue)

Tato struktura se také někdy označuje termínem FIFO (first-in first-out).

Fronta se dá implementovat polem a to buď polem statické délky s explicitním omezením na počet vložených prvků nebo polem dynamické délky. Alterantivně se dá také realizovat datovou strukturou nazývanou spojový seznam, se kterou se seznámíme na dalším cvičení.

V případě omezené kapacity fronty, například realizované polem statické délky, můžeme využít takzvanou kruhovou frontu. V té se začátek fronty pohybuje po jednotlivých prvcích pole tak jak jsou postupně prvky vkládány a odebírány. Praktické použití takové fronty si můžeme představit v případech, kdy do fronty jsou dávány jednotlivé požadavky na obsloužení, které v průměru nepřicházejí častěji než je rychlost obsluhy. V případě, že obsloužení konkrétního požadavku trvá déle, jsou další požadavky uloženy ve frontě a po vyřízení náročnějšího požadavku jsou pak ostatní, méně náročné, požadavky obslouženy rychleji a fronta je rychle vyprázdněna. Analogickou situaci můžeme začít například v obchodě, ve kterém je kapacita fronty omezena velikostí obchodu.

Kruhová fronta může explicitně hlídat, zda-li je možné nový požadavek do fronty vložit a v případě zaplnění fronty je možné požadavek na vložení zamítnout. Na druhé straně můžeme také najít připady, kdy do kruhové fronty dáváme požadavky a pokud je plná, jsou ty nejstarší požadavky přepisovány. To může například nastat v případě zpracování senzorických dat, ve kterém předpokládáme, že pokud se data nestihla zpracovat, jsou pravděpodobně již zastaralá a dáváme přednost zpracování aktuálnějších informací.