Stapeln är inget annat än den linjära datastrukturen där insättning och radering endast sker i ena änden. Införingsoperationen har ett speciellt namn som kallas PUSH och borttagningsoperationen har också ett speciellt namn som kallas POP. PUSH och POP är två grundläggande operationer som endast kan utföras i en viss stack. Det är en grupp minnesplatser och minnesplatserna är relaterade till antingen läsminne eller skrivminne. Detta används för att lagra binär information under genomförandet av programmet, när vi kör något program kommer innehållet i det programmet att lagras i stacken. Det följer Sist in först ut (LIFO) och den används endast för lagring och hämtning av data men inte för lagring av data. Den korta förklaringen av stack / stack-pekaren diskuteras nedan.
Vad är Stack / Stack Pointer?
Definition: Stapeln är en lagringsenhet som används för att lagra information eller data på ett sätt som LIFO (Last In First Out). Närhelst vi matar in data i form av LIFO-sätt är elementet som måste raderas först det sista infogningselementet, så det senast införda elementet tas ut först. Det är minnesenheten i ett adressregister som kallas stack pointer (SP). Stackpekaren anger alltid det översta elementet i stacken som betyder vilken plats data måste infogas.
Typer av stack
Det finns två typer av stackar, de är registerstack och minnestack.
Registrera Stack
Registerstacken är också en minnesenhet som finns i minnesenheten, men den hanterar endast en liten mängd data. Stapeldjupet är alltid begränsat i registerstacken eftersom storleken på registerstacken är mycket liten jämfört med minnet.
Skjut operation i Register Stack
Steg 1: Stapelpekaren ökas med 1.
SP ← SP + 1
Steg 2: Ange data i stacken.
1000 [SP] ← CT
Där DR är dataregistret
Steg 3: Kontrollera om stacken är full eller inte
if (sp = 0) då (full ← 1)
Steg 4: Markera inte tomt
tom ← 0
Popoperation i Register Stack
Steg 1: Läs data från stacken.
DR ← M [SP]
Steg 2: Minska stackpunkten.
SP ← SP-1
Steg 3: Kontrollera om stacken är tom eller inte
om sp = 0 så är tom ← 1
Stackorganisationen för 64-bitars registerstacken visas i figuren nedan.
Registrera Stack Organisation
Memory Stack
I minnestacken är stapeldjupet flexibelt. Den upptar en stor mängd minnesdata, medan endast ett begränsat antal minnesord i registerstacken lagras.
Push-drift i minnesstapeln
Steg 1: SP ← SP-1
Steg 2: 1000 [SP] ← CT
Popoperation i Memory Stack
Steg 1: DR ← M [SP]
Steg 2: SP ← SP-1
Jämfört med registerenheten lagrar minnesenheten en stor mängd data. Minnesstapeln visas i figuren nedan.
Memory Stack
Den totala minnesenheten är uppdelad i tre delar, den första minnesenheten har programmet (ingenting annat än instruktioner), den andra delen är data (operander) och den tredje delen är stack. Programinstruktionerna lagras alltid i programräknaren (PC), dataregistren identifieras av adressregistret (AR). Adressen 3000 till 4001 som används för stacken och det första objektet eller elementet lagras vid 4001.
Stack / Stack-pekare i 8085 mikroprocessor
Programmerarvyn 8085 mikroprocessor innehåller allmänna register och specialregister . Registren för allmänna ändamål är A, B, C, D, E, H, L och specialregistret är SP (Stack Pointer) och PC (Program Counter). Programmeringsvyn för 8085 mikroprocessor visas i figuren nedan.
Programmerarvy av 8085
Stackpekaren är ett 16-bitars register som innehåller minnesadress, antag att stackpekarens (SP) innehåll är FC78H, så tolkar mikroprocessorn 8085 den. Minnesplatserna har användbar information från FC78H till FFFH och från FC77H till 0000H har minnesplatsen ingen användbar information. Tolkningen av stackpekaren visas i figuren nedan.
Tolkning av Stack Pointer
Grundläggande funktioner för Stack / Stack Pointer
Det finns två operationer i stacken: PUSH-operation och POP-operation.
PUSH-drift
PUSH betyder att man trycker på eller sätter in ett element i stacken. PUSH-operationen ökar alltid stackpekaren och POP-operationen minskar alltid stackpekaren. Vid en push-operation måste vi kontrollera om det finns ledigt utrymme tillgängligt eller inte. Om ledigt utrymme är tillgängligt kan vi gå till push-operationen, om ledigt utrymme inte är tillgängligt uppstår felmeddelande som är överflöd. Överflödet ska kontrolleras vid tryckoperation respektive. Den grundläggande funktionen för push och pop visas i figuren nedan.
Grundläggande användning av PUSH och POP
Figur (a) är stapeln. Om du vill trycka in elementet som är att sätta in elementet i stacken måste du trycka på (s, a) där 's' inte är något annat än en stack. I stacken placerar vi ”a” -elementet och denna operation visas i figur (b). Se figuren (3), antag att stacken innehåller tre element a, b, c och stacken är fylld med ett element.
Om du vill infoga ett fjärde element-'d 'med push (s, d), men det inte finns något utrymme att infoga elementet, indikerar det att stacken är överflödig. Överflödsterminologin används när stacken är full och algoritmen för push-operation visas nedan.
tryck (stack [], topp, max stack, objekt)
if (top == maxstack-1)
{
skriva ut 'överflöd'
}
annan
{
top = top + 1
stack [top] = objekt
}
slutet
POP-drift
POP betyder att radera elementet högst upp i stacken. Vid popoperation måste vi kontrollera om stacken initialt är tom eller inte. Om stacken initialt är tom uppstår det en situation med underflöde. Antag att stacken är tom, men du vill popa elementen i stacken men det finns inga element i stacken, då leder det till stack underflöde.
Underflödet ska kontrolleras vid pop-funktion. I pop-funktion, oavsett vilket toppelement som finns i stacken som ska poppas eller tas bort, så behöver du inte nämna vilket element som kommer att poppas, som standard kommer det översta elementet att poppas. Algoritmen för popoperation visas nedan.
pop (stack [], top, item)
if (top == - 1)
{
skriva ut 'underflöde'
}
annan
{
objekt = stack [överst]
topp = topp-1
}
Exempel
Elementen infogas i ordningen som A, B, C, D, E, det representerar stapeln med fem element. I figur (a) vill vi trycka 'A' -elementet på stapeln då blir toppen noll (topp = 0), på samma sätt toppen = 1 när 'B' -elementet trycks, topp = 2 när 'C' -elementet trycks, topp = 3 när 'D' -elementet trycks in, och topp = 4 när 'E' -elementet trycks in.
Så oavsett vilka element jag har tagit placeras i stacken, nu är stacken full. Om du vill trycka på ett annat element finns det ingen plats i stacken, så det indikerar överflödet. Nu är stacken full om du vill poppa elementet 'E' måste först raderas. Push-operationen visas i nedanstående bild.
Push-operation
Vi måste använda pop-operationen för att ta bort elementen i stacken. Så nämn bara pop () skriv inte argument i pop eftersom det som standard raderar toppelementet. Det första 'E' -elementet raderas nästa 'D' -element ... .. 'A'. När toppelementen raderas minskar toppvärdet. När topp = -1 visar stacken underflöde. Popoperationen visas i figuren nedan.
POP-drift
Så detta är förklaringen av hur elementen sätts in och tas bort i stacken med hjälp av push- och pop-operation.
Applikationer
Tillämpningarna för stack / stack-pekaren är
- Vändning av sträng
- Balanserad parentes
- Ångra / FINGER
- Systemstack för aktiveringsposter
- Infix, prefix, postfix, expression
Vanliga frågor
1). Vad är stackpekaren i armen?
Stackpekarregistret (R13) används som en pekare till den aktiva stacken i ARM.
2). Varför är stackpekaren 16 bitar?
Stackpekaren (SP) och programräknaren (PC) som används för att lagra den tidigare platsen och minnesplaceringsadressen är 16 bitar, så stackpekaren (SP) har också 16 bitar.
3). Vilken roll har stackpekaren?
Stapelpekarens (SP) roll är att ange toppen av elementet i stacken.
4). Vilken stack används i 8085?
Stapeln som används i 8085 är Last In First Out (LIFO).
5). Är stackpekaren ett register?
Ja, stackpekaren (SP) är ett adressregister som alltid anger toppen av elementet i stacken.