Zásobník (datová struktura)

Princip zásobníku

Zásobník je v informatice obecná datová struktura (tzv. abstraktní datový typ) používaná pro dočasné ukládání dat. Také se používá anglický výraz stack.

Pro zásobník je charakteristický způsob manipulace s daty - data uložena jako poslední budou čtena jako první. Proto se používá také výraz LIFO z anglického „Last In – First Out“. (Srovnej s FIFO).

Pro manipulaci s uloženými datovými položkami se udržuje tzv. ukazatel zásobníku, který udává relativní adresu poslední přidané položky, tzv. vrchol zásobníku.

Obsahem zásobníku mohou být jakékoli datové struktury. Může být realizován jak programovými prostředky, tak i elektronickými obvody.

Nejznámější aplikací zásobníku je vnitřní zásobník realizovaný procesorem, do něhož jsou ukládány návratové adresy a příznaky stavu procesoru při přerušeních a skocích do podprogramů. Při návratu z podprogramu je z vrcholu zásobníku vyjmuta návratová adresa a zpracování pokračuje od přerušeného místa. Tento zásobník může být čistě v procesoru, nebo se fyzicky nachází v paměti a procesor obsahuje pouze podporu jeho používání. Ve většině případů (včetně procesorů architektury i386) je možné na zásobník v paměti s podporou procesoru ukládat libovolné informace, což se využívá především k ukládání parametrů funkcí a jejich lokálních proměnných.

Zásobník, ať už hardwarový nebo softwarový (emulovaný), je klíčovou datovou strukturou používanou v programování při realizaci rekurzivních algoritmů.

Historie

Zásobník byl poprvé vytvořen v roce 1955, načež byl v roce 1957 patentován Němcem Friedrichem L. Bauerem. Stejný koncept byl nezávisle a v přibližně stejném čase vyvinut Australanem Charlesem L. Hamblinem.

Zásobníková architektura

Jako počítače nebo virtuální stroje se zásobníkovou architekturou se označují takové, které používají zásobník jako základní strukturu pro ukládání mezivýsledků výpočtu. Často nemají žádné nebo jen minimum registrů a omezený přístup k paměti. Aby byly turingovsky úplné, musí buď mít přece jen nějaký přístup k paměti, nebo musí mít zásobníky dva.

Příklady virtuálních strojů se zásobníkovou architekturou:

Minimální implementace zásobníku

Pro implementaci zásobníku jako abstraktního datového typu jsou zapotřebí tato primitiva:

  • inicializace zásobníku (create) - může proběhnout v rámci funkce push
  • přidání položky na vrchol zásobníku (push)
  • odebrání položky z vrcholu zásobníku (pop nebo pull)
  • dotaz na vrchol zásobníku (top)
  • dotaz na prázdnost zásobníku (is_empty) – může se také detekovat v rámci funkce pull

Softwarová implementace zásobníku

Implementace

Ve většině vyšších programovacích jazyků může být zásobník poměrně jednoduše implementován pomocí pole, nebo lineárního seznamu. To, co identifikuje datovou strukturu jako zásobník, není implementace, ale rozhraní - uživatel smí pouze přidávat (push) nebo ubírat (pop) hodnoty z pole či lineárního seznamu spolu s několika málo pomocnými funkcemi. Následující text demonstruje toto pravidlo pomocí jazyka C.

Pole

Implementace pomocí pole se zaměřuje na vytvoření pole, kde se na nulovém indexu (array[0]) nachází dno zásobníku. Program si do pomocné proměnné ukládá, na jakém indexu se nachází vrchol zásobníku - tento index se mění podle toho, jak velikost zásobníku roste, nebo se zmenšuje. V jazyce C může být tento zásobník implementován jako jednoduchá struktura:

    typedef struct {
        int top;
        int items[STACKSIZE];
    } STACK;

Funkce push() je použita k inicializaci zásobníku a zároveň přidání nové hodnoty na jeho vrchol. Je zodpovědná za změnu hodnoty proměnné ps->top a za vložení nového prvku do pole ps->items[]. Funkce také ověřuje, jestli pole není plné; pokud by se pole naplnilo a tato kontrola by zde nebyla, vedlo by to k chybě segmentation fault.

    void push(int x, STACK *ps)
    {
        if (ps->top == STACKSIZE-1) {
            printf("Error: stack overflow");
            exit(EXIT_FAILURE);
        } else 
            ps->items[++(ps->top)] = x;
            
        return;
    }

Funkce pop() odstraňuje prvek z vrcholu zásobníku a dekrementuje hodnotu ps->top. Dále ověřuje, jestli zásobník není prázdný - pokud by zde tato kontrola nebyla, tak by pokus u vyjmutí prvku z již prázdného zásobníku pravděpodobně vedl k chybě segmentation fault.

    int pop(STACK *ps)
    {
        if (empty(ps)) {
            printf("Error: stack underflow");
            exit(EXIT_FAILURE);
        } else 
            return(ps->items[(ps->top)--]);
    }

Lineární seznam

