Fronta a zásobník
Fronta a zásobník jsou datové struktury, které v programech slouží k dočasnému ukládání dat (nejčastěji k ukládání v operační paměti počítače).
Základní rozdíl editovat
Fronta slouží k ukládání dat, která z ní vystupují ve stejném pořadí, jako do ní vstupují. Odborně se nazývá FIFO (z anglického First In, First Out, česky První dovnitř, první ven; někdy se také označuje jako tunel). Lze si ji představit jako frontu lidí, kteří postupují k pokladně. Jak se řadí do fronty, tak i odcházejí od pokladny. Zásobník je přesně naopak, první data do zásobníku vložená vystupují ze zásobníku jako poslední. Odborně LIFO (z anglického Last In, First Out, česky Poslední dovnitř, první ven). Zároveň se označuje i jako studna nebo díra, protože když je něco uloženo do díry jako první, je to možné vyndat až jako poslední (resp. až se odstraní všechno ostatní, co následně na první prvek bylo položeno).
Spojový seznam editovat
V tomto článku jsou uvedeny příklady s implementací pomocí ukazatele neboli dynamické proměnné. Tato struktura se používá pro zápis do nových proměnných za běhu aplikace. Jednou z možností tvorby struktury je i spojový seznam, který je právě zde uveden.
Fronta (FIFO) editovat
V praxi se používá např. k vyrovnání rychlostí dvou datových toků, tj. data přicházející z internetu (např. streamované video) a datový tok, který má video při přehrávání. Také se s frontou lze setkat při vypalování. Vypalovaná data z disku počítače se „sunou“ obvykle jinou rychlostí, než jak potřebuje vypalovačka (k tomu patří často zmiňované pojmy jako přetečení nebo podtečení bufferu, viz níže). Přímo v programu se fronta používá např. při postupném zkoumání vstupních znaků od uživatele – char (laicky řečeno: co uživatel napsal, postupně se zkoumá jeden znak za druhým a celý řetězec písmen je vlastně fronta).
Základní operace s frontou:
- vytvoření prázdné fronty
- vložení prvku na konec fronty (přidání, zápis)
- odebrání prvku na začátku fronty (čtení)
- test prázdnosti fronty (abychom nemuseli číst, když tam nic není)
Implementace pomocí pole editovat
Jako úložný prostor pro frontu je možné v nejjednodušším případě použít obyčejné pole (array), odborně se tomuto případu říká implementace pomocí pole. Při běhu se do položek pole umisťují data jedno za druhým, tj. do položky 1, 2, 3 atd. Zároveň se data čtou, opět postupně.
Problematika editovat
Pole při tomto řešení má omezenou délku (definují se proměnné na začátku programu ve formě např. pole:arrays[1..1000] of integer, takové pole může mít maximálně 1000 míst pro uložení dat ve frontě). Tím, jak se data do pole zapisují a čtou, posouvají se právě zapsaná data polem až ke konci. Tam se zastaví.
Jednoduchým řešením by bylo při každém přečtení všechny položky v poli posunout na začátek, to ovšem není nejlepší především u velkých polí s množstvím dat. Proto se používá tzv. kruhová fronta, neboli, když dojde zápis na konec pole, zapisuje se opět na volné místo na začátku. Celé to funguje jako had, který na konci zalézá do díry a opět vylézá na začátku.
Nesmí se nikdy zapomenout na důležitost kontroly plnosti fronty, resp. jestli místo, ze kterého se čte nebo do kterého se zapisuje, je plné (obsahuje data), jinak následuje podtečení nebo přetečení fronty.
Příklad editovat
(Pascal)
const MaxDelka = N; {N je číslo omezující délku fronty}
type TFronta = record
polozky:array[0..MaxDelka-1] of datovytyp;
zacatek, konec: 0..MaxDelka;
end;
procedure FrontaVytvor(var fronta:TFronta);
begin
fronta.zacatek := 0;
fronta.konec := 0;
end;
function FrontaPrazdna(fronta:TFronta): boolean;
begin
FrontaPrazdna := (fronta.zacatek=fronta.konec);
end;
function FrontaPlna(fronta:TFronta): boolean;
begin
FrontaPlna := (fronta.zacatek=((fronta.konec+1) mod MaxDelka));
end;
procedure FrontaVloz(var fronta:TFronta; X: datovytyp);
begin
if FrontaPlna(fronta) then
begin {ošetření překročení maximální velikosti}
...
end
else
begin
fronta.polozky[fronta.konec] := X;
fronta.konec := (fronta.konec + 1) mod MaxDelka;
end;
end;
procedure FrontaOdeber(var fronta:TFronta; var X: datovytyp);
begin
if FrontaPrazdna(fronta) then
begin {ošetření prázdnosti fronty}
...
end
else
begin
X := fronta.polozky[fronta.zacatek];
fronta.zacatek := (fronta.zacatek + 1) mod MaxDelka;
end;
end;
Implementace pomocí ukazatele editovat
Tento způsob vytvoření fronty je poněkud složitější, ale odpadá zde problém s velikostí pole. Místo pole se používá ukazatel do operační paměti. Tímto lze zapisovat data tak dlouho, dokud je dostatek operační paměti (jelikož systém dnes umí rozšířit paměť RAM i na volné místo na pevném disku, je k dispozici opravdu velké množství paměti, řádově GB). Při použití pole je omezení na 64kB (podle nastavení kompilátoru).
Samotné vytvoření je založeno na klasické implementaci pomocí ukazatele. Nekontroluje se však dostupné místo v poli a dostupnou RAM; je nutné dávat pozor na cyklické chyby, které by znamenaly zaplnění RAM a následný kolaps aplikace a někdy i celého systému.
Problematika editovat
Snaha udělat stabilní frontu implementovanou ukazatelem přináší značnou obtíž určit, kolik paměti je vlastně k dispozici a kolik ji zabírá samotný program. Způsobů hlídání je mnoho a liší se v závislosti na operačním systému. Nejpodstatnější je kontrola volné paměti. Všeobecně je dosti důležité najít vhodné řešení kontroly paměti, protože se jedná o choulostivou část běhu aplikace.
Příklad editovat
(Pascal)
type spoj = ^element;
element = record
hodnota: datovytyp;
dalsi: spoj;
end;
var zacatek, konec: spoj;
procedure Vytvor;
begin
new(zacatek);
konec := zacatek;
end;
procedure Vloz(X: datovytyp);
begin
konec^.hodnota := X;
new(konec^.dalsi);
konec := konec^.dalsi;
end;
procedure Odeber(var X: datovytyp);
var pom: spoj;
begin
if zacatek = konec then
begin
write('Pozor - fronta je prazdna.');
Halt;
end
else
begin
X := zacatek^.hodnota;
pom := zacatek;
zacatek := zacatek^.dalsi;
dispose(pom);
end;
end;
function JePrazdna: boolean;
begin
if zacatek = konec then JePrazdna := true
else JePrazdna := false;
end;
Zásobník (LIFO) editovat
V praxi se používá především pro ukládání rekurzí. Příkladem by mohl být program, který počítá jako kalkulačka se závorkami. Každá závorka v závorce je rekurzí. Když se hledá jedna závorka za druhou, zároveň se naráží na další, které se nacházejí uvnitř. Tímto se vytváří jakýsi strom. Prohledáním se zapíše do zásobníku obsah závorek a pak se kalkuluje nejprve ta poslední nalezená. Asi nejběžnějším příkladem je historie v prohlížečích. Když se klikne na zpět, otevře se posledně otevřená stránka.
Implementace pomocí pole editovat
Stejně jako u fronty se jedná o nejjednodušší formu zásobníku. Na rozdíl o fronty je zásobník celkově snadnější, protože není nutné počítat s tím, že se data budou „točit“ z konce na začátek (viz výše, kruhová fronta). Bude opět potřebné pole, do něhož se zapíší data postupně, ale číst se budou od vrcholu zásobníku.
Problematika editovat
U zásobník implementovaného polem se musí jen ohlídat velikost pole (klasika). Jinak nic zvláštního.
Příklad editovat
(Pascal)
const MaxDelka = N; {N je číslo omezující max. délku zásobníku}
type TZasobnik = record
polozky:array[1..MaxDelka] of datovytyp;
vrchol: 0..MaxDelka;
end;
procedure ZasobnikVytvor(var zasobnik:TZasobnik);
begin
zasobnik.vrchol := 0;
end;
function ZasobnikPrazdny(zasobnik:TZasobnik):boolean;
begin
ZasobnikPrazdny:=(zasobnik.vrchol=0);
end;
function ZasobnikPlny(zasobnik:TZasobnik):boolean;
begin
ZasobnikPlny:=(zasobnik.vrchol=MaxDelka);
end;
procedure ZasobnikVloz(var zasobnik:TZasobnik; X: datovytyp);
begin
if ZasobnikPlny(zasobnik) then
begin {ošetření překročení maximální velikosti}
...
end
else
begin
zasobnik.vrchol := zasobnik.vrchol + 1;
zasobnik.polozky[zasobnik.vrchol] := X;
end;
end;
procedure ZasobnikOdeber(var zasobnik:TZasobnik; var X: datovytyp);
begin
if ZasobnikPrazdny(zasobnik) then
begin {ošetření prázdnosti zásobníku}
...
end
else
begin
X := zasobnik.polozky[zasobnik.vrchol];
zasobnik.vrchol := zasobnik.vrchol - 1;
end;
end;
Implementace pomocí ukazatele editovat
Podobně jako u fronty je možné zapisovat přímo do operační paměti za běhu aplikace. Nemusí se hlídat velikost pole, ale musí se hlídat volná paměť. Princip leží na připojování a odpojovaní položek spojového seznamu. Trochu více v odstavci implementace ukazatelem u fronty a v článku o Dynamických strukturách (proměnných).
Problematika editovat
Stejně jako u fronty je důležitá kontrola volné paměti. Pokud se bude zapisovat a nebude k dispozici, následuje kolaps aplikace a někdy i celého systému.
Příklad editovat
(Pascal)
type spoj = ^element
element = record
hodnota: datovytyp;
dalsi: spoj;
end;
var zasobnik : spoj;
procedure Vytvor;
begin
zasobnik := nil;
end;
procedure Vloz(X: datovytyp);
var pom: spoj;
begin
new(pom);
with pom^ do
begin
hodnota := X;
dalsi := zasobnik;
end;
zasobnik := pom;
end;
procedure Odeber(var X: datovytyp);
var pom: spoj;
begin
if zasobnik = nil then
begin
write('Pozor - zasobnik je prazdny.');
Halt; //někdy se používá Exit;
end;
else
begin
X := zasobnik^.hodnota;
pom := zasobnik;
zasobnik := zasobnik^.dalsi;
dispose(pom);
end;
end;
function Jeprazdny: boolean;
begin
if zasobnik = nil then Jeprazdny := true;
else Jeprazdny := false;
end;