Zásobník
Dátová štruktúra Zásobník, označované aj ako pamäť LIFO. LIFO je skratka z anglického Last In First Out.
Pamäť LIFO
Zásobník je v všeobecná dátová štruktúra (tzv. abstraktný dátový typ) používaná pre dočasné ukladanie dát. Používa sa aj anglické označenie stack. Pre zásobník je charakteristický spôsob manipulácie s dátami - dáta, ktoré sú do pamäti vložené ako posledné, budú čítané ako prvé.
Pre manipuláciu s uloženými dátovými položkami sa sa používa tzv. ukazateľ zásobníka, ktorý udáva relatívnu adresu poslednej pridanej položky, tzv. vrchol zásobníku.
Obsahom zásobníka môžu byť akékoľvek dátové štruktúry. Môže byť realizovaný ako programovými prostriedkami, tak aj elektronickými obvodmi.
Implementácia zásobníka
Pri práci so zásobníkom (LIFO) platia nasledujúce tvrdenia:
- dátový typ zásobník (LIFO) model pamäte,
- kapacita pamäte je obmedzená; vždy je definovaná veľkosť pamäte,
- pri vkladaní údajov do zásobníka neurčujeme adresu, kde sa dáta zapíšu,
- vkladané dáta sa zapíšu na vrchol zásobníka (ak nie je zásobník plný),
- vrchol zásobníka obsahuje hodnotu (resp. adresu) vrcholu zásobníka, teda miesta, ktoré je voľné,
- pri čítaní údajov zo zásobníka sa taktiež nedefinuje adresa z ktorej sa budú dáta čítať,
- pri čítaní sa vždy prečíta údaj, ktorý bol vložený posledný,
- dátové položky zásobníka môžu byť ľubovoľné dátové typy (štruktúra, pole, smerník, ...)
Princíp práce so zásobníkom
Pre prácu zo zásobníkom definujme nasledujúce operácie:
- pridanie jedného prvku do zásobníka (push)
- odobratie jedného prvku zo zásobníka (pop)
- prečítanie hodnoty z vrcholu zásobníka (top)
- test na veľkosť zásobníka (is_empty)
Pridávanie nových údajov do zásobníka je znázornené na nasledujúcom obrázku:
Pri pokuse vložiť do plného zásobníka ďalší údaj, skončí táto operácia neúspechom.
Pri výbere údajov zo zásobníka je operácia úspešná len vtedy, ak nie je zásobník prázdny.
Návrh dátovej štruktúry pre zásobník
Dátová štruktúra LIFO pozostáva z 2 častí:
- miesto, kde budú uložené samotné dáta,
- pre uloženie samotných dát môžeme použiť dátovú štruktúru pole s definovanou veľkosťou
- indikátor zaplnenia zásobníka, resp. vrchol zásobníka.
- keďže dáta sú uložené v jednorozmernom poli, tak ukazateľ (pozor, teraz nemyslím smerník, resp. pointer) na vrchol môže byť celočíselná premenná, ktorá by udávala index prvku poľa.
V nasledujúcom texte budeme pracovať so zásobníkom, ktorý bude ukladať celočíselné hodnoty.
Návrh dátovej štruktúry LIFO:
#define MAX_PAMAT 20
struct LIFO{
int pamat[MAX_PAMAT];
int vrchol;
};
Treba povedať, že premenná vrchol štruktúry LIFO má hodnotu prvého voľného prvku v pamäti LIFO.
Implementácia zásobníka v jazyku C
Pridávanie do zásobníka
Funkcia push bude pridávať položky do zásobníka. Funkcia bude mať jeden parameter - údaj, ktorý chceme do zásobníka vložiť.
Počas tejto operácie môžu nastať nasledujúce prípady:
- vloženie bolo úspešné (stav OK)
- vloženie bolo neúspešné, zásobník bol pred vložením plný (stav FULL)
Pre reprezentáciu týchto stavom navrhneme špeciálny vymenovaný (enumerated) dátový typ stav_fronty:
enum stav_fronty
{
OK=-1,
FULL=-2,
EMPTY=-3
};
Zdrojový kód v jazyku C:
1 stav_fronty push(LIFO &zasobnik,int x)
2 {
3 if(zasobnik.vrchol<MAX_PAMAT)
4 zasobnik.pamat[zasobnik.vrchol++]=x;
5 else
6 return FULL;
7 return OK;
8 }
Vysvetlenie:
- funkcia push pridá do zásobníka (zasobnik) hodnotu (x)
- Na riadku 4 je samotné vloženie údaja do zásobníka. Nový údaj (x) sa vloží do časti pamat štruktúry LIFO s indexom vrchol. Následne treba hodnotu vrcholu zväčšiť o 1.
- V prípade úspechu (zásobník ešte nie je plný) vráti OK, v opačnom prípade vráti hodnotu FULL
Výber zo zásobníka
Pre výber údajov zo zásobníka slúži funkcia pop. Funkcia pop zabezpečí výber najvrchnejšej hodnoty zo zásobníka. Počas tejto operácie môžu nastať nasledujúce prípady:
- výber bol úspešný (stav OK),
- výber bol úspešný, pretože sme sa pokúsili vybrať údaj z prázdneho zásobníka (stav EMPTY).
Zdrojový kód v jazyku C:
1 int pop(LIFO &zasobnik)
2 {
3 if(zasobnik.vrchol>0)
4 return zasobnik.pamat[ --zasobnik.vrchol];
5 else
6 return EMPTY;
7 }
Vysvetlenie:
- funkcia pop odoberie zo zásobníka (zasobnik) hodnotu na vrchole zásobníka a túto hodnotu vvráti
- Na riadku 4 je samotný výber údaja zo zásobníka. Pri výbere sa skôr ako sa zavolá príkaz return musí znížiť hodnota vrcholu zásobníka o 1. To ale len v tom prípade, ak nie je zásovník prázdny.
- V prípade úspechu (zásobník ešte nie je prázdny) vráti prečítanú hodnotu, v opačnom prípade vráti hodnotu EMPTY
prečítanie hodnoty z vrcholu zásobníka (top) Funkcia top sa od funkcie pop líši len na riadku 4. V prípade funkcie top, nebudeme znižovať hodnotu vrcholu zásobníka.
1 int top(LIFO &zasobnik)
2 {
3 if(zasobnik.vrchol>0)
4 return zasobnik.pamat[zasobnik.vrchol];
5 else
6 return EMPTY;
7 }
Test na veľkosť zásobníka
Počas práce so zásobníkom potrebuje zistiť veľkosť zásobníka, resp. či je zásobník prázdny. Vytvorme nasledujúce funkcie:
- is_empty : vráti hodnotu 1, ak je zásobník prázdy
- volne_miesta : vráti počet voľných miest v zásovníku
int is_empty(LIFO &zasobnik)
{
return zasobnik.vrchol==0 ? 1:0;
}
int volne_miesta(LIFO &zasobnik)
{
return MAX_PAMAT - zasobnik.vrchol;
}
Praktické využitie zásobníka
Stack pointer
Najznámejšou aplikáciou zásobníka je vnútorný zásobník realizovaný procesorom, do ktorého sú ukladané návratové adresy a príznaky stavu procesora pri prerušeniach a skokoch do podprogramov. Pri návrate z podprogramu je z vrcholu zásobníka vybratá návratová adresa a spracovanie pokračuje od prerušeného miesta. Tento zásobník môže byť čisto v procesore, alebo sa fyzicky nachádza v pamäti a procesor obsahuje iba podporu jeho používania. Vo väčšine prípadov (vrátane procesorov architektúry i386) je možné na zásobník v pamäti s podporou procesora ukladať ľubovoľné informácie, čo sa využíva predovšetkým k ukladaniu parametrov funkcií a ich lokálnych premenných.
Intepreter postfixových aritmetických výrazov
Pomocou abstraktného dátového typu (ADT) zásobníka sa dajú veľmi dobre vyhodnocovať práve postfixové aritmetické výrazy. Každý operátor si z vrcholu zásobníka načíta svoje dva operandy a po vykonaní operácie na nich vráti jej výsledok namiesto týchto dvoch operandov na vrchol zásobníka (využitie princípu dátovej štruktúry typu LIFO). Nasledujúci obrázok demonštruje tento jednoduchý princíp na vyhodnocovaní vyššie uvedeného postfixového aritmetického výrazu. Pozri - Zásobník - pamäť typu LIFO
