Stekas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Stekas – duomenų struktūra, veikianti LIFO (angl. „last in first out“) principu. Kitaip tariant, iš steko visada paimamas paskutinis į jį padėtas elementas, po to – priešpaskutinis ir t.t. Tai primena plytas, kraunamas vienas ant kitų stulpu.
Stekas palaiko dvi pagrindines operacijas – push (padėti) ir pop (pasiimti).
Turinys |
[taisyti] Aparatinė realizacija
Daugelis procesorių (ypač – CISC architektūros) palaiko steko darbą aparatiškai. Tokiuose procesoriuose būna vienas ar keli už steką atsakingi registrai (Intel 8080 – SP, Intel x86 – SP ir ESP), rodantys į steko galą. Procesoriaus vykdoma Pop operacija automatiškai perkelia į nurodytą registrą paskutinį steko elementą ir sumažina steko registro reikšmę. Push operacija steko registro reikšmę padidina, bei nurodyto registro reikšmę perkelia į steką. Asembleriu tokia operacijų seka gali būti aprašyta maždaug taip:
PUSH AX ; ; Atitiktų žemiau komentaruose esančią seką:
; ADD SP, 2 ; (Keičiama steko rodyklė, AX dydis baitais)
; MOV WORD PTR [SP], AX ; Registro reikšmė perkeliama į steką
POP AX ; ; Atitiktų žemiau komentaruose esančią seką:
; MOV AX, WORD PTR [SP] ; Steko viršūnė perkeliama į registrą
; SUB SP, 2 ; (Keičiama steko rodyklė, AX dydis baitais)
Sukompiliuotame Intel x86 procesoriui skirtos programos kode yra steko segmentas, kuriame ir saugomi į steką dedami elementai.
Jei kodas generuojamas kompiliatoriaus, kviečiamų funkcijų argumentai programiniame kode dažniausiai perduodami per steką (asembleriu programuojantis žmogus parametrus dažniausiai perduoda registruose).
Lokalūs kintamieji taip pat dažnai saugomi steke.
Pirmieji masiškai gaminti mikroprocesoriai turėjo vidinę stekinę atmintį. Pavyzdžiui, Intel 4004 turėjo trijų lygių paprogramių steką grįžimo adresui atsiminti, kuris Intel 4040 buvo padidintas iki ašuonių lygių. Vidinis stekas patogus itin paprastuose kompiuteriuose, kur išorinės operatyvinės atminties gali ir nebūti. Intel 8080 vis dar turėjo retai naudotą galimybė prijungti net iki 64 Kb talpos atskirai adresuojamą steko atmintį. Daugumoje šiuolaikinių kompiuterių stekas yra pagrindinės atminties dalis.
[taisyti] Programinė realizacija
Stekas gali būti realizuojamas tiesinio sąrašo pagrindu arba panaudojant masyvus. Masyvo pagalba realizuotas stekas dirba greičiau ir nereikalauja papildomos atminties sąrašo struktūroms saugoti. Jis imituoja aparatinę realizaciją, turėdamas steko rodyklę atitinkantį sveikojo tipo kintamąjį, rodantį į pirmą laisvą elementą virš steko viršūnes. Reikšmės padėjimo operacija užrašoma kaip
stekas[sp] = reikšmė sp = sp + 1
Reikšmės paėmimo operacija užrašoma kaip
sp = sp - 1 reikšmė = stekas[sp]
čia stekas – steko turinį saugantis masyvas, sp – steko rodyklės kintamais (pradinė reikšmė lygi nuliui).
Toks stekas paprastai turi ribotą iš anksto žinomą talpą (masyvo ilgį), nebent jį viršijus visas turinys būtų automatiškai kopijuojamas į kitą (didesnį) masyvą.
Nuorodas naudojančio tiesinio sąrašo pagrindu galima sukurti tik kompiuterio atminties ribojamą dinamiškai augantį steką, tačiau duomenų saugojimas jame mažiau efektyvus.
[taisyti] Steko naudojimo sritys
[taisyti] Stekas ir paprogramės
Kviečiant įvairių programos vietų bendrai naudojamą paskirties kodo fragmentą (pavyzdžiui, simbolio išvedimo į ekraną paprogramę), taip pat aptarnaujant pertraukimus, svarbu neužmiršti šiuo metu vykdomos komandų sekos adreso, kad užbaigus paprogramę būtų galima grįžti atgal. Grįžimo adresas beveik visada išsaugomas steke. Dažnai pasitaiko, jog vykdoma paprogramė savo ruožtu kviečia kitas paprogrames. Tuomet įsiminimo operacija kartojama. Baigiant paprogramę, steko viršūnėje visada bus reikalingas grįžimo adresas, nes jis buvo ten padėtas paskutinis.
[taisyti] Stekas ir būsenos išsaugojimas
Steke gali būti išsaugomas ne tik ankstesnis vykdymo adresas, bet ir įvairi kita su ankstensniu vykdymu susijusi informacija (registrų bei vėliavėlių reikšmės, kai kada ir informacija apie įvedimo ar išvedimo įrenginių būseną). Kviečiant vieną paprogramę iš kitos, būsena gali būti išsaugota daugelį kartų. Stekas tinka, nes paskutinė išsaugota būsena turi būti atstatyta pirmoji.
[taisyti] Stekas ir lokalūs kintamieji
Jei paprogramei reikia atminties lokaliems kintamiesiems saugoti, ją taip pat patogu išskirti steka, pradedant nuo dabartinės steko rodyklės reikšmės (rodyklė pastumiama tiek, jog rodytų į laisvą sritį greta užimtos atminties ribos). Stekas tam patogus todėl, jog paskutinė pradėta vykdyti paprogramė pirmoji ir pabaigiama (taigi paskutinė išskirta lokialių kintamųjų sritis pirmoji ir atlaisvinama). Steke išskirtai atminties sričiai naudoti daugelis procesorių turi komandas ne tik steko viršūnei, bet ir žinomu atstumu žemiau jos esantiems duomenims pasiekti.
