Čo je zásobník

Zásobník je jednoduchá abstrakcia pre kolekciu prvkov, v ktorej sa prístup uskutočňuje len na jednom mieste — na vrchole zásobníka. Táto politika sa nazýva LIFO (last-in, first-out) alebo ekvivalentne FILO (first-in, last-out). Predstavte si kôpku tanierov: pridávate a odoberáte iba ten, ktorý je navrchu. Zásobník sa používa ako základná stavebná jednotka v rôznych algoritmoch a programoch, pretože operácie sú rýchle a jednoducho sa implementujú.

Základné operácie a vlastnosti

Typické operácie, ktoré zásobník podporuje, sú:

  • push(x) — vloženie prvku x na vrchol zásobníka;
  • pop() — odstránenie a vrátenie prvku z vrcholu (chyba pri prázdnom zásobníku, tzv. underflow);
  • peek() alebo top() — prehliadnutie prvku na vrchole bez jeho odstránenia;
  • isEmpty() — overenie, či je zásobník prázdny;
  • size() — počet prvkov (ak je táto informácia udržiavaná).

Časová zložitosť týchto operácií býva O(1). Z praktického hľadiska môžu byť zásobníky obmedzené (statická kapacita) alebo dynamické (rastú podľa potreby), pričom pri obmedzenom zásobníku treba riešiť pretek (overflow).

Bežné implementácie

Zásobník možno implementovať viacerými spôsobmi, najčastejšie sú:

  • pole (statické alebo dynamické) — jednoduché a rýchle, treba sledovať index vrcholu;
  • singly linked list (jednosmerný zoznam) — flexibilný, rýchle operácie pri hlave zoznamu, žiadne kopírovanie pri raste;
  • vrstvy jazyka alebo knižnice — v mnohých jazykoch existuje vstavaná štruktúra alebo trieda pre zásobník.

Niekedy sa používajú špecializované varianty: vytrvalé (persistent) zásobníky, obmedzené monotónne zásobníky používané v optimalizačných algoritmoch, či dvojsmerné štruktúry (deque) umožňujúce prácu z oboch strán.

História a vznik

Koncept zásobníka vznikol prirodzene pri prvých potrebách usporiadania dát a ovládania toku programu. Zásobník sa stal kľúčovým v návrhu počítačovej architektúry pre ukladanie návratových adries volaní podprogramov (call stack). Postupne sa stal štandardnou abstrakciou v teorii počítania, implementácii kompilátorov a pri návrhu algoritmov, ktoré potrebujú reverzné spracovanie vstupu alebo dočasné ukladanie stavov.

Použitie a príklady

Zásobník má široké uplatnenie v informatike a programovaní. Medzi typické príklady patrí:

  1. volanie funkcií a návratové adresy v call stacku;
  2. rekurzívne algoritmy implementované iteratívne pomocou zásobníka;
  3. parsovanie výrazov, overovanie zátvoriek a premena do poľského zápisu;
  4. algoritmy prehľadávania grafov do hĺbky (DFS);
  5. mechanizmy undo/redo v editore — posledná akcia je prvá, ktorú vrátime späť;
  6. vyhodnocovanie výrazov so zohľadnením priority operácií.

Tieto príklady ilustrujú, prečo je zásobník také univerzálne a prečo sa objavuje v mnohých rôznych častiach softvéru a teórie.

Porovnanie a dôležité poznámky

Zásobník kontrastuje s frontou (queue), ktorá používa FIFO poradie. Voči všeobecným kolekciám je zásobník obmedzený prístupom len k vrcholu, čo je však výhodné pre rýchlosť a jednoduchosť. Pri návrhu treba zvážiť riziko pretečenia zásobníka pri obmedzenej kapacite a tiež správu pamäte pri rekurzii (prehĺbenie volaní). Pre ďalšie informácie a fundamentálne definície si môžete pozrieť všeobecné zdroje: preskúmať spojitosti, doplňujúci materiál alebo príklady a implementácie.