Zásobník ( angl. stack - stack; stack is read ) - abstraktní datový typ , což je seznam prvků organizovaných podle principu LIFO ( angl. last in - first out , "last in - first out").
Nejčastěji se princip stohu porovnává se stohem talířů: abyste mohli vzít druhý shora, musíte odstranit ten horní.
V digitálním výpočetním komplexu se zásobník nazývá zásobník - analogicky se zásobníkem ve střelné zbrani (střelba začne s posledním nabitým nábojem).
V roce 1946 Alan Turing představil koncept zásobníku [1] [2] . A v roce 1957 si Turingův nápad patentovali Němci Klaus Samelson a Friedrich L. Bauer [3] .
V některých jazycích (například Lisp , Python [4] ) lze jakýkoli seznam nazvat zásobníkem , protože jsou pro něj dostupné operace pop a push. V jazyce C++ má standardní knihovna třídu s implementovanou strukturou a metodami [5] . Atd.
Zásobník je často implementován jako jednoduše propojený seznam (každý prvek v seznamu obsahuje kromě informací uložených v zásobníku i ukazatel na další prvek zásobníku).
Ale je také běžné, že zásobník je v jednorozměrném poli s uspořádanými adresami. Taková organizace zásobníku je vhodná, pokud informační prvek zabírá v paměti pevný počet slov, například 1 slovo. To eliminuje potřebu ukládat explicitní ukazatel na další prvek zásobníku v prvku zásobníku, což šetří paměť. V tomto případě je ukazatel zásobníku ( Stack Pointer , - SP ) obvykle registr procesoru a ukazuje na adresu hlavy zásobníku.
Předpokládejme například, že hlava zásobníku je umístěna na nižší adrese, následující prvky jsou umístěny na rostoucích adresách. Pokaždé, když je slovo vloženo do zásobníku, SP se nejprve zvýší o 1 a pak se adresa v SP zapíše do paměti. Pokaždé, když slovo vyskočí ze zásobníku (popping), nejprve přečte aktuální adresu z SP a poté sníží obsah SP o 1.
Když je zásobník organizován jako jednotlivě řízený seznam, hodnota proměnné zásobníku je ukazatel na jeho vrchol - adresa vrcholu. Pokud je zásobník prázdný, je hodnota ukazatele NULL.
Příklad implementace zásobníku v jazyce C:
zásobník struktur { neplatná * data ; struct stack * další ; };Na zásobníku jsou možné tři operace: přidání prvku (jinak zatlačení, zatlačení ), odebrání prvku ( pop ) a načtení prvku hlavičky ( peek ) [6] .
Push přidá nový prvek ukazující na prvek, který byl dříve hlavou. Nový prvek se nyní stává prvkem hlavy.
Když je odstraněn prvek ( pop ), je odstraněn první a ten, na který měl tento objekt ukazatel (další prvek), se stává hlavním. Vrátí se hodnota odstraněného prvku.
#include <iostream> #include <cassert> #include <stack> // standardní implementace zásobníku C++ int main () { std :: stack < int > stk ; // zásobník prvků int std :: cout << "Zadejte celá čísla (-1 do konce):" << std :: endl ; zatímco ( pravda ) { int num ; std :: cin >> num ; if ( num == -1 ) zlomit ; stk . tlačit ( num ); // přidat prvek do zásobníku } std :: cout << "Na zásobníku" << stk . velikost () << "prvky" << std :: endl ; // stk.size() se při přidávání/odebírání mění, takže // smyčka for (int i = 0; i < stk.size(); i++) { ... } // se bude chovat nesprávně pro ( int i = stk .velikost ( ) ; i > 0 ; i -- ) { // pohled na horní prvek std :: cout << "Top prvek: " << stk . nahoru () << std :: endl ; // odstranění horního prvku stk . pop (); } tvrdit ( stk.empty ( ) ); // zásobník je prázdný návrat 0 ; }Programové zobrazení zásobníku se používá k procházení datových struktur , jako je strom nebo graf . Při použití rekurzivních funkcí se použije také zásobník, ale jeho hardwarová podoba. Kromě těchto účelů se zásobník používá k organizaci zásobníku, který implementuje výpočty v reverzní polské notaci . Příkladem použití stohovacího stroje je unixový dc program .
Zásobník volání se používá ke sledování návratových bodů z podprogramů .
Aritmetické koprocesory , programovatelné kalkulačky a jazyk Forth používají zásobníkový výpočetní model [7] .
Myšlenka stacku se používá v stack machine mezi stack programovacími jazyky .
Jiný název pro hardwarový zásobník je strojový zásobník. Práce s ním je podporována hardwarem centrálního procesoru. Zásobník stroje se používá pro potřeby běžícího programu: ukládání proměnných a volání podprogramů . Když je volán podprogram (procedura) , procesor vloží do zásobníku adresu instrukce následující po instrukci, aby zavolal podprogram "zpáteční adresu" z podprogramu. Při příkazu k návratu z podprogramu se návratová adresa programu, který podprogram vyvolal, odstraní ze zásobníku a provede se skok na tuto adresu.
K podobným procesům dochází během hardwarového přerušení (procesor X86 automaticky uloží registr příznaků do zásobníku během hardwarového přerušení). Kromě toho kompilátory alokují lokální proměnné procedur na zásobníku (pokud procesor poskytuje přístup k libovolnému umístění na zásobníku).
V architektuře X86 je hardwarový zásobník souvislou oblastí paměti adresovanou speciálními registry ESP (Stack Pointer) a SS (Stack Segment Selector) [8] .
Před použitím zásobníku je nutné jej inicializovat tak, aby registry SS:ESP ukazovaly na adresu hlavy zásobníku v oblasti fyzické RAM a pro ukládání dat na něm musí být rezervován potřebný počet paměťových buněk. zásobník (je zřejmé, že zásobník v ROM samozřejmě nelze organizovat). Aplikační programy zpravidla dostávají od operačního systému zásobník připravený k použití. V chráněném režimu procesoru segment stavu úlohy obsahuje čtyři selektory segmentů zásobníku (pro různé úrovně oprávnění), ale vždy se používá pouze jeden zásobník [9] .
| Datové struktury | |
|---|---|
| Seznamy | |
| Stromy | |
| Počítání | |
| jiný | |
| Aspekty operačních systémů | |||||
|---|---|---|---|---|---|
| |||||
| Typy |
| ||||
| Jádro |
| ||||
| Řízení procesů |
| ||||
| Správa a adresování paměti |
| ||||
| Nástroje pro načítání a inicializaci | |||||
| skořápka | |||||
| jiný | |||||
| Kategorie Wikimedia Commons Wikibooks Wikibooks | |||||