Stack ( angol. verem - verem; verem olvasva ) - egy absztrakt adattípus , amely a LIFO elv szerint szervezett elemek listája ( angol. last in - first out , "last in - first out").
Leggyakrabban a köteg elvét egy tányérköteghez hasonlítják: ahhoz, hogy felülről vegye a másodikat, el kell távolítania a felsőt.
Egy digitális számítástechnikai komplexumban a köteget tárnak nevezik – a lőfegyverben lévő tárral analóg módon (a lövés az utoljára betöltött patronnal kezdődik).
1946-ban Alan Turing bevezette a verem fogalmát [1] [2] . 1957-ben pedig a németek Klaus Samelson és Friedrich L. Bauer szabadalmaztatták Turing ötletét [3] .
Egyes nyelveken (például Lisp , Python [4] ) bármely lista veremnek nevezhető , mivel pop és push műveletek állnak rendelkezésre számukra. A C++ nyelvben a szabványos könyvtárnak van egy osztálya implementált szerkezettel és metódusokkal [5] . Stb.
A verem gyakran egyedileg összekapcsolt listaként valósul meg (a lista minden eleme a veremben tárolt információkon kívül a verem következő elemére mutató mutatót is tartalmaz).
De az is gyakori, hogy a verem egydimenziós tömbben van rendezett címekkel. Egy ilyen veremszervezés kényelmes, ha az információs elem meghatározott számú szót foglal el a memóriában, például 1 szót. Így nincs szükség explicit mutató tárolására a veremelem következő veremelemére, ami memóriát takarít meg. Ebben az esetben a veremmutató ( Stack Pointer , - SP ) általában egy processzorregiszter , és a veremfej címére mutat.
Tegyük fel például, hogy a verem feje alacsonyabb címen található, a következő elemek pedig növekvő címeken találhatók. Minden alkalommal, amikor egy szót a verembe tolnak, az SP először 1-gyel nő, majd az SP-ben lévő cím a memóriába kerül. Minden alkalommal, amikor egy szó kikerül a veremből (popping), először az aktuális címet olvassa be az SP-ből, majd 1-gyel csökkenti az SP tartalmát.
Ha egy verem egyedileg irányított listaként van megszervezve, a veremváltozó értéke egy mutató a tetejére – a tetejének címére. Ha a verem üres, akkor a mutató értéke NULL.
Példa verem megvalósítására C nyelven:
struct verem { érvénytelen * adat ; struct verem * next ; };Három művelet lehetséges a veremen: elem hozzáadása (egyébként push, push ), elem eltávolítása ( pop ) és a fejelem beolvasása ( peek ) [6] .
A Push hozzáad egy új elemet, amely arra az elemre mutat, amely korábban a fej volt. Az új elem mostantól a fejelem lesz.
Amikor egy elemet eltávolítanak ( pop ), az első eltávolításra kerül, és az, amelyre az objektum mutatott (a következő elem), a fejléc lesz. Az eltávolított elem értéke kerül visszaadásra.
#include <iostream> #include <cassert> #include <verem> // szabványos C++ veremmegvalósítás int main () { std :: verem < int > stk ; // int elemek halma std :: cout << "Adjon meg egész számokat (-1 a végéhez):" << std :: endl ; míg ( igaz ) { int num ; std :: cin >> num ; ha ( szám == -1 ) szünet ; stk . nyomni ( szám ); // elem hozzáadása a veremhez } std :: cout << "A veremben" << stk . méret () << "elemek" << std :: endl ; // stk.size() módosul hozzáadásakor/eltávolításakor, ezért // ciklus for (int i = 0; i < stk.size(); i++) { ... } // helytelenül fog viselkedni a ( int i = stk esetén .size ( ) ; i > 0 ; i -- ) { // felső elem megtekintése std :: cout << "Felső elem: " << stk . top () << std :: endl ; // távolítsa el a felső elemet stk . pop (); } állít ( stk.empty ( ) ); // a verem üres return 0 ; }A verem programozott nézete adatstruktúrák , például fa vagy grafikon bejárására szolgál . Rekurzív függvények használatakor a verem is használatban lesz, de annak hardveres formája. E célokon kívül a verem egy veremgép rendszerezésére szolgál, amely fordított lengyel jelöléssel hajtja végre a számításokat . A veremgép használatára példa a Unix dc program .
A hívási verem az alprogramok visszatérési pontjainak nyomon követésére szolgál .
Az aritmetikai társprocesszorok , programozható számológépek és a Forth nyelv veremszámítási modellt használ [7] .
A verem ötletét a veremgépben használják a veremprogramozási nyelvek között .
A hardververem másik neve a gépverem. A vele való munkavégzést a központi processzor hardvere támogatja. A gépi verem a futó program igényeire szolgál: változók tárolására és szubrutinok hívására . Amikor egy szubrutint (eljárást) hívunk, a processzor a verembe tolja az utasítás címét a szubrutin „visszaadási címének” az alprogramból való meghívására vonatkozó utasítását követően. A szubrutinból való visszatérés parancsára az alprogramot hívó program visszatérési címe kikerül a veremből, és erre a címre ugrás történik.
Hasonló folyamatok történnek hardveres megszakításkor (az X86 processzor hardveres megszakításkor automatikusan elmenti a jelzőregisztert a veremben). Ezenkívül a fordítók az eljárások helyi változóit foglalják le a veremben (ha a processzor hozzáférést biztosít a verem tetszőleges helyéhez).
Az X86 architektúrában a hardververem egy összefüggő memóriaterület, amelyet speciális ESP (Stack Pointer) és SS (Stack Segment Selector) [8] regiszterek címeznek .
A verem használata előtt inicializálni kell, hogy az SS:ESP regiszterek a veremfej címére mutassanak a fizikai RAM területén, és a szükséges számú memóriacellát le kell foglalni az adatok tárolására verem (nyilvánvaló, hogy a ROM -ban lévő verem természetesen nem rendezhető). Az alkalmazási programok általában használatra kész köteget kapnak az operációs rendszertől. A processzor védett üzemmódjában a feladatállapot szegmens négy veremszegmens választót tartalmaz (különböző jogosultsági szintekhez), de egyszerre csak egy verem használatos [9] .
| Adatstruktúrák | |
|---|---|
| Listák | |
| fák | |
| Számít | |
| Egyéb | |
| Az operációs rendszerek szempontjai | |||||
|---|---|---|---|---|---|
| |||||
| Típusok |
| ||||
| Sejtmag |
| ||||
| Folyamatmenedzsment _ |
| ||||
| Memóriakezelés és címzés | |||||
| Betöltési és inicializálási eszközök | |||||
| Héj | |||||
| Egyéb | |||||
| Kategória Wikimedia Commons Wikikönyvek Wikiszótár | |||||