Zásobník (dátová štruktúra): princíp, operácie a použitie

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.