Něco ke stažení
Články a návody
Poezie
Odkazy
Fronta
Fronta je spolu se zásobníkem velmi často používaná struktura. Patří k těm velmi jednoduchým, ale přesto je mocná.
Princip fronty si lze nejlépe představit jako frontu někde v prodejně. Postupně do ní přicházejí lidé, stoupnou si na konec a čekají. Člověk na začátku fronty nakoupí co chce a odejde.
Datová struktura fronta pracuje stejným způsobem - prvky, které do ní vkládáme, se ukládají na konec fronty a když chceme nějaký prvek vzít a zpracovat, vezmeme ten na začátku.
Takto bude vypadat frota po vložení prvků A,B,B,A,B,A
Vyjmout můžeme vždy jen první prvek
Nakonec ještě vložíme do fronty B - přidá se na konec.
Zbývá tedy ještě vysvětlit, jak takovou frontu naprogramovat. Dá se to samozřejmě mnoha způsoby. Ten nejjednodušší je použít pole o délce Maximalni_delka, co bude nějaká konstanta, kterou zvolíme podle použití fronty (abychom nezabrali zbytečně moc paměti). K tomuhle poli ještě potřebujem dva indexy Konec a Zacatek (třeba typu word nebo unsigned int, podle zvoleného jazyku), které nám budou ukazovat na první a poslední prvek v poli.
No a dále to u bude snadné - napíšem si dvě funkce Fronta_vlož a Fronta_vyjmi.
Fronta_vlož uloží prvek do fronty - to tak, že do pole fronta na pozici Konec uloží prvek a Konec zvýší o 1.
Fronta_vyjmi zase vezme prvek z pole fronta na pozici Zacatek, zvýší proměnou Zacatek a vrátí nalezený prvek.
Všimněte si, e takto intuitivně popsaná fronta roste doprava a začátek má vlevo, tedy přesně opačně, než na předchozích obrázcích. Pro ilustraci radši uvedu obrázek nový:
Z obrázku je také patrné, že po nějaké době, kdy budeme vkládat do fronty prvky a zas je vybírat, se nám celá fronta posune až k pravému konci pole a nebude u kam vložit nový prvek, ačkoliv začátek fronty bude opět prázdný. To se samozřejmě řeší tak, že pokud je proměnná Konec < konstanta Maximalni_delka, do Konec vložíme 0. Způsobí nám to , že se znovu začnou zaplňovat prázdná políčka na začátku pole. Stejně musíme upravit i přičítání jedničky k proměnné Zacatek.
Aby nám fronta fungovala korektně, zbývá jen ošetření chyb. Protože programátor nemůže (nebo ani nechce) pořád složitě kontrolovat, zda nevkládá prvek do přeplněné fronty, nebo naopak se nepokouší číst z fronty prázdné, měla by taková kontrola být součástí funkcí Fronta_vlož a Fronta_vyjmi. Jak na to?
Můeme to vyřešit například takto:
Při vybírání prvku z fronty se musí zkontrolovat, zda fronta není prázdná. To je tehdy, kdy Zacatek=Konec.
Vkládáme-li prvek do fronty, pak podle popisu funkce Fronta_vlo uložíme prvek na pozici Konec a proměnou Konec zvýšíme o 1 (popř. nastavíme na 0). Konec tedy ukazuje na první volné políčko. Proměná Zacatek zase ukazuje na první použité políčko. Před vložením prvku zkontrolujeme, zda na následující prvek neukazuje Zacatek. Kdyby ano, tak je fronta plná, nic nevložíme a oznámíme to např. pomocí návratové hodnoty.
Při tomto způsobu nám vždy zůstane jedno políčko volné - to, na které ukazuje index Konec. To je nám dobré k tomu, abychom rozlišili, kdy je fronta plná a kdy je úplně prázdná.