Implementace pomocí lineárního seznamu je stejně jednoduchá a srozumitelná. Dalo by se říct, že zásobníkový lineární seznam je o dost jednodušší než ostatní obvyklé použití lineárního seznamu - požaduje pouze takovou implementaci, kde může být přidán nebo odebrán pouze vrchní element.

Na rozdíl od implementace pomocí pole tato struktura neodpovídá celému zásobníku, ale pouze jedinému elementu:

    typedef struct stack {
        int data;
        struct stack *nxt;
    } STACK;

Tato struktura odpovídá typickému prvku lineárního seznamu (minimálně v C).

Funkce push() má za úkol inicializovat prázdný zásobník a přidat nový prvek k neprázdnému seznamu. Funguje tak, že jako parametr dostane nová data spolu s adresou cílového zásobníku, načež vytvoří nový prvek seznamu tím, že mu alokuje paměť, a pak ho vloží do seznamu jako nový vrchol:

    void push(int nw, STACK **hd)
    {
        STACK *node= (STACK*) malloc(sizeof(STACK));  /* vytvoř nový prvek */
                
        if (node == NULL) {
            printf("Error: no space available for node");
            getchar();
            exit(EXIT_FAILURE);
        } else {                                      /* inicializuj prvek */
            node->data = nw;                          
            node->nxt = NULL;
        }
    
        if (empty(*hd))                                /* inicializuj seznam */
            *hd = node;
        else {                                        /* vlož nový vrchol */
            node->nxt = *hd;
            *hd = node;
        }
    
        return;
    }

Funkce pop() odstraní vrchol zásobníku ze seznamu a přiřadí ukazatel na vrchol zásobníku předchozímu prvku. Ověřuje, jestli seznam není prázdný před tím, než z něj odebere prvek:

    int pop (STACK **hd)
    {
        int value;
        STACK *dummy;
    
        if (empty(*hd)) {                             /* zásobník je prázdný */     
           printf("Stack is empty");
           getchar();
        } else {                                     /* odeber prvek */
            value = (*hd)->data;
            dummy = *hd;
            *hd = (*hd)->nxt;
            free(dummy);
        }
    
        return value;
    }

Zásobník a programovací jazyky

Některé jazyky jako Lisp a Python nepotřebují implementace zásobníku, protože funkce push a pop jsou dostupné ke každému seznamu. Všechny Forthu podobné jazyky (např. Adobe PostScript) jsou navrženy okolo zásobníku, který je viditelný a přístupný programátorovi.

C++ a jeho Standard Template Library poskytují "stack" šablonu tříd, které jsou omezeny jenom na push a pop operace. Java obsahuje třídu Stack, která je odvozena od třídy Vector, což může být považováno za chybu návrhu, protože zděděná metoda get() ignoruje LIFO model zásobníku.

Podobné datové struktury

Funkcí se zásobníku podobá fronta, která s ním může být zkombinovaná do obousměrně ukončené fronty. Stručně řečeno, fronta je struktura typu FIFO.

Složitost v závislosti na implementaci

Zásobník lze implementovat (nejen) pomocí paměťového pole s vrcholem na začátku, pole s dnem na začátku a jednosměrného spojového seznamu. V těchto implementacích je pro všechny operace asymptotická složitost operací konstantní - mimo push a pop v poli s vrcholem na začátku. V tomtě případech je asymptotická složitost O(n).

Hardwarová implementace zásobníku

Nejčastější použití zásobníku na úrovni hardwaru (architektury) je jako prostředek k alokování a přidělování paměti.

Základní architektura zásobníku

Typická ukázka zásobníku rostoucího směrem dolů. Tento typ je používaný velice často, ale je náchylný k útokům pomocí přetečení na zásobníku.

Nejčastěji je zásobník část paměti počítače s pevně danou počáteční adresou a proměnnou velikostí. Na začátku je velikost stacku 0. Ukazatel velikosti zásobníku (nejčastěji registr) ukazuje na adresu začátku zásobníku.

Dvě základní operace použitelné na jakýkoliv zásobník jsou:

  • push
    • data jsou přidána na adresu paměti, na kterou ukazuje ukazatel velikosti zásobníku a adresa ukazatele je změněna o velikost paměti zabranou daty
  • pop nebo pull
    • data jsou vyjmuta z adresy, na kterou ukazuje ukazatel velikosti zásobníku a jeho adresa je změněna o velikost paměti kterou na zásobníku zabírala data

Existuje několik variací základních operací nad zásobníkem. Každý zásobník má v paměti pevně danou pozici kde začíná. Jak jsou data přidávána, ukazatel zásobníku je měněn tak, aby ukazoval aktuální velikost zásobníku, která se mění směrem od počáteční adresy zásobníku (buď dolu, nebo nahoru v závislosti na implementaci).

Například zásobník může začínat na adrese 1000 a expandovat směrem dolu, díky čemuž jsou nová data uchovávána na adrese 1000 a ukazatel velikosti zásobníku je dekrementován pokaždé, když je přidán nový prvek. Pokud je prvek ze zásobníku odebrán, ukazatel je inkrementován. Maximální možná adresa na kterou je možné uložit data je 0.

