Mis on korstna / virna osuti: tüübid ja selle rakendused

Proovige Meie Instrumenti Probleemide Kõrvaldamiseks





Virn pole midagi muud kui lineaarne andmestruktuur, kus sisestamine ja kustutamine toimub ainult ühes otsas. Sisestusoperatsioonil on spetsiaalne nimi PUSH ja kustutamisoperatsioonil on ka POP-nimeline nimi. PUSH ja POP on kaks põhilist toimingut, mida saab teha ainult kindlas virnas. See on rühm mälu asukohti ja mälu asukohad on seotud kas lugemismälu või kirjutusmäluga. Seda kasutatakse binaarteabe salvestamiseks programmi käivitamise ajal, kui me käivitame mis tahes programmi, siis selle programmi sisu salvestatakse virnasse. See järgneb Viimane sisse esimene välja (LIFO) ja seda kasutatakse ainult andmete salvestamiseks ja hankimiseks, kuid ei kasutata andmete salvestamiseks. Virna / virna osuti lühikest selgitust käsitletakse allpool.

Mis on korstna / virna osuti?

Definitsioon: Virn on salvestusseade, mida kasutatakse teabe või andmete salvestamiseks LIFO (Last In First Out) viisil. Alati, kui sisestame andmed LIFO-vormis, on kõigepealt kustutatav element viimane sisestuselement, nii et viimane sisestatud element võetakse kõigepealt välja. See on aadressiregistri mäluüksus, mida nimetatakse virnaviituriks (SP). Virnaosuti osutab alati virna ülemisele elemendile, mis tähendab, millisesse kohta tuleb andmed sisestada.




Virna tüübid

Virnaid on kahte tüüpi: need on registrivirn ja mälupakk.

Registreerige virn

Registrivirn on ka mäluseadmes olev mäluseade, kuid see käsitseb ainult väikest andmemahtu. Virna sügavus on registrivirnas alati piiratud, kuna registrivirna suurus on mäluga võrreldes väga väike.



Push Operation register Stackis

Samm 1: Virnaosuti suureneb 1 võrra.

SP ← SP + 1


2. samm: Sisestage andmed virna.

1000 [SP] ← CT

Kus DR on andmeregister

3. samm: Kontrollige, kas virn on täis või mitte

kui (sp = 0) siis (täis ← 1)

4. samm: Märkige, et pole tühi

tühi ← 0

Popoperatsioon registrivirnas

Samm 1: Andmete lugemine virnast.

DR ← M [SP]

2. samm: Vähenev virna punkt.

SP ← SP-1

3. samm: Kontrollige, kas virn on tühi või mitte

kui sp = 0, siis tühi ← 1

64-bitise registrivirna korstna korraldus on näidatud alloleval joonisel.

Registreerige korstnate organisatsioon

Registreerige korstnate organisatsioon

Mälupakk

Mälupakis on virna sügavus paindlik. See võtab palju mäluandmeid, samas kui registrivirnasse salvestatakse ainult piiratud arv mälusõnu.

Push Operation mälupakis

Samm 1: SP ← SP-1

2. samm: 1000 [SP] ← CT

Popoperatsioon mälupakis

Samm 1: DR ← M [SP]

2. samm: SP ← SP-1

Võrreldes registriüksusega salvestab mäluüksus suure hulga andmeid. Mälupinu joonis on näidatud alloleval joonisel.

Mälupakk

Mälupakk

Kogu mäluüksus on jagatud kolmeks osaks, esimesel mäluseadmel on programm (mitte midagi peale juhiste), teine ​​osa on andmed (operandid) ja kolmas osa virn. Programmi juhised salvestatakse alati programmiloendurisse (PC), andmeregistrid identifitseeritakse aadressiregistris (AR). Virna jaoks kasutatavad aadressid 3000 kuni 4001 ja esimene element või element salvestatakse aadressil 4001.

Virnade / korstnate osuti 8085 mikroprotsessoris

Programmeerija vaade 8085-le mikroprotsessor sisaldab üldotstarbelisi registreid ja eriotstarbelised registrid . Üldotstarbelised registrid on A, B, C, D, E, H, L ja eriotstarbelised registrid on SP (Stack Pointer) ja PC (Program Counter). 8085 mikroprotsessori programmeerija vaade on näidatud alloleval joonisel.

Programmeerija vaade 8085-le

Programmeerija vaade 8085-le

Virnaosuti on 16-bitine register, mis sisaldab mäluaadressi, oletame, et virnamuteri (SP) sisu on FC78H, seejärel tõlgendab seda mikroprotsessor 8085. Mälu asukohtades on kasulikku teavet FC78H-st FFFH-ni ja FC77H-st kuni 0000H-ni mälu asukohas pole kasulikku teavet. Virnaosuti tõlgendus on näidatud alloleval joonisel.

Stack Pointer

Stack Pointer'i tõlgendamine

Virnade / virnade osutamise põhitoimingud

Virnast on kaks toimingut: PUSH-operatsioon ja POP-operatsioon.

PUSH-operatsioon

PUSH tähendab elemendi virna surumist või sisestamist. PUSH-operatsioon suurendab alati virnaosutit ja POP-toiming alati virnaosutit. Lükkamistoimingu korral peame kontrollima, kas vaba ruumi on olemas või mitte. Kui vaba ruumi on saadaval, võime minna tõukefunktsioonile. Kui vaba ruumi pole, siis ilmneb ülevoolu tõrketeade. Ülevoolu tuleb kontrollida vastavalt tõukejõu korral. Push ja popi põhitoimingud on näidatud alloleval joonisel.

PUSH ja POP põhitoimingud

PUSH ja POP põhitoimingud

Joonis (a) on virn. Kui soovite elementi, mis sisestab elemendi, virna suruda, peate suruma (s, a), kus ‘s’ pole midagi muud kui virna. Virnas asetame elemendi ‘a’ ja see toiming on näidatud joonisel (b). Vaadake joonist (3). Oletame, et virn sisaldab kolme elementi a, b, c ja virn on täidetud elemendiga.

Kui soovite sisestada neljanda elemendi ‘d’, kasutades push (s, d), kuid elemendi sisestamiseks pole ruumi, näitab see, et virna on ülevoolav. Ülevooluterminoloogiat kasutatakse siis, kui virn on täis ja allpool on näidatud tõukamise algoritm.

tõuge (virn [], ülemine, maksimaalne virn, üksus)

kui (ülemine == maxstack-1)

{

print 'ülevool'

}

muud

{

top = top + 1

virn [ülemine] = üksus

}

lõpp

POP-i töö

POP tähendab virna ülaosas oleva elemendi kustutamist. Pop-operatsiooni korral peame kontrollima, kas virn on algselt tühi või mitte. Kui virn on algselt tühi, tekib alavoolu olukord. Oletame, et virn on tühi, kuid soovite virna elemente poputada, kuid virnas pole ühtegi elementi, see viib virna allavoolu.

Alajooksu tuleb kontrollida vastavalt pop-toimimise korral. Pop-operatsioonis on ükskõik milline virna pealmine element, mis tuleks hüpata või kustutada, nii et pole vaja mainida, milline element hüpatakse, vaikimisi hüpatakse kõige ülemine element. Pop-operatsiooni algoritm on toodud allpool.

pop (virn [], ülaosa, üksus)

kui (ülemine == - 1)

{

printida “allavool”

}

muud

{

item = virn [üles]

top = top-1

}

Näide

Elemendid sisestatakse järjestuses A, B, C, D, E, see tähistab viie elemendi virna. Joonisel (a) tahame virnale lükata 'A' elemendi, siis ülemine osa saab nulli (ülemine = 0), samamoodi ülemine = 1, kui elementi 'B' surutakse, ülemine = 2, kui element 'C' lükatakse, top = 3, kui elementi 'D' surutakse, ja ülemine = 4, kui elementi 'E' surutakse.

Nii et ükskõik millised elemendid, mille olen võtnud, pannakse virna, nüüd on virn täis. Kui soovite mõnda muud elementi lükata, pole virnas kohta, nii et see näitab ülevoolu. Nüüd on virn täis, kui soovite hüpata, tuleb kõigepealt element E kustutada. Lükkamistoiming on näidatud alloleval joonisel.

Lükake töö

Lükake töö

Virnast elementide kustutamiseks peame kasutama pop-toimingut. Nii et mainige lihtsalt pop (), ärge kirjutage argumente popi, sest see kustutab vaikimisi ülemise elemendi. Esimene „E” element kustutatakse järgmise „D” elemendi… A ’järgi. Kui ülemised elemendid kustutatakse, siis ülemine väärtus väheneb. Kui top = -1, näitab virn alavoolu. Pop-operatsioon on näidatud alloleval joonisel.

POP-i töö

POP-i töö

Nii et see on selgitus, kuidas elemendid virnasse sisestatakse ja kustutatakse, kasutades push ja pop operatsiooni.

Rakendused

Virna / virna osuti rakendused on

  • Stringi ümberpööramine
  • Tasakaalustatud sulgud
  • TEHA / SÕRM
  • Süsteemivirn aktiveerimiskirjete jaoks
  • Infix, prefiks, postfix, avaldis

KKK

1). Mis on virnaosuti käes?

Virnaosuti register (R13), mida kasutatakse ARM-is aktiivse virna osutajana.

2). Miks korstakursor on 16-bitine?

Virnaosuti (SP) ja programmiloendur (PC), mida kasutatakse eelmise asukoha ja mälu asukoha aadressi salvestamiseks, on 16 bitti, seega on ka virnaosuti (SP) 16-bitine.

3). Mis on virnaosuti roll?

Virnaosuti (SP) roll on näidata virna elemendi ülaosa.

4). Millist virna kasutatakse aastal 8085?

Aastal 8085 kasutatud virn on Last In First Out (LIFO).

5). Kas virnaosuti on register?

Jah, virnaosuti (SP) on aadressiregister, mis näitab alati korstna elemendi ülaosa.

Selles artiklis, mis on