Sysop: /* Stack a programovací jazyky */

2022-11-03T11:49:39Z

Stack a programovací jazyky

← Starší verze		Verze z 3. 11. 2022, 11:49
Řádka 144:		Řádka 144:
	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 [[Forth]]u podobné jazyky (např. [[PostScript\|Adobe PostScript]] jsou navrženy okolo zásobníku, který je viditelný a přístupný programátorovi.		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 [[Forth]]u podobné jazyky (např. [[PostScript\|Adobe PostScript]] jsou navrženy okolo zásobníku, který je viditelný a přístupný programátorovi.

-	[[C++]] a jeho [[~~:en:~~Standard Template Library]] poskytují "<code>stack</code>" šablonu tříd, které jsou omezeny jenom na '''push''' a '''pop''' operace. Java obsahuje třídu [http://java.sun.com/javase/6/docs/api/java/util/Stack.html stack], která je odvozena od třídy [http://java.sun.com/javase/6/docs/api/java/util/Vector.html 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.	+	[[C++]] a jeho [[Standard Template Library]] poskytují "<code>stack</code>" šablonu tříd, které jsou omezeny jenom na '''push''' a '''pop''' operace. Java obsahuje třídu [http://java.sun.com/javase/6/docs/api/java/util/Stack.html stack], která je odvozena od třídy [http://java.sun.com/javase/6/docs/api/java/util/Vector.html 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 ===		=== Podobné datové struktury ===

Sysop: 1 revizi

2013-06-16T12:40:08Z

1 revizi

← Starší verze

Verze z 16. 6. 2013, 12:40

Sysop: + Nový článek...jen díky přerušenému přesměrování

2012-09-03T21:57:12Z

+ Nový článek...jen díky přerušenému přesměrování

Nová stránka

[[Soubor:Data stack.png|thumb|220px|right|Princip zásobníku]]
'''Zásobník''' je v [[Informatika (počítačová věda)|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 [[zásobník volání|vnitřní zásobník]] realizovaný [[procesor]]em, 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 [[IA-32|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ž [[hardware|hardwarový]] nebo [[software|softwarový]] (emulovaný) je klíčovou datovou strukturou používanou v [[programování]] při realizaci [[rekurze|rekurzivních]] [[algoritmus|algoritmů]].

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

== Zásobníková architektura ==

Jako počítače nebo [[virtuální stroj]]e 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 procesoru|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 (programovací jazyk)|Java]]
* [[Lisp]]
* [[PostScript]] – jazyk pro popis stránky

== Minimální implementace zásobníku ==

Pro implementaci zásobníku jako abstraktního [[datový typ|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 (datová struktura)|pole]], nebo [[Lineární seznam|lineárního seznamu]]. To co identifikuje datovou strukturu jako zásobník není implementace, ale [[Rozhraní (informatika)|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 (programovací jazyk)|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 (programování)|struktura]]:

<source lang="c">
typedef struct{
int top;
int items[STACKSIZE];
}STACK;
</source>

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é '''<code>ps->top</code>''' a za vložení nového prvku do pole '''<code>ps->items[]</code>'''. Funkce také ověřuje jestli pole není plné; pokud by se pole naplnilo a tato kontrola by zde nebyla, vedlo by to k chybě [[segmantation fault]].

<source lang="c">
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;
}
</source>

Funkce '''pop()''' odstraňuje prvek z vrcholu zásobníku a [[Unární operace#Unární operace v programování|dekrementuje]] hodnotu '''<code>ps->top</code>'''. 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.

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

==== Lineární seznam ====

Implementace pomocí '''lineárního seznamu''' je stejně jednoduchá a srozumitelná. Dalo by říct, že zásobníkový lineární seznam je o dost více 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:

<source lang="c">
typedef struct stack{
int data;
struct stack *nxt;
} STACK;
</source>

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:

<source lang="c">
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;
}
</source>

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:

<source lang="c">
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;
}
</source>

=== Stack 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 [[Forth]]u podobné jazyky (např. [[PostScript|Adobe PostScript]] jsou navrženy okolo zásobníku, který je viditelný a přístupný programátorovi.

[[C++]] a jeho [[:en:Standard Template Library]] poskytují "<code>stack</code>" šablonu tříd, které jsou omezeny jenom na '''push''' a '''pop''' operace. Java obsahuje třídu [http://java.sun.com/javase/6/docs/api/java/util/Stack.html stack], která je odvozena od třídy [http://java.sun.com/javase/6/docs/api/java/util/Vector.html 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 (datová struktura)|fronta]], která s ním může být zkombinovaná do [[deque|obousměrně ukončené fronty]]. Stručně řečeno, fronta je struktura typu [[FIFO]].

== 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 ===
[[Soubor:ProgramCallStack2.png|thumb|350px|right|Typická ukázka zásobníku rostoucího směrem dolu. 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, 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 vyjmuty 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íraly 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ř. [[x86|Intel x86]] a [[Z80|Zilog Z80]]) mají speciální instrukce, které implicitně používají registr který byl vyhrazený k použití pro ukazatel Ostatní (např. [[PDP-11|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é okno|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 [[Jednočipový počítač|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ý.
* [[Mikrokontrolér PIC|mikrokontroléry PIC]]
* počítač Cowboys MuP21
* řada Harris RTX
* Novix NC4016

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 [[Mainframe|mainfraimů]] a minipočítačů. Tyto stroje se nazývají [[zásobníkový počítač]].

== Související články ==
* [[Zásobníkový automat]]

== Externí odkazy ==

{{Článek z Wikipedie}}
[[Kategorie:Datové struktury]]

Zásobník (datová struktura) - Historie editací

Sysop: /* Stack a programovací jazyky */

Sysop: 1 revizi

Sysop: + Nový článek...jen díky přerušenému přesměrování