Zásobník nie je nič iné ako lineárna dátová štruktúra, kde vkladanie a mazanie prebieha iba na jednom konci. Operácia vloženia má špeciálny názov známy ako PUSH a operácia odstránenia má tiež špeciálny názov známy ako POP. PUSH a POP sú dve základné operácie, ktoré je možné vykonať iba v konkrétnom zásobníku. Je to skupina pamäťových miest a tieto pamäťové miesta súvisia s pamäťou na čítanie alebo na zápis. Používa sa na ukladanie binárnych informácií počas vykonávania programu, keď vykonávame akýkoľvek program, potom sa obsah tohto programu uloží do zásobníka. Nasleduje to Last In First Out (LIFO) a používa sa iba na ukladanie a načítanie údajov, ale nepoužíva sa na ukladanie údajov. Stručné vysvetlenie ukazovateľa stack / stack je uvedené nižšie.
Čo je Stack / Stack Pointer?
Definícia: Zásobník je úložné zariadenie, ktoré sa používa na ukladanie informácií alebo údajov spôsobom LIFO (Last In First Out). Kedykoľvek zadáme údaje vo forme spôsobu LIFO, prvkom, ktorý je potrebné najskôr vymazať, je posledný vkladací prvok, takže posledný vložený prvok sa vyberie ako prvý. Je to pamäťová jednotka v registri adries, ktorá sa nazýva stack pointer (SP). Ukazovateľ zásobníka vždy označuje horný prvok v zásobníku, čo znamená, na ktoré miesto sa majú údaje vložiť.
Druhy zásobníka
Existujú dva typy zásobníkov, ktorými sú zásobník registrov a zásobník pamäte.
Registrovať stoh
Zásobník registrov je tiež pamäťové zariadenie prítomné v pamäťovej jednotke, ale spracováva iba malé množstvo údajov. Hĺbka stohu je v stohu registrov vždy obmedzená, pretože veľkosť stohu registrov je v porovnaní s pamäťou veľmi malá.
Prevádzka typu push v registri
Krok 1: Ukazovateľ zásobníka sa zvyšuje o 1.
SP ← SP + 1
Krok 2: Zadajte údaje do zásobníka.
1 000 [SP] ← CT
Kde DR je register údajov
Krok 3: Skontrolujte, či je zásobník plný alebo nie
if (sp = 0) then (full ← 1)
Krok 4: Značka nie je prázdna
prázdny ← 0
Popová operácia v zásobníku registrov
Krok 1: Čítanie údajov zo zásobníka.
DR ← M [SP]
Krok 2: Bod zníženia zásobníka.
SP ← SP-1
Krok 3: Skontrolujte, či je stoh prázdny alebo nie
ak sp = 0, potom prázdne ← 1
Organizácia zásobníka 64-bitového registra zaregistrovať sa zobrazuje na obrázku nižšie.
Registrovať organizáciu zásobníkov
Stack pamäte
V zásobníku pamäte je hĺbka stohu flexibilná. Zaberá veľké množstvo pamäťových dát, zatiaľ čo v zásobníku registrov bude uložený iba konečný počet pamäťových slov.
Prevádzka typu push v zásobníku pamäte
Krok 1: SP ← SP-1
Krok 2: 1 000 [SP] ← CT
Popová operácia v pamäti Stack
Krok 1: DR ← M [SP]
Krok 2: SP ← SP-1
V porovnaní s jednotkou registra ukladá pamäťová jednotka veľké množstvo dát. Obrázok zásobníka pamäte je zobrazený na obrázku nižšie.
Stack pamäte
Celková pamäťová jednotka je rozdelená na tri časti, prvá pamäťová jednotka má program (nič iné ako inštrukcie), druhá časť je dátová (operandy) a tretia časť je zásobník. Programové pokyny sa vždy ukladajú do počítadla programov (PC), dátové registre sa identifikujú podľa registra adries (AR). Adresa 3000 až 4001 použitá pre zásobník a prvú položku alebo prvok je uložená na 4001.
Stack / Stack Pointer v mikroprocesore 8085
Programátorský pohľad na 8085 mikroprocesor obsahuje univerzálne registre a účelové registre . Registre na všeobecné účely sú A, B, C, D, E, H, L a registre na špeciálne účely sú SP (Stack Pointer) a PC (Program Counter). Pohľad programátora na mikroprocesor 8085 je uvedený na nasledujúcom obrázku.
Programátorský pohľad na 8085
Ukazovateľ zásobníka je 16-bitový register, ktorý obsahuje adresu pamäte, predpokladajme, že obsah ukazovateľa zásobníka (SP) je FC78H, potom ho interpretuje mikroprocesor 8085. Pamäťové miesta obsahujú užitočné informácie od FC78H do FFFH a od FC77H do 0000H tieto pamäťové miesta neobsahujú užitočné informácie. Interpretácia ukazovateľa zásobníka je uvedená na nasledujúcom obrázku.
Interpretácia ukazovateľa zásobníka
Základné operácie zásobníka / ukazovateľa zásobníka
Existujú dve operácie zásobníka, ktorými sú: PUSH operácia a POP operácia.
PUSH prevádzka
PUSH znamená zatlačenie alebo vloženie prvku do stohu. Operácia PUSH vždy zvýši ukazovateľ zásobníka a operácia POP vždy zníži ukazovateľ zásobníka. V prípade operácie stlačenia musíme skontrolovať, či je alebo nie je k dispozícii voľné miesto. Ak je k dispozícii voľné miesto, môžeme prejsť na operáciu push, ak nie je k dispozícii voľné miesto, potom sa zobrazí chybové hlásenie, ktoré pretečie. Prepad je potrebné skontrolovať v prípade stlačenia. Základné operácie push a pop sú zobrazené na nasledujúcom obrázku.
Základné fungovanie PUSH a POP
Obrázok (a) je komín. Ak chcete vložiť prvok, ktorý vkladá prvok do stohu, musíte ho stlačiť (s, a), kde ‘s’ nie je nič iné ako zásobník. V zásobníku umiestňujeme prvok „a“ a táto operácia je znázornená na obrázku (b). Pozrite si obrázok (3), predpokladajme, že zásobník obsahuje tri prvky a, b, c a zásobník je naplnený prvkom.
Ak chcete vložiť štvrtý prvok „d“ pomocou tlačidiel (s, d), ale na vloženie prvku nie je k dispozícii žiadne miesto, znamená to, že zásobník pretečie. Terminológia pretečenia sa používa, keď je zásobník plný a algoritmus operácie push je zobrazený nižšie.
push (zásobník [], hore, max. zásobník, položka)
if (top == maxstack-1)
{
tlačiť „pretečenie“
}
inak
{
hore = hore + 1
stack [top] = položka
}
koniec
Prevádzka POP
POP znamená odstránenie prvku v hornej časti stohu. V prípade popovej operácie musíme skontrolovať, či je zásobník spočiatku prázdny alebo nie. Ak je stoh spočiatku prázdny, nastane situácia podtečenia. Predpokladajme, že zásobník je prázdny, napriek tomu chcete vložiť prvky do zásobníka, ale v zásobníku nie sú žiadne prvky, potom to vedie k podtečeniu zásobníka.
Prietok je potrebné skontrolovať v prípade popovej operácie. V popovej operácii, nech je v zásobníku prítomný akýkoľvek horný prvok, ktorý by mal byť vyskočený alebo odstránený, takže nie je potrebné spomínať, ktorý prvok bude vyskočený, štandardne bude vysunutý najvyšší prvok. Algoritmus popovej operácie je uvedený nižšie.
pop (zásobník [], horná časť, položka)
ak (hore == - 1)
{
tlačiť „podtečenie“
}
inak
{
item = stack [top]
top = top-1
}
Príklad
Prvky sa vkladajú v poradí A, B, C, D, E, čo predstavuje súhrn piatich prvkov. Na obrázku (a) chceme stlačiť prvok „A“ do zásobníka, potom sa vrchol stane nulou (vrchol = 0), podobne vrchol = 1, keď je posunutý prvok „B“, vrchol = 2, keď je prvok „C“ je stlačené, horná = 3, keď je stlačený prvok „D“, a horná = 4, keď je stlačený prvok „E“.
Takže všetko, čo som vzal, je umiestnené v zásobníku, teraz je zásobník plný. Ak chcete zatlačiť ďalší prvok, v zásobníku nie je miesto, znamená to teda pretečenie. Teraz je zásobník plný, ak chcete vyskočiť, musí byť najskôr odstránený prvok „E“. Prevádzka stlačenia je znázornená na nasledujúcom obrázku.
Prevádzka tlačením
Musíme použiť popovú operáciu na odstránenie prvkov v zásobníku. Stačí teda spomenúť pop (), nepíšte argumenty do popu, pretože predvolene odstráni horný prvok. Prvý prvok „E“ sa vypúšťa nasledujúci prvok „D“ ... „A“. Keď sa horné prvky mazajú, horná hodnota sa zníži. Keď top = -1, stoh naznačuje podtečenie. Popová operácia je zobrazená na obrázku nižšie.
Prevádzka POP
Toto je teda vysvetlenie toho, ako sú prvky vkladané a mazané do zásobníka pomocou operácie push and pop.
Aplikácie
Aplikácie ukazovateľa stack / stack sú
- Obrátenie reťazca
- Vyvážená zátvorka
- ZRUŠIŤ / PRST
- Systémový zásobník pre záznamy o aktivácii
- Infix, prefix, postfix, výraz
Časté otázky
1). Čo je ukazovateľ stohu v ramene?
Register ukazovateľa zásobníka (R13) použitý ako ukazovateľ na aktívny zásobník v ARM.
2). Prečo je ukazovateľ zásobníka 16 bitový?
Ukazovateľ zásobníka (SP) a programové počítadlo (PC) použité na uloženie predchádzajúceho umiestnenia a adresa umiestnenia v pamäti je 16 bitov, takže ukazovateľ zásobníka (SP) je tiež 16 bitový.
3). Aká je úloha ukazovateľa zásobníka?
Úlohou ukazovateľa zásobníka (SP) je označiť hornú časť prvku v zásobníku.
4). Ktorý zásobník sa používa v produkte 8085?
Zásobník používaný v produkte 8085 je Last In First Out (LIFO).
5). Je ukazovateľ zásobníka register?
Áno, ukazovateľ zásobníka (SP) je register adries, ktorý vždy označuje hornú časť prvku v zásobníku.