Zásobník (datová struktura)
Z Wikipedie, otevřené encyklopedie
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ů.
[editovat] 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 Turing-kompletní, 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:
- Java
- Lisp
- PostScript – jazyk pro popis stránky
[editovat] 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)
- přidání položky na vrchol zásobníku (push)
- odebrání položky z vrcholu zásobníku (pull nebo pop)
- 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
Pro fyzickou implementaci zásobníku lze použít například pole nebo lineární seznam.