Ukazatel velikosti zásobníku může ukazovat na počáteční adresu zásobníku, nebo na omezený počet adres pod, nebo nad počáteční adresou (záleží na tom jestli roste nahoru, nebo dolu), ale nikdy nesmí ukazovat za tuto hranici. Jinak řečeno, pokud je počáteční adresa 1000 a zásobník roste dolu (nabírá hodnot 999, 998 atp..), ukazatel nikdy nesmí být inkrementován přes 1000 (1001, 1002 etc..). Pokud přílišné volání funkce pop způsobí změnu adresy nad tuto hodnotu, dochází k podtečení zásobníku. Jestliže nastane příliš volání funkce push a ukazatel velikosti zásobníku bude ukazovat za minimální (nebo maximální v případě rostoucího zásobníku) adresu, dochází k přetečení zásobníku.

Některá prostředí, která opravdu závisí na zásobníku mohou nabízet dodatečné operace nad zásobníkem:

  • Dup(likovat)
    • vrchol zásobníku je vyjmut a vložen dvakrát, takže kopie vrcholu je nyní nejvýše s originálem pod sebou
  • Peek
    • vrchol je vrácen jako v případě pop, ale ukazatel velikosti zásobníku a velikost stacku zůstává nezměněna
    • tato operace je často v literatuře nazývána též top
  • Swap nebo Exchange
    • vrchol zásobníku si prohodí místo s prvkem pod ním
  • Rotate
    • n nejvyšších prvků je přemístěno rotací (viz dál)
    • existují dva základní způsoby rotace - rotace vlevo a rotace vpravo

Zásobník je často zobrazován jak roste směrem nahoru (viz obrázek na vrcholu stránky), nebo směrem zleva doprava, takže nejvyšší hodnota je hodnota nejvíce vpravo. Toto znázornění může být nezávislé na skutečné struktuře zásobníku v paměti. Rotace vpravo pak znamená, že prvek na prvním místě se přemístí na třetí místo, druhý na první a třetí na místo druhého. Zde je znázornění tohoto procesu;

jablko                        banán
banán    → rotace vpravo →    okurka
okurka                        jablko

okurka                        jablko
banán     → rotace vlevo →    okurka 
jablko                        banán

V počítači je zásobník obvykle reprezentován jako blok paměťových buněk s "dnem" na pevně dané adrese, přičemž ukazatel na vrchol ukazuje na momentálně nejvyšší zabranou buňku zásobníku (vrchol). Termíny vrchol a dno jsou používány bez ohledu na to, jestli zásobník roste v paměti nahoru (98, 99, 100 ..), nebo dolu (100, 99, 98 ..).

Vrchol zásobníku

Vložením prvku na zásobník je ukazatel vrcholu změněn o velikost prvku (jestli je inkrementován nebo dekrementován záleží na tom kam zásobník v paměti roste), takže ukazuje na novou buňku paměti kam nakopíruje nový vrchol zásobníku.

Při vkládání (push) může ukazatel na konci operace ukazovat na vrchol zásobníku, nebo na následující volnou buňku. Pokud ukazuje na vrchol zásobníku, tak bude aktualizován před tím než bude na danou adresu vložen nový prvek.

Vyjmutí (pop) hodnoty ze zásobníku je jednoduše inverzní operace k vkládání. Prvek na vrcholu je odstraněn a ukazatel je aktualizován v opačném pořadí než jaké bylo použito při vkládání.

Hardwarová podpora

Zásobník v hlavní paměti

Hodně CPU má registry, které mohou být použity jako ukazatele vrcholu. Některé (např. Intel x86 a Zilog Z80) mají speciální instrukce, které implicitně používají registr který byl vyhrazený k použití pro ukazatel Ostatní (např. DEC PDP-11 a řada Motorola 68000) mají módy adresování které umožňují použít jakýkoliv registr pro ukazatel.

Zásobník v registru

Série numerických koprocesorů Intel 80x87 má řadu registrů které mohou být adresovány jako zásobník, nebo jako sada číselných registrů. Počítače Sun SPARC mají řadu registrových oken organizovaných jako zásobník, takže podstatně redukují místo v paměti které zabírají argumenty funkcí a návratové hodnoty.

Zásobník v oddělené paměti

Existuje řada mikroprocesorů. které implementují zásobník přímo v hardwaru; některé mikrokontrolery mají zásobník s pevně danou délkou, přičemž zásobník není přímo přístupný.

Hodně mikroprocesorů založených na stacku je používáno k běhu programovacího jazyka Forth na úrovní mikrokódu. Zásobník je také často používán jako základ mainfraimů a minipočítačů. Tyto stroje se nazývají zásobníkový počítač.

Reference

V tomto článku byl použit překlad textu z článku Stack (data structure) na anglické Wikipedii.

Související články

Externí odkazy

Média použitá na této stránce

ProgramCallStack2.svg
Autor: Vektorizace: OmenBreeze, Licence: Attribution
Přeložený obrázek principu hardwarové implementace zásobníku.
Data stack.svg
Simple representation of a stack