5. Zásobník

5.1  Čo je to?

Zásobník (stack) je taký lineárny zoznam, na ktorom sú definované iba tieto operácie:

• vytvoriť prázdny zásobník
• pridať nový prvok na vrch zásobníka (na začiatok zoznamu)
• odobrať prvok z vrchu zásobníka (zo začiatku zoznamu)
• zistiť, či je zásobník prázdny

   Operácia "vlož prvok do zásobníka" sa niekedy v literatúre označuje push. Operácia "vyber prvok zo zásobníka" sa nazýva pop.

Graficky sa zásobník implementovaný ako jednosmerný lineárny zoznam znázorňuje väčšinou takto:

h1,h2, h3, ..., hn sú hodnoty prvkov, ktoré sme do zásobníka vložili Ako ste si isto všimli, prvok, ktorý bol do zásobníka vložený ako posledný, nachádza sa na vrchu zásobníka (na začiatku zoznamu). Prvky sú v zásobníku uložené v opačnom poradí, než v akom sme ich do zásobníka vkladali !

  Prvok v zásobníku, ktorý nemá nasledovníka, nazýva sa aj dno zásobníka.

Princíp, podľa ktorého sa ako prvý musí vždy odstrániť ten prvok zásobníka, ktorý bol do neho vložený ako posledný, sa označuje ako princíp LIFO (z angl. Last In First Out - "posledný príde, prvý odíde"). Zásobník sa preto nazýva aj pamäť LIFO.

Pri práci so zásobníkom si stačí uvedomiť, že priamy prístup (pomocou ukazovateľa na vrch zásobníka) máme len k prvku, ktorý bol vložený ako posledný. Ak chceme pracovať s nejakým iným prvkom v zásobníku, musíme najskôr všetky prvky, ktoré sú nad ním zo zásobníka vybrať (odstrániť alebo premiestniť do pomocného zásobníka).

Zásobníky hrajú dôležitú úlohu pri syntaktickej analýze a konštrukcii prekladačov. Prvoradý význam však majú pri realizovaní rekurzie, kde sa pri každom rekurzívnom volaní funkcie do zásobníka uloží záznam s lokálnymi premennými volanej funkcie a tiež informácia o momentálnom stave výpočtu. Rekurzívny výpočet končí vyprázdnením zásobníka. Vzhľadom na vysoké pamäťové nároky je pri použití rekurzie dobré vedieť odhadnúť jej maximálnu hĺbku. Pri veľkom počte rekurzívnych volaní (napr. pri nekonečnej rekurzii) hrozí totiž preplnenie zásobníka a následne "havária" programu! Nielen pri rekurzii, ale vždy keď sa s nejakej funkcie volá iná funkcia, treba realizáciu volajúcej funkcie prerušiť - uložiť návratovú adresu a začať vypĺňať nový záznam pre volanú funkciu.

Často sa stáva, že úloha potrebuje viac zásobníkov toho istého údajového typu - tzv. homogénne zásobníky. V tomto prípade sa definuje pole, ktoré obsahuje ukazovatele na všetky zásobníky.

  Zásobník sa dá implementovať aj jednorozmerným poľom. Prvý prvok poľa je zvyčajne dno zásobníka, posledný prvok v poli je vrch zásobníka. Ukazovateľ na vrch zásobníka je tu nahradený premennou, v ktorej je uložený index posledného vloženého prvku (t.j. počet prvkov poľa). Nevýhodou je, že musíme vopred obmedziť veľkosť zásobníka stanovením rozsahu použitého poľa.

Precvičme si