Stiva nu este altceva decât structura liniară de date în care inserarea și ștergerea au loc doar la un capăt. Operația de inserare are un nume special cunoscut sub numele de PUSH și operațiunea de ștergere are, de asemenea, un nume special cunoscut sub numele de POP. PUSH și POP sunt două operațiuni fundamentale care ar putea fi efectuate numai într-o anumită stivă. Este un grup de locații de memorie, iar locațiile de memorie sunt legate fie de memoria citită, fie de memoria de scriere. Aceasta este utilizată pentru stocarea informațiilor binare în timpul execuției programului, când executăm orice program, atunci conținutul acelui program va fi stocat în stivă. Urmează Last In First Out (LIFO) și este utilizat numai pentru stocarea și recuperarea datelor, dar nu este utilizat pentru stocarea datelor. Explicația succintă a indicatorului stivă / stivă este discutată mai jos.
Ce este Stack / Stack Pointer?
Definiție: Stiva este un dispozitiv de stocare, utilizat pentru stocarea informațiilor sau datelor într-un mod LIFO (Last In First Out). Ori de câte ori introducem datele sub formă LIFO, elementul care trebuie șters mai întâi este ultimul element inserator, deci ultimul element inserat este scos mai întâi. Este unitatea de memorie dintr-un registru de adrese numit indicator de stivă (SP). Indicatorul stivei indică întotdeauna elementul de sus din stivă, ceea ce înseamnă locația în care trebuie inserate datele.
Tipuri de stive
Există două tipuri de stive: sunt stiva de registre și stiva de memorie.
Înregistrați stiva
Stiva de registre este, de asemenea, un dispozitiv de memorie prezent în unitatea de memorie, dar gestionează doar o cantitate mică de date. Adâncimea stivei este întotdeauna limitată în stiva de registre, deoarece dimensiunea stivei de registre este foarte mică în comparație cu memoria.
Apăsați operațiunea în registru
Pasul 1: Indicatorul stivei crește cu 1.
SP ← SP + 1
Pasul 2: Introduceți datele în stivă.
1000 [SP] ← CT
Unde DR este registrul de date
Pasul 3: Verificați dacă stiva este plină sau nu
dacă (sp = 0) atunci (complet ← 1)
Pasul 4: Marcați ca gol
gol ← 0
Operațiune Pop în Registrul Stack
Pasul 1: Citiți datele din stivă.
DR ← M [SP]
Pasul 2: Decrementează punctul stivei.
SP ← SP-1
Pasul 3: Verificați dacă stiva este goală sau nu
dacă sp = 0 atunci gol ← 1
Organizarea stivei stivei de registre pe 64 de biți este prezentată în figura de mai jos.
Înregistrați organizația stivei
Stivă de memorie
În stiva de memorie, adâncimea stivei este flexibilă. Ocupă o cantitate mare de date de memorie, în timp ce în teancul de registre va fi stocat doar un număr finit de cuvinte de memorie.
Apăsați operațiunea în memoria stivei
Pasul 1: SP ← SP-1
Pasul 2: 1000 [SP] ← CT
Operați pop în Memory Stack
Pasul 1: DR ← M [SP]
Pasul 2: SP ← SP-1
Comparativ cu unitatea de înregistrare, unitatea de memorie stochează o cantitate mare de date. Figura stivei de memorie este prezentată în figura de mai jos.
Stivă de memorie
Unitatea de memorie totală este împărțită în trei părți, prima unitate de memorie are programul (nimic altceva decât instrucțiuni), a doua parte este de date (operanzi) și a treia parte este stivă. Instrucțiunile programului sunt stocate întotdeauna în contorul de programe (PC), registrele de date sunt identificate prin registrul de adrese (AR). Adresa 3000 la 4001 utilizată pentru stivă și primul articol sau element este stocată la 4001.
Stack / Stack Pointer în 8085 Microprocesor
Vizualizarea programatorului 8085 microprocesor conține registre de uz general și registre cu destinație specială . Registrele de uz general sunt A, B, C, D, E, H, L, iar registrele cu scop special sunt SP (Stack Pointer) și PC (Program Counter). Vizualizarea programatorului microprocesorului 8085 este prezentată în figura de mai jos.
Programator View of 8085
Pointerul stivei este un registru de 16 biți conține adresa de memorie, să presupunem că conținutul indicatorului stivei (SP) este FC78H, apoi microprocesorul 8085 îl interpretează. Locațiile de memorie au informații utile de la FC78H la FFFH și de la FC77H la 0000H locația de memorie nu are informații utile. Interpretarea indicatorului stivei este prezentată în figura de mai jos.
Interpretarea indicatorului Stack
Operațiuni de bază ale indicatorului Stack / Stack
Există două operații ale stivei: operația PUSH și operația POP.
Operațiunea PUSH
PUSH înseamnă împingerea sau introducerea unui element în stivă. Operația PUSH crește întotdeauna indicatorul stivei, iar operația POP scade întotdeauna indicatorul stivei. În cazul unei operații push, trebuie să verificăm dacă există sau nu spațiu liber. Dacă spațiul liber este disponibil, putem merge la operația de împingere, dacă spațiul liber nu este disponibil, apare mesajul de eroare care este depășit. Revărsarea trebuie verificată în cazul operației de împingere respectiv. Operațiunea de bază a push și pop este prezentată în figura de mai jos.
Funcționarea de bază a PUSH și POP
Figura (a) este stiva. Dacă doriți să împingeți elementul care este o inserare a elementului în stivă, trebuie să împingeți (s, a), unde „s” nu este altceva decât o stivă. În stivă, plasăm elementul „a” și această operațiune este prezentată în figura (b). A se vedea figura (3), să presupunem că stiva conține trei elemente a, b, c, iar stiva este umplută cu un element.
Dacă doriți să inserați un al patrulea element -d folosind push (s, d), dar nu există spațiu disponibil pentru a insera elementul, atunci acesta indică faptul că stiva este depășită. Terminologia de revărsare este utilizată atunci când stiva este plină și algoritmul operației push este prezentat mai jos.
împinge (stivă [], sus, stivă maximă, element)
if (top == maxstack-1)
{
tipăriți „overflow”
}
altceva
{
sus = sus + 1
stivă [sus] = element
}
Sfârșit
Operațiune POP
POP înseamnă ștergerea elementului din partea de sus a stivei. În cazul operației pop, trebuie să verificăm dacă stiva este inițial goală sau nu. Dacă stiva este inițial goală, atunci apare o situație de scurgere. Să presupunem că stiva este goală, totuși doriți să scoateți elementele din stivă, dar nu există elemente în stivă, atunci aceasta duce la un flux de stivă.
Debitul trebuie verificat în cazul unei operații pop, respectiv. În operație pop orice element superior este prezent în stivă care ar trebui să fie popped sau șters, deci nu este necesar să menționăm ce element va fi popped, în mod implicit elementul cel mai de sus va fi popped. Algoritmul operației pop este prezentat mai jos.
pop (stack [], top, item)
if (sus == - 1)
{
tipăriți „underflow”
}
altceva
{
item = stack [sus]
top = top-1
}
Exemplu
Elementele sunt inserate în ordinea A, B, C, D, E, reprezintă teancul de cinci elemente. În figura (a), vrem să împingem elementul „A” pe stivă, apoi partea de sus devine zero (sus = 0), în mod similar partea superioară = 1 când elementul „B” este împins, sus = 2 când elementul „C” este împins, sus = 3 când elementul „D” este împins și sus = 4 când este împins elementul „E”.
Deci, indiferent de elementele pe care le-am luat este plasat în stivă, acum stiva este plină. Dacă doriți să împingeți un alt element, nu există loc în stivă, deci indică depășirea. Acum stiva este plină dacă doriți să deschideți elementul „E” trebuie să fie șters mai întâi. Operația de împingere este prezentată în figura de mai jos.
Operațiunea Push
Trebuie să folosim operația pop pentru a șterge elementele din stivă. Deci, menționați pop () nu scrieți argumente în pop, deoarece implicit șterge elementul de sus. Primul element „E” este șters următorul element „D” ... .. „A”. Când elementele de sus se șterg, atunci valoarea de sus scade. Când top = -1, stiva indică o defluxare. Operația pop este prezentată în figura de mai jos.
Operațiune POP
Deci, aceasta este explicația modului în care elementele sunt inserate și șterse în stivă utilizând operația push și pop.
Aplicații
Aplicațiile indicatorului stack / stack sunt
- Inversarea șirului
- Paranteză echilibrată
- UNDO / DEGET
- Stivă de sistem pentru înregistrări de activare
- Infix, prefix, postfix, expresie
Întrebări frecvente
1). Ce este indicatorul stivei în braț?
Registrul indicatorului stivei (R13) utilizat ca indicator al stivei active din ARM.
2). De ce indicatorul de stivă are 16 biți?
Indicatorul de stivă (SP) și contorul de programe (PC) utilizate pentru a stoca locația anterioară și adresa locației de memorie este de 16 biți, astfel încât indicatorul de stivă (SP) este, de asemenea, de 16 biți.
3). Care este rolul indicatorului stivei?
Rolul indicatorului stivei (SP) este de a indica partea de sus a elementului din stivă.
4). Care stivă este utilizată în 8085?
Stiva utilizată în 8085 este Last In First Out (LIFO).
5). Pointerul stack este un registru?
Da, indicatorul stivei (SP) este un registru de adrese care indică întotdeauna partea de sus a elementului din stivă.
