Stakken er intet andet end den lineære datastruktur, hvor indsættelse og sletning kun finder sted i den ene ende. Indsættelsesoperationen har et specielt navn kendt som PUSH, og sletningsoperationen har også et specielt navn kendt som POP. PUSH og POP er to grundlæggende operationer, der kun kunne udføres i en bestemt stak. Det er en gruppe hukommelsesplaceringer, og hukommelsesplaceringerne er relateret til enten læsehukommelse eller skrivehukommelse. Dette bruges til lagring af binær information under udførelsen af programmet, når vi udfører et hvilket som helst program, så vil indholdet af det program blive gemt i stakken. Det følger Sidste ind først ud (LIFO), og det bruges kun til lagring og hentning af data, men ikke til lagring af data. Den korte forklaring af stak / stakmarkøren diskuteres nedenfor.
Hvad er Stack / Stack Pointer?
Definition: Stakken er en lagerenhed, der bruges til lagring af information eller data på en måde som LIFO (Last In First Out). Når vi indtaster dataene i form af LIFO-måde, er det element, der først skal slettes, det sidste indsætterelement, så det sidst indsatte element tages først ud. Det er hukommelsesenheden i et adresseregister kaldet stack pointer (SP). Stakmarkøren angiver altid det øverste element i stakken, hvilket betyder hvilken placering dataene skal indsættes.
Typer af stak
Der er to typer stakke, de er registerstak og hukommelsesstak.
Registrer stak
Registerstakken er også en hukommelsesenhed, der findes i hukommelsesenheden, men den håndterer kun en lille mængde data. Stakdybden er altid begrænset i registerstakken, fordi størrelsen på registerstakken er meget lille sammenlignet med hukommelsen.
Skub operation i Register Stack
Trin 1: Stakmarkøren forøges med 1.
SP ← SP + 1
Trin 2: Indtast dataene i stakken.
1000 [SP] ← CT
Hvor DR er dataregisteret
Trin 3: Kontroller, om stakken er fuld eller ej
hvis (sp = 0) så (fuld ← 1)
Trin 4: Marker ikke tom
tom ← 0
Popdrift i Register Stack
Trin 1: Læs data fra stakken.
DR ← M [SP]
Trin 2: Reducer stakpunkt.
SP ← SP-1
Trin 3: Kontroller, om stakken er tom eller ej
hvis sp = 0 så tom ← 1
Stackorganisationen af 64-bit registerstakken er vist i nedenstående figur.
Registrer Stack Organisation
Memory Stack
I hukommelsesstakken er stackdybden fleksibel. Det optager en stor mængde hukommelsesdata, mens der i registerstakken kun lagres et begrænset antal hukommelsesord.
Skubbetjening i hukommelsesstakken
Trin 1: SP ← SP-1
Trin 2: 1000 [SP] ← CT
Pop-operation i Memory Stack
Trin 1: DR ← M [SP]
Trin 2: SP ← SP-1
Sammenlignet med registerenheden lagrer hukommelsesenheden en stor mængde data. Hukommelsesstakstallet er vist i nedenstående figur.
Memory Stack
Den samlede hukommelsesenhed er opdelt i tre dele, den første hukommelsesenhed har programmet (intet andet end instruktioner), den anden del er data (operander) og den tredje del er stak. Programinstruktionerne gemmes altid i programtælleren (PC), dataregistrene identificeres af adresseregistret (AR). Adressen 3000 til 4001, der bruges til stakken, og det første element eller element er lagret ved 4001.
Stak / stak-markør i 8085 mikroprocessor
Programmeringsvisningen af 8085 mikroprocessor indeholder generelle registre og specialregistre . De generelle formålsregistre er A, B, C, D, E, H, L, og specialregistrene er SP (Stack Pointer) og PC (Program Counter). Programmeringsvisningen af 8085 mikroprocessor er vist i nedenstående figur.
Programmørvisning af 8085
Stakmarkøren er et 16-bit register, der indeholder hukommelsesadresse, antag, at stakmarkørens (SP) indhold er FC78H, så fortolker mikroprocessoren 8085 den. Hukommelsesplaceringerne har nyttige oplysninger fra FC78H til FFFH, og fra FC77H til 0000H har hukommelsesplaceringen ikke nyttige oplysninger. Fortolkningen af stakmarkøren er vist i nedenstående figur.
Fortolkning af stakpointer
Grundlæggende betjening af stak / stakmarkør
Der er to operationer af stakken, de er: PUSH-drift og POP-drift.
PUSH-betjening
PUSH betyder at skubbe eller indsætte et element i stakken. PUSH-operationen forøger altid stakemarkøren, og POP-handlingen reducerer altid stakemarkøren. I tilfælde af en push-operation skal vi kontrollere, om der er ledig plads til rådighed eller ej. Hvis ledig plads er tilgængelig, kan vi gå til push-operationen, hvis ledig plads ikke er tilgængelig, opstår der en fejlmeddelelse, der er overløb. Overløbet skal kontrolleres i tilfælde af henholdsvis skubbetjening. Den grundlæggende funktion af push og pop er vist i nedenstående figur.
Grundlæggende betjening af PUSH og POP
Figur (a) er stakken. Hvis du vil skubbe elementet, der er at indsætte elementet i stakken, skal du skubbe (s, a), hvor 's' ikke er andet end en stak. I stakken placerer vi 'a'-elementet, og denne operation vises i figur (b). Se figuren (3), antag at stakken indeholder tre elementer a, b, c, og stakken er fyldt med et element.
Hvis du vil indsætte et fjerde element-'d 'ved hjælp af push (s, d), men der ikke er plads til at indsætte elementet, betyder det, at stakken er overløb. Overløbsterminologien bruges, når stakken er fuld, og algoritmen for push-operation vises nedenfor.
skub (stak [], top, maks stak, vare)
hvis (top == maxstack-1)
{
print “overløb”
}
andet
{
top = top + 1
stak [top] = vare
}
ende
POP-drift
POP betyder at slette elementet øverst i stakken. I tilfælde af popoperation skal vi kontrollere, om stakken oprindeligt er tom eller ej. Hvis stakken oprindeligt er tom, opstår der en understrømningssituation. Antag, at stakken er tom, men du vil pope elementerne i stakken, men der er ingen elementer i stakken, så fører den til stabelunderstrømning.
Underflowet skal kontrolleres i tilfælde af pop-operation. I pop-operation uanset hvilket topelement der er til stede i stakken, der skal poppes eller slettes, så det er ikke nødvendigt at nævne hvilket element der poppes, som standard poppes det øverste element. Algoritmen til popoperation er vist nedenfor.
pop (stak [], top, vare)
hvis (top == - 1)
{
udskriv “underflow”
}
andet
{
element = stak [top]
top = top-1
}
Eksempel
Elementerne indsættes i rækkefølgen som A, B, C, D, E, det repræsenterer stakken med fem elementer. I figur (a) ønsker vi at skubbe 'A' element på stakken, så bliver toppen nul (top = 0), ligeledes toppen = 1 når 'B' element skubbes, top = 2 når 'C' elementet skubbes, top = 3 når 'D' elementet skubbes, og top = 4 når 'E' elementet skubbes.
Så uanset hvilke elementer jeg har taget, placeres i stakken, nu er stakken fuld. Hvis du vil skubbe et andet element, er der ikke plads i stakken, så det angiver overløbet. Nu er stakken fuld, hvis du vil pope elementet 'E' elementet skal først slettes. Push-operationen er vist i nedenstående figur.
Push-operation
Vi skal bruge popoperationen til at slette elementerne i stakken. Så bare nævne pop () skriv ikke argumenter i pop, fordi det som standard sletter det øverste element. Det første 'E' element slettes næste 'D' element ... .. 'A'. Når topelementerne slettes, falder topværdien. Når top = -1 angiver stakken understrømning. Popoperationen er vist i nedenstående figur.
POP-drift
Så dette er forklaringen på, hvordan elementerne indsættes og slettes i stakken ved hjælp af push- og pop-operation.
Ansøgninger
Anvendelserne til stak / stakmarkøren er
- Vending af streng
- Balanceret parentes
- Fortryd / FINGER
- Systemstak til aktiveringsposter
- Infix, præfiks, postfix, udtryk
Ofte stillede spørgsmål
1). Hvad er stakmarkøren i armen?
Stakpointerregistret (R13) bruges som en markør til den aktive stak i ARM.
2). Hvorfor er stackmarkøren 16 bit?
Stakmarkøren (SP) og programtælleren (PC), der bruges til at gemme den tidligere placering, og hukommelsesplaceringsadressen er 16 bit, så stakemarkøren (SP) er også på 16 bit.
3). Hvad er stakemarkørens rolle?
Stakemarkørens (SP) rolle er at angive toppen af elementet i stakken.
4). Hvilken stak bruges i 8085?
Stakken, der blev brugt i 8085, er Last In First Out (LIFO).
5). Er stakemarkør et register?
Ja, stakemarkøren (SP) er et adresseregister, der altid angiver toppen af elementet i stakken.
