Ang stack ay walang anuman kundi ang linear na istraktura ng data kung saan ang pagpapasok at pagtanggal ay magaganap lamang sa isang dulo. Ang pagpapatakbo ng pagpasok ay nagkakaroon ng isang espesyal na pangalan na kilala bilang PUSH at ang pagpapatanggal ng operasyon ay nagkakaroon din ng isang espesyal na pangalan na kilala bilang POP. Ang PUSH at POP ay dalawang pangunahing pagpapatakbo na maaaring isagawa lamang sa isang partikular na stack. Ito ay isang pangkat ng mga lokasyon ng memorya at ang mga lokasyon ng memorya ay nauugnay sa basahin na memorya o sumulat ng memorya. Ginagamit ito para sa pagtatago ng binary na impormasyon sa panahon ng pagpapatupad ng programa, kapag nagpapatupad kami ng anumang programa kung gayon ang mga nilalaman ng programang iyon ay mag-iimbak sa stack. Sumusunod ito Huling pumasok Unang lumabas (LIFO) at ginagamit lamang ito para sa pagtatago at pagkuha ng data ngunit hindi ginagamit para sa pagtatago ng data. Ang maikling paliwanag ng stack / stack pointer ay tinalakay sa ibaba.
Ano ang Stack / Stack Pointer?
Kahulugan: Ang stack ay isang aparato ng imbakan, ginagamit para sa pagtatago ng impormasyon o data sa isang paraan ng LIFO (Huling Sa Unang Paglabas). Tuwing ipinasok namin ang data sa anyo ng paraan ng LIFO, ang elemento na dapat munang matanggal ay ang huling elemento ng inserter, kaya't ang huling naipasok na elemento ay unang inilalabas. Ito ang yunit ng memorya sa loob ng isang rehistro ng address na tinatawag na stack pointer (SP). Laging ipinapahiwatig ng stack pointer ang nangungunang elemento sa stack na nangangahulugang aling lokasyon ang data na dapat na ipasok.
Mga uri ng Stack
Mayroong dalawang uri ng mga stack na rehistro nila ang stack at ang memory stack.
Magrehistro Stack
Ang rehistro na stack ay isa ring aparato ng memorya na naroroon sa yunit ng memorya, ngunit pinangangasiwaan lamang nito ang isang maliit na halaga ng data. Ang lalim ng stack ay palaging limitado sa rehistro stack dahil ang laki ng rehistro stack s napakaliit kumpara sa memorya.
Push Operation sa Rehistro Stack
Hakbang1: Ang stack pointer ay nagdaragdag ng 1.
SP ← SP + 1
Hakbang2: Ipasok ang data sa stack.
1000 [SP] ← CT
Kung saan ang DR ay ang Rehistro ng Data
Hakbang3: Suriin kung ang stack ay puno o hindi
kung (sp = 0) pagkatapos (buong ← 1)
Hakbang4: Markahan hindi walang laman
walang laman ← 0
Pop Operation sa Rehistro Stack
Hakbang1: Basahin ang data mula sa stack.
DR ← M [SP]
Hakbang2: Punto ng pagbawas ng pagbawas.
SP ← SP-1
Hakbang3: Suriin kung ang stack ay walang laman o hindi
kung sp = 0 kung gayon walang laman ang ← 1
Ang samahang stack ng 64-bit register stack ay ipinapakita sa figure sa ibaba.
Magrehistro ng Organisasyon ng Stack
Memory Stack
Sa stack ng memorya, ang lalim ng stack ay nababaluktot. Sumasakop ito ng isang malaking halaga ng data ng memorya, samantalang sa rehistro na stack ay isang may hangganan na bilang ng mga salitang memorya ang maiimbak.
Push Operation sa Memory Stack
Hakbang1: SP ← SP-1
Hakbang2: 1000 [SP] ← CT
Pagpapatakbo ng pop sa Memory Stack
Hakbang1: DR ← M [SP]
Hakbang2: SP ← SP-1
Ihambing sa yunit ng rehistro, ang yunit ng memorya ay nag-iimbak ng isang malaking halaga ng data. Ang numero ng stack ng memorya ay ipinapakita sa figure sa ibaba.
Memory Stack
Ang kabuuang yunit ng memorya ay nahahati sa tatlong bahagi, ang unang yunit ng memorya ay mayroong programa (wala ngunit mga tagubilin), ang pangalawang bahagi ay data (operands) at ang ikatlong bahagi ay stack. Ang mga tagubilin sa programa ay laging nakaimbak sa counter ng programa (PC), ang mga pagrehistro ng data ay nakilala ng rehistro ng address (AR). Ang address na 3000 hanggang 4001 na ginamit para sa stack at ang unang item o elemento ay nakaimbak sa 4001.
Stack / Stack Pointer noong 8085 Microprocessor
Ang pagtingin sa programmer ng 8085 microprocessor naglalaman ng mga rehistro para sa pangkalahatang layunin at mga rehistro para sa espesyal na layunin . Ang mga rehistro sa pangkalahatang layunin ay A, B, C, D, E, H, L, at ang mga espesyal na layunin na rehistro ay SP (Stack Pointer) at PC (Program Counter). Ang view ng programmer ng 8085 microprocessor ay ipinapakita sa figure sa ibaba.
Programmer View ng 8085
Ang stack pointer ay isang 16-bit na rehistro na naglalaman ng memory address, ipagpalagay na ang mga nilalaman ng stack pointer (SP) ay FC78H, pagkatapos ay binibigyang kahulugan ito ng microprocessor 8085. Ang mga lokasyon ng memorya ay may kapaki-pakinabang na impormasyon mula sa FC78H hanggang FFFH at mula sa FC77H hanggang 0000H ang lokasyon ng memorya ay walang kapaki-pakinabang na impormasyon. Ang interpretasyon ng stack pointer ay ipinapakita sa figure sa ibaba.
Pagbibigay kahulugan ng Stack Pointer
Pangunahing Pagpapatakbo ng Stack / Stack Pointer
Mayroong dalawang pagpapatakbo ng stack ang mga ito ay: operasyon ng PUSH at operasyon ng POP.
Operasyon ng PUSH
Ang PUSH ay nangangahulugang pagtulak o pagpasok ng isang elemento sa stack. Palaging nadaragdagan ng operasyon ng PUSH ang stack pointer at palaging binabawasan ng operasyon ng POP ang stack pointer. Sa kaso ng isang operasyon ng push, kailangan naming suriin kung mayroong isang libreng puwang na magagamit o hindi. Kung magagamit ang libreng puwang, maaari kaming pumunta sa operasyon ng push, kung ang libreng puwang ay hindi magagamit kung gayon nangyayari ang mensahe ng error na umapaw. Ang overflow ay dapat suriin sa kaso ng operasyon ng push ayon sa pagkakabanggit. Ang pangunahing operasyon ng push and pop ay ipinapakita sa figure sa ibaba.
Pangunahing Pagpapatakbo ng PUSH at POP
Ang figure (a) ay ang stack. Kung nais mong itulak ang elemento na isang pagpasok ng elemento sa stack, kailangan mong itulak (s, a), kung saan ang ‘s’ ay walang iba kundi isang stack. Sa stack, inilalagay namin ang elemento na 'a' at ang operasyong ito ay ipinapakita sa pigura (b). Tingnan ang pigura (3), ipagpalagay na ang stack ay naglalaman ng tatlong mga elemento a, b, c, at ang stack ay puno ng isang elemento.
Kung nais mong magsingit ng pang-apat na elemento-‘d ’gamit ang push (s, d), ngunit walang magagamit na puwang upang ipasok ang elemento pagkatapos ay ipinapahiwatig nito na ang stack ay overflow. Ginagamit ang overflow terminology kapag ang stack ay puno at ang algorithm ng push operation ay ipinapakita sa ibaba.
itulak (stack [], itaas, max stack, item)
kung (itaas == maxstack-1)
{
i-print ang 'overflow'
}
iba pa
{
itaas = tuktok + 1
stack [top] = item
}
magtapos
Pagpapatakbo ng POP
Ang ibig sabihin ng POP ay tinatanggal ang elemento sa tuktok ng stack. Sa kaso ng pagpapatakbo ng pop, kailangan nating suriin kung ang stack ay una nang walang laman o hindi. Kung ang stack ay una nang walang laman pagkatapos ay nangyayari ang isang underflow na sitwasyon. Ipagpalagay na ang stack ay walang laman pa rin nais mong i-pop ang mga elemento sa stack ngunit walang mga elemento sa stack pagkatapos ay humantong ito sa stack underflow.
Ang underflow ay dapat suriin sa kaso ng pagpapatakbo ng pop ayon sa pagkakabanggit. Sa pagpapatakbo ng pop anuman ang nangungunang elemento na naroroon sa stack na dapat na mag-pop o matanggal, kaya hindi na kailangang banggitin kung aling elemento ang mai-pop, bilang default ang pinakamataas na elemento ay mai-pop. Ang algorithm ng pagpapatakbo ng pop ay ipinapakita sa ibaba.
pop (stack [], itaas, item)
kung (itaas == - 1)
{
i-print ang 'underflow'
}
iba pa
{
item = stack [itaas]
tuktok = tuktok-1
}
Halimbawa
Ang mga elemento ay ipinasok sa pagkakasunud-sunod bilang A, B, C, D, E, ito ay kumakatawan sa stack ng limang elemento. Sa figure (a), nais naming itulak ang sangkap na 'A' sa stack pagkatapos ang tuktok ay nagiging zero (itaas = 0), katulad ng tuktok = 1 kapag ang elemento na 'B' ay tinulak, itaas = 2 kapag ang elemento na 'C' ay itinulak, tuktok = 3 kapag ang elementong 'D' ay naitulak, at itaas = 4 kapag ang elementong 'E' ay naitulak.
Kaya't anuman ang mga elemento na kinuha ko ay inilalagay sa stack, ngayon ang stack ay puno na. Kung nais mong itulak ang isa pang elemento walang lugar sa stack, kaya't ipinapahiwatig nito ang overflow. Ngayon ang stack ay puno na kung nais mong i-pop ang elementong 'E' na elemento ay dapat munang tanggalin. Ang operasyon ng push ay ipinapakita sa figure sa ibaba.
Push Operation
Kailangan naming gamitin ang pagpapatakbo ng pop upang tanggalin ang mga elemento sa stack. Kaya banggitin lamang ang pop () huwag magsulat ng mga argumento sa pop sapagkat bilang default tinatanggal nito ang nangungunang elemento. Ang unang sangkap na 'E' ay tinanggal sa susunod na elemento ng 'D' ... .. 'A'. Kapag ang mga nangungunang elemento ay tinatanggal pagkatapos bumababa ang nangungunang halaga. Kapag tuktok = -1 ang stack ay nagpapahiwatig ng underflow. Ang operasyon ng pop ay ipinapakita sa figure sa ibaba.
Pagpapatakbo ng POP
Kaya't ito ang paliwanag kung paano ipinasok at tinanggal ang mga elemento sa stack sa pamamagitan ng paggamit ng push at pop operation.
Mga Aplikasyon
Ang mga aplikasyon ng stack / stack pointer ay
- Pagbaligtad ng string
- Balanseng panaklong
- UNDO / FINGER
- Ang stack ng system para sa mga tala ng pagsasaaktibo
- Infix, prefiks, postfix, expression
Mga FAQ
1). Ano ang stack pointer sa braso?
Ang rehistro ng stack pointer (R13) na ginamit bilang isang pointer sa aktibong stack sa ARM.
2). Bakit ang stack pointer ay 16 bit?
Ang stack pointer (SP) at ang program counter (PC) na ginamit upang maiimbak ang nakaraang lokasyon at ang address ng lokasyon ng memorya ay 16 bits, kaya ang stack pointer (SP) ay nasa 16 bit din.
3). Ano ang papel na ginagampanan ng stack pointer?
Ang papel na ginagampanan ng stack pointer (SP) ay upang ipahiwatig ang tuktok ng elemento sa stack.
4). Aling mga stack ang ginamit noong 8085?
Ang stack na ginamit noong 8085 ay Last In First Out (LIFO).
5). Ang stack pointer ba ay isang rehistro?
Oo, ang stack pointer (SP) ay isang rehistro ng address na palaging ipinapahiwatig ang tuktok ng elemento sa stack.
