Juraj na 20:10, 16. august 2010

2010-08-16T20:10:44Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} Dátová štruktúra Zásobník, označovan…“

2010-07-30T14:37:14Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} Dátová štruktúra Zásobník, označovan…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
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=
[[Súbor:Data stack.svg|thumb|right|Princíp zásobníka]]
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:

[[Súbor:pridavanie 1 lifo.png|framed|center|Úspešné pridávanie údajov do zásobníka]]

Pri pokuse vložiť do plného zásobníka ďalší údaj, skončí táto operácia neúspechom.

[[Súbor:pridavanie 2 lifo.png|framed|center|Neúspešné pridávanie údajov do zásobníka]]

Pri výbere údajov zo zásobníka je operácia úspešná len vtedy, ak nie je zásobník prázdny.

[[Súbor:vyber lifo.png|framed|center|Výber údajov zo zásobníka]]

==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.

[[Súbor:zasobnik lifo.png|thumb|right|Zásobník LIFO]]

V nasledujúcom texte budeme pracovať so zásobníkom, ktorý bude ukladať celočíselné hodnoty.

Návrh dátovej štruktúry LIFO:
<source lang="c">
#define MAX_PAMAT 20
struct LIFO{
int pamat[MAX_PAMAT];
int vrchol;
};
</source>
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'':
<source lang="c">
enum stav_fronty
{
OK=-1,
FULL=-2,
EMPTY=-3
};
</source>

Zdrojový kód v jazyku C:
<source lang="c" line >
stav_fronty push(LIFO &zasobnik,int x)
{
if(zasobnik.vrchol<MAX_PAMAT)
zasobnik.pamat[zasobnik.vrchol++]=x;
else
return FULL;
return OK;
}
</source>

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:
<source lang="c" line line>
int pop(LIFO &zasobnik)
{
if(zasobnik.vrchol>0)
return zasobnik.pamat[ --zasobnik.vrchol];
else
return EMPTY;
}
</source>

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.
<source lang="c" line line>
int top(LIFO &zasobnik)
{
if(zasobnik.vrchol>0)
return zasobnik.pamat[zasobnik.vrchol];
else
return EMPTY;
}
</source>
===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

<source lang="c">
int is_empty(LIFO &zasobnik)
{
return zasobnik.vrchol==0 ? 1:0;
}

int volne_miesta(LIFO &zasobnik)
{
return MAX_PAMAT - zasobnik.vrchol;
}
</source>

=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 - [[Štruktúry (riešené príklady)#Zásobník - pamäť typu LIFO|Zásobník - pamäť typu LIFO]]
=Použitá literatúra=
* http://cs.wikipedia.org/wiki/Z%C3%A1sobn%C3%ADk_%28datov%C3%A1_struktura%29
* http://cs.wikipedia.org/wiki/Fronta_a_z%C3%A1sobn%C3%ADk#Z.C3.A1sobn.C3.ADk_.28LIFO.29
* http://en.wikipedia.org/wiki/Stack_%28data_structure%29

@@ Riadok 1: / Riadok 1: @@
 [[Kategória:Študijné materiály]]
-[[Kategória:Programovanie]]
+[[Kategória:Algoritmy a programovanie]]
 [[Kategória:Informatika]]
 {{Draft}}

Zásobník - História úprav

Juraj na 20:10, 16. august 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} Dátová štruktúra Zásobník, označovan…“