De stapel is niets anders dan de lineaire datastructuur waarbij het invoegen en verwijderen slechts aan één uiteinde plaatsvindt. De invoegbewerking heeft een speciale naam die bekend staat als PUSH en de verwijderbewerking heeft ook een speciale naam die bekend staat als POP. De PUSH en POP zijn twee fundamentele bewerkingen die alleen in een bepaalde stapel kunnen worden uitgevoerd. Het is een groep geheugenlocaties en de geheugenlocaties hebben betrekking op leesgeheugen of schrijfgeheugen. Dit wordt gebruikt voor het opslaan van binaire informatie tijdens de uitvoering van het programma, wanneer we een programma uitvoeren, wordt de inhoud van dat programma opgeslagen in de stapel. Het volgt Laatste erin, eerste eruit (LIFO) en wordt alleen gebruikt voor het opslaan en ophalen van de gegevens, maar niet voor het opslaan van de gegevens. De korte uitleg van de stapel / stapel pointer wordt hieronder besproken.
Wat is Stack / Stack Pointer?
Definitie: De stapel is een opslagapparaat, dat wordt gebruikt voor het opslaan van informatie of gegevens op een manier van LIFO (Last In First Out). Telkens wanneer we de gegevens invoeren in de vorm van een LIFO-manier, is het element dat als eerste moet worden verwijderd het laatste inserter-element, dus het laatst ingevoegde element wordt als eerste verwijderd. Het is de geheugeneenheid binnen een adresregister genaamd stack pointer (SP). De stapelaanwijzer geeft altijd het bovenste element in de stapel aan dat betekent op welke locatie de gegevens moeten worden ingevoegd.
Soorten stapel
Er zijn twee soorten stapels: de registerstapel en de geheugenstapel.
Registreer stapel
De registerstapel is ook een geheugenapparaat dat aanwezig is in de geheugeneenheid, maar het verwerkt slechts een kleine hoeveelheid gegevens. De stapeldiepte is altijd beperkt in de registerstapel omdat de grootte van de registerstapel erg klein is in vergelijking met het geheugen.
Push-bewerking in registerstapel
Stap 1: De stapelaanwijzer wordt met 1 verhoogd.
SP ← SP + 1
Stap 2: Voer de gegevens in de stapel in.
1000 [SP] ← CT
Waar DR is het gegevensregister
Stap 3: Controleer of de stapel vol is of niet
if (sp = 0) then (volledig ← 1)
Stap 4: Markeer niet leeg
leeg ← 0
Pop-operatie in registerstapel
Stap 1: Lees gegevens uit de stapel.
DR ← M [SP]
Stap 2: Stapelpunt verlagen.
SP ← SP-1
Stap 3: Controleer of de stapel leeg is of niet
als sp = 0 dan leeg ← 1
De stapelorganisatie van de 64-bits registerstapel wordt weergegeven in de onderstaande afbeelding.
Registreer stapelorganisatie
Geheugenstapel
In de geheugenstapel is de stapeldiepte flexibel. Het neemt een grote hoeveelheid geheugengegevens in beslag, terwijl in de registerstapel slechts een eindig aantal geheugenwoorden wordt opgeslagen.
Push-bewerking in geheugenstapel
Stap 1: SP ← SP-1
Stap 2: 1000 [SP] ← CT
Pop-bewerking in Memory Stack
Stap 1: DR ← M [SP]
Stap 2: SP ← SP-1
In vergelijking met de registereenheid slaat de geheugeneenheid een grote hoeveelheid gegevens op. Het geheugenstapelcijfer wordt weergegeven in de onderstaande afbeelding.
Geheugenstapel
De totale geheugeneenheid is verdeeld in drie delen, de eerste geheugeneenheid heeft het programma (niets dan instructies), het tweede deel is data (operanden) en het derde deel is stapel. De programma-instructies worden altijd opgeslagen in de programmateller (PC), de dataregisters worden geïdentificeerd door het adresregister (AR). Het adres 3000 tot 4001 dat wordt gebruikt voor de stapel en het eerste item of element wordt opgeslagen op 4001.
Stapel- / stapelaanwijzer in microprocessor 8085
De programmeurweergave van 8085 microprocessor bevat registers voor algemene doeleinden en registers voor speciale doeleinden De registers voor algemene doeleinden zijn A, B, C, D, E, H, L, en de registers voor speciale doeleinden zijn SP (Stack Pointer) en PC (Program Counter). De programmeurweergave van de 8085-microprocessor wordt weergegeven in de onderstaande afbeelding.
Programmer View van 8085
De stapelaanwijzer is een 16-bits register met geheugenadres, stel dat de inhoud van de stapelaanwijzer (SP) FC78H is, dan interpreteert de microprocessor 8085 deze. De geheugenlocaties hebben nuttige informatie van FC78H tot FFFH en van FC77H tot 0000H heeft de geheugenlocatie geen bruikbare informatie. De interpretatie van de stapelaanwijzer wordt weergegeven in de onderstaande afbeelding.
Interpretatie van Stack Pointer
Basisbewerkingen van Stack / Stack Pointer
Er zijn twee bewerkingen van de stapel, dit zijn: PUSH-bewerking en POP-bewerking.
PUSH-bediening
De PUSH betekent een element in de stapel duwen of plaatsen. De PUSH-bewerking verhoogt altijd de stapelaanwijzer en de POP-bewerking verhoogt altijd de stapelaanwijzer. In het geval van een push-operatie, moeten we controleren of er een vrije ruimte beschikbaar is of niet. Als er vrije ruimte beschikbaar is, kunnen we naar de push-operatie gaan, als er geen vrije ruimte beschikbaar is, treedt er een foutmelding op die overloop is. De overloop moet worden gecontroleerd in het geval van een duwbediening. De basiswerking van push en pop wordt weergegeven in de onderstaande afbeelding.
Basisbediening van PUSH en POP
Figuur (a) is de stapel. Als je het element dat het element invoert in de stapel wilt duwen, moet je duwen (s, a), waarbij ‘s’ niets anders is dan een stapel. In de stapel plaatsen we het ‘a’ -element en deze bewerking wordt weergegeven in figuur (b). Zie figuur (3), stel dat de stapel drie elementen a, b, c bevat, en de stapel is gevuld met een element.
Als je een vierde element-‘d’ wilt invoegen met push (s, d), maar er is geen ruimte beschikbaar om het element in te voegen, dan geeft dit aan dat de stapel overloopt. De overflow-terminologie wordt gebruikt wanneer de stack vol is en het algoritme van push-operatie wordt hieronder weergegeven.
push (stack [], top, max stack, item)
if (top == maxstack-1)
print 'overflow'
anders
boven = boven + 1
stack [top] = item
einde
POP-werking
De POP betekent het verwijderen van het element bovenaan de stapel. In het geval van een pop-operatie, moeten we controleren of de stapel in eerste instantie leeg is of niet. Als de stapel aanvankelijk leeg is, treedt er een underflow-situatie op. Stel dat de stapel leeg is, maar u wilt de elementen in de stapel plaatsen, maar er zijn geen elementen in de stapel, dan leidt dit tot een onderloop van de stapel.
De underflow moet worden gecontroleerd in het geval van een pop-operatie. In pop-operatie, wat het bovenste element ook aanwezig is in de stapel dat moet worden gepopt of verwijderd, dus het is niet nodig om te vermelden welk element zal worden gepopt, standaard wordt het bovenste element gepopt. Het algoritme van de pop-operatie wordt hieronder weergegeven.
pop (stapel [], boven, item)
if (top == - 1)
print 'underflow'
anders
item = stapel [boven]
top = top-1
Voorbeeld
De elementen worden ingevoegd in de volgorde A, B, C, D, E, het vertegenwoordigt de stapel van vijf elementen. In figuur (a) willen we element 'A' op de stapel duwen, dan wordt de bovenkant nul (top = 0), op dezelfde manier wordt de bovenkant = 1 wanneer element 'B' wordt ingedrukt, top = 2 wanneer het element 'C' wordt geduwd, top = 3 wanneer het 'D'-element wordt ingedrukt en top = 4 wanneer het' E'-element wordt ingedrukt.
Dus wat de elementen die ik heb genomen, in de stapel worden geplaatst, nu is de stapel vol. Als je een ander element wilt duwen, is er geen plaats in de stapel, dus het geeft de overloop aan. Nu is de stapel vol. Als je het element ‘E’ wilt laten knappen, moet het eerst worden verwijderd. De push-operatie wordt getoond in de onderstaande afbeelding.
Push-operatie
We moeten de pop-bewerking gebruiken om de elementen in de stapel te verwijderen. Dus noem gewoon pop () en schrijf geen argumenten in de pop omdat het standaard het bovenste element verwijdert. Het eerste ‘E’ element wordt verwijderd, het volgende ‘D’ element… .. ’A’. Wanneer de bovenste elementen worden verwijderd, neemt de bovenste waarde af. Wanneer top = -1 geeft de stapel een underflow aan. De pop-operatie wordt getoond in de onderstaande afbeelding.
POP-werking
Dit is dus de uitleg van hoe de elementen in de stapel worden ingevoegd en verwijderd door middel van push en pop.
Toepassingen
De toepassingen van de stapel / stapel-aanwijzer zijn
- String omkering
- Evenwichtige haakjes
- ONGEDAAN / VINGER
- Systeemstack voor activeringsrecords
- Tussenvoegsel, voorvoegsel, postfix, uitdrukking
Veelgestelde vragen
1). Wat is de stapelwijzer in de arm?
Het stapelaanwijzerregister (R13) wordt gebruikt als een aanwijzer naar de actieve stapel in ARM.
2). Waarom is de stapelwijzer 16 bit?
De stapelaanwijzer (SP) en de programmateller (pc) die worden gebruikt om de vorige locatie op te slaan en het geheugenlocatie-adres is 16 bits, dus de stapelaanwijzer (SP) is ook 16 bits.
3). Wat is de rol van de stapelaanwijzer?
De rol van de stapelaanwijzer (SP) is om de bovenkant van het element in de stapel aan te geven.
4). Welke stapel wordt gebruikt in 8085?
De stapel die in 8085 wordt gebruikt, is Last In First Out (LIFO).
5). Is de stapelwijzer een register?
Ja, de stapelaanwijzer (SP) is een adresregister dat altijd de bovenkant van het element in de stapel aangeeft.
