Začínáme programovat v Javě (3. díl) – Hello world!

Vytvoření fronty bývá velice častým zadáním v různých školních předmětech zabývajícími se programováním. A jelikož spousta lidí nemá tušení jak taková fronta vůbec funguje, tak jsem se rozhodl sepsat malou teorii o tom jak vytvořit Datovou strukturu typu Fronta v jazyce Java.

Fronta je abstraktní datový typ uplatňující mechanismus FIFO (First in, First out). To znamená, že vkládaná data do struktury jsou vybírána ve stejném pořadí v jakém byla vložena. V praxi se většinou návrh fronty používá například k tzv. dávkovému zpracování dat. To vypadá zhruba tak, že zadavatel vyšle ke zpracování dávku tvořenou větším počtem dat. Zařízení, které má data zpracovat si uloží dávku do fronty odkud si je postupně odebírá. Princip činnosti si můžeme demonstrovat i na věcech z běžného života. Jistě každý z vás zná čekací systém fungující na úřadech, v nemocnicích a na poštách. Po příchodu si vezmete číslo a čekáte dokud na vás nepřijde řada. To je přesně funkční ukázka fronty. Zaměstnanec někde na přepážce má určitou rychlost jakou odbavuje návštěvníky a ta není vždy stejná jako rychlost příchodu návštěvníků. Pomocí tohoto vyčkávacího systému lze během pracovní doby odbavit prakticky všechny návštěvníky i když jich například v jeden časový úsek přijde větší množství než je schopen jeden zaměstnanec na přepážce v danou chvíli odbavit.

Fronta ve statickém poli

V programovacím jazyce Java lze vytvořit frontu několika způsoby. Tím asi nejjednodušším způsobem je vytvoření statického pole o N rozměrech. U tohoto způsobu vkládáme prvky vždy za poslední obsazené místo v poli a vybíráme vždy z prvního obsazeného místa. To má bohužel za následek to, že se nám fronta pomalu přesunuje z levé části pole doprava a až dojde na konec, tak dojde k přetečení pole.

Tomu se dá zabránit tak, že si vytvoříme tzv. kruhovou frontu. Jedná se vlastně o statické pole jako v předchozím případě kde po obsazení posledního prvku se začne pole zaplňovat opět od začátku. Ovšem toto řešení také není úplně to pravé ořechové. Pokud počet prvků momentálně uložených ve frontě převýší rozměr pole, tak dojde opět k nežádoucímu přetečení.

Fronta s referencemi

My si nyní ukážeme jak vytvořit frontu, která netrpí stejnými neduhy jako fronty tvořené statickým polem. A tou je fronta tvořená referencemi. Takto vytvořená fronta má tu výhodu, že může být prakticky libovolně veliká a nemusíme se bát přetečení pole jako v předchozím případě.

Samotná fronta je tvořena prvky, které si vždy udržují informaci o následujícím prvku (reference na další) a vytváří tak zřetězený seznam. Fronta si pak dále udržuje ještě informaci o prvním a o posledním prvku v seznamu (reference na první a poslední). Tyto reference nám ve frontě jasně vymezují pořadí prvků v jakém jsou ve frontě uloženy a v jakém pořadí mají být vybírány.