Zásobník (Stack)

Zásobník (anglicky Stack) je abstraktní datová struktura, která slouží k ukládání prvků v lineárním uspořádání. Je fundamentální součástí informatiky a funguje na principu LIFO (Last In, First Out), což v překladu znamená „poslední dovnitř, první ven“.

Tuto strukturu si lze představit jako tos talířů v jídelně:

• Když přinesete nový talíř, položíte ho nahoru na ostatní.
• Když si chcete vzít talíř, musíte vzít ten, který je nahoře (ten, který byl položen jako poslední).
• Není možné bezpečně vytáhnout talíř ze spodní části, aniž byste odebrali ty nad ním.

• Lineární struktura: Prvky jsou řazeny za sebou.
• Omezený přístup: Přistupovat lze pouze k prvku na vrcholu (Top).
• Efektivita: Vložení a odebrání prvku má konstantní časovou složitost O(1).

Každá implementace zásobníku musí podporovat následující základní operace:

V programování lze zásobník implementovat dvěma hlavními způsoby:

Jedná se o statickou implementaci.

• Výhody: Rychlý přístup, paměťová efektivita (není třeba ukládat ukazatele).
• Nevýhody: Pevná velikost. Pokud se zásobník naplní, dojde k chybě Stack Overflow (pokud není pole dynamicky realokováno).

Jedná se o dynamickou implementaci.

• Výhody: Velikost je omezena pouze pamětí počítače, roste podle potřeby.
• Nevýhody: Vyšší paměťová náročnost (každý prvek potřebuje extra paměť pro odkaz na další prvek).

class Stack {
    pole data[100];
    int top = -1; // Ukazatel na vrchol (prázdný zásobník)
 
    void push(x) {
        top++;
        data[top] = x;
    }
 
    int pop() {
        if (top == -1) return error;
        hodnota = data[top];
        top--;
        return hodnota;
    }
}

Zásobník je jednou z nejpoužívanějších struktur, často i tam, kde to uživatel nevidí.

Pravděpodobně nejdůležitější využití. Když program zavolá funkci:

1. 1. Adresa návratu a lokální proměnné jsou uloženy na zásobník (tzv. Stack Frame).
2. 2. Pokud tato funkce zavolá další funkci, přidá se na vrchol nový Stack Frame.
3. 3. Jakmile funkce skončí, její rámec je odstraněn (Pop) a řízení se vrací funkci pod ní.

> Poznámka: Pokud dojde k nekonečné rekurzi, paměť zásobníku se vyčerpá a program spadne na chybu Stack Overflow.

Textové editory (Word, VS Code) používají dva zásobníky pro sledování změn:

• Když napíšete text, akce se uloží do zásobníku Undo.
• Když stisknete Ctrl+Z, akce se přesune ze zásobníku Undo do zásobníku Redo.

Kompilátory používají zásobník pro kontrolu, zda jsou závorky ve zdrojovém kódu správně spárovány.

• Otevírací závorka ``(``, ``{``, ``[`` → Push.
• Zavírací závorka ``)``, ``}``, ``]`` → Pop (a zkontroluje se shoda).
• Pokud je na konci zásobník prázdný, syntaxe je správná.

Zásobník se používá pro vyhodnocování matematických výrazů zapsaných v Reverzní polské notaci (např. ``3 4 +`` místo ``3 + 4``).

Je důležité nezaměňovat zásobník s frontou.

Operace nad zásobníkem jsou extrémně rychlé, protože se vždy pracuje pouze s jedním koncem datové struktury.

• Přístup (Access): O(n) (Zásobník není určen k prohledávání, pro přístup k n-tému prvku musíme odebrat vše nad ním).
• Hledání (Search): O(n)
• Vložení (Push): O(1)
• Smazání (Pop): O(1)

Autorem tohoto textu je AI asistent (2025).