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

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

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)

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

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

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

(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

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

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

(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)

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

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

U zásobník implementovaného polem se musí jen ohlídat velikost pole (klasika). Jinak nic zvláštního.

Příklad

(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

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

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

(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;