Zásobník není nic jiného než lineární datová struktura, kde vkládání a mazání probíhá pouze na jednom konci. Operace vložení má speciální název známý jako PUSH a operace odstranění má také speciální název známý jako POP. PUSH a POP jsou dvě základní operace, které lze provést pouze v konkrétním zásobníku. Jedná se o skupinu paměťových míst a paměťová místa souvisejí buď s pamětí pro čtení, nebo pro zápis do paměti. Slouží k ukládání binárních informací během provádění programu, když provádíme jakýkoli program, pak se obsah tohoto programu uloží do zásobníku. Následuje Last In First Out (LIFO) a používá se pouze k ukládání a načítání dat, ale nepoužívá se k ukládání dat. Stručné vysvětlení ukazatele zásobníku / zásobníku je popsáno níže.
Co je Stack / Stack Pointer?
Definice: Zásobník je úložné zařízení, které se používá k ukládání informací nebo dat způsobem LIFO (Last In First Out). Kdykoli zadáme data ve formě LIFO, je prvkem, který je třeba nejdříve odstranit, poslední vložený prvek, takže poslední vložený prvek je odebrán jako první. Je to paměťová jednotka v registru adres, která se nazývá stack pointer (SP). Ukazatel zásobníku vždy označuje horní prvek v zásobníku, což znamená, do kterého umístění musí být data vložena.
Druhy zásobníku
Existují dva typy zásobníků, kterými jsou zásobník registrů a zásobník paměti.
Zaregistrovat zásobník
Zásobník registrů je také paměťovým zařízením přítomným v paměťové jednotce, ale zpracovává pouze malé množství dat. Hloubka stohu je v zásobníku registrů vždy omezena, protože velikost zásobníku registrů je ve srovnání s pamětí velmi malá.
Operace push v zásobníku registrů
Krok 1: Ukazatel zásobníku se zvyšuje o 1.
SP ← SP + 1
Krok 2: Zadejte data do zásobníku.
1000 [SP] ← CT
Kde DR je datový registr
Krok 3: Zkontrolujte, zda je zásobník plný nebo ne
if (sp = 0) then (full ← 1)
Krok 4: Označit jako prázdné
prázdný ← 0
Popová operace v zásobníku registrů
Krok 1: Čtení dat ze zásobníku.
DR ← M [SP]
Krok 2: Snížení bodu zásobníku.
SP ← SP-1
Krok 3: Zkontrolujte, zda je zásobník prázdný nebo ne
pokud sp = 0, pak prázdný ← 1
Organizace zásobníku zásobníku 64bitových registrů je uvedena na následujícím obrázku.
Zaregistrujte organizaci zásobníku
Stack paměti
V zásobníku paměti je hloubka zásobníku flexibilní. Zabírá velké množství dat v paměti, zatímco v zásobníku registrů bude uložen pouze konečný počet slov v paměti.
Push operace v zásobníku paměti
Krok 1: SP ← SP-1
Krok 2: 1000 [SP] ← CT
Popová operace v paměti Stack
Krok 1: DR ← M [SP]
Krok 2: SP ← SP-1
Ve srovnání s registrační jednotkou ukládá paměťová jednotka velké množství dat. Obrázek zásobníku paměti je zobrazen na následujícím obrázku.
Stack paměti
Celková paměťová jednotka je rozdělena na tři části, první paměťová jednotka má program (nic než instrukce), druhá část jsou data (operandy) a třetí část je zásobník. Programové pokyny se vždy ukládají do počitadla programu (PC), datové registry jsou identifikovány adresovým registrem (AR). Adresa 3000 až 4001 použitá pro zásobník a první položku nebo prvek je uložena na 4001.
Ukazatel zásobníku / zásobníku v mikroprocesoru 8085
Pohled programátora na 8085 mikroprocesor obsahuje univerzální registry a účelové registry . Registry pro všeobecné účely jsou A, B, C, D, E, H, L a registry pro speciální účely jsou SP (Stack Pointer) a PC (Program Counter). Pohled programátora na mikroprocesor 8085 je uveden na následujícím obrázku.
Pohled programátora na 8085
Ukazatel zásobníku je 16bitový registr, který obsahuje adresu paměti, předpokládejme, že obsah zásobníku (SP) je FC78H, pak jej mikroprocesor 8085 interpretuje. Paměťová místa obsahují užitečné informace od FC78H do FFFH a od FC77H do 0000H paměťová místa neobsahují užitečné informace. Interpretace ukazatele zásobníku je uvedena na následujícím obrázku.
Interpretace ukazatele zásobníku
Základní operace zásobníku / ukazatele zásobníku
Existují dvě operace zásobníku: PUSH operace a POP operace.
PUSH provoz
PUSH znamená tlačit nebo vložit prvek do stohu. Operace PUSH vždy zvýší ukazatel zásobníku a operace POP vždy sníží ukazatel zásobníku. V případě operace push musíme zkontrolovat, zda je nebo není k dispozici volné místo. Pokud je k dispozici volné místo, můžeme přejít na operaci push, pokud volné místo není k dispozici, objeví se chybová zpráva, která přeteče. Přetečení je třeba zkontrolovat v případě tlakové operace. Základní operace push a pop je uvedena na následujícím obrázku.
Základní funkce PUSH a POP
Obrázek (a) je zásobník. Pokud chcete vložit prvek, který vkládá prvek do zásobníku, musíte tlačit (s, a), kde „s“ není nic jiného než zásobník. V zásobníku umisťujeme prvek „a“ a tato operace je znázorněna na obrázku (b). Viz obrázek (3), předpokládejme, že zásobník obsahuje tři prvky a, b, c a zásobník je naplněn prvkem.
Pokud chcete vložit čtvrtý prvek - „d“ pomocí push (s, d), ale není k dispozici žádný prostor pro vložení prvku, znamená to, že je zásobník přetečen. Terminologie přetečení se používá, když je zásobník plný a algoritmus operace push je zobrazen níže.
tlačit (zásobník [], horní, maximální zásobník, položka)
if (top == maxstack-1)
{
tisknout „přetečení“
}
jiný
{
nahoru = nahoru + 1
stack [top] = položka
}
konec
Provoz POP
POP znamená odstranění prvku v horní části zásobníku. V případě pop operace musíme zkontrolovat, zda je zásobník zpočátku prázdný nebo ne. Pokud je zásobník zpočátku prázdný, dojde k situaci podtečení. Předpokládejme, že zásobník je stále prázdný, chcete vyskakovat prvky v zásobníku, ale v zásobníku nejsou žádné prvky, pak to vede k podtečení zásobníku.
Podtečení je třeba zkontrolovat v případě pop operace. V popové operaci bez ohledu na to, zda je v zásobníku umístěn horní prvek, který by měl být vyskakován nebo odstraněn, není třeba uvádět, který prvek bude vyskakován, ve výchozím nastavení bude vyskakován nejvyšší prvek. Algoritmus popové operace je uveden níže.
pop (zásobník [], nahoře, položka)
if (top == - 1)
{
tisknout „podtečení“
}
jiný
{
item = stack [nahoru]
top = top-1
}
Příklad
Prvky se vkládají v pořadí A, B, C, D, E, což představuje hromadu pěti prvků. Na obrázku (a) chceme do zásobníku tlačit prvek 'A', pak se vrchol stane nulou (top = 0), podobně top = 1, když je tlačen prvek 'B', top = 2, když je prvek 'C' je tlačen, top = 3, když je tlačen prvek 'D', a top = 4, když je tlačen prvek 'E'.
Takže ať už jsou všechny prvky, které jsem vzal, umístěny do zásobníku, nyní je zásobník plný. Pokud chcete tlačit na jiný prvek, není v zásobníku místo, takže to naznačuje přetečení. Nyní je zásobník plný, pokud chcete vyskočit, nejprve musíte odstranit prvek „E“. Provoz push je zobrazen na následujícím obrázku.
Push operace
K odstranění prvků v zásobníku musíme použít operaci pop. Stačí tedy zmínit pop (), nepište argumenty do popu, protože ve výchozím nastavení odstraní horní prvek. První prvek „E“ se vypouští další prvek „D“… „A“. Když se top prvky mazají, pak se top hodnota snižuje. Když top = -1, zásobník označuje podtečení. Popová operace je zobrazena na následujícím obrázku.
Provoz POP
Toto je vysvětlení toho, jak jsou prvky vkládány a mazány do zásobníku pomocí operace push a pop.
Aplikace
Aplikace ukazatele zásobníku / zásobníku jsou
- Obrácení řetězce
- Vyvážená závorka
- ZPĚT / PRST
- Systémový zásobník pro aktivační záznamy
- Infix, prefix, postfix, výraz
Časté dotazy
1). Co je ukazatel zásobníku v paži?
Registr ukazatele zásobníku (R13) použitý jako ukazatel na aktivní zásobník v ARM.
2). Proč je ukazatel zásobníku 16 bitů?
Ukazatel zásobníku (SP) a programový čítač (PC) používané k uložení předchozího umístění a adresa umístění paměti je 16 bitů, takže ukazatel zásobníku (SP) je také 16 bitový.
3). Jaká je role ukazatele zásobníku?
Úlohou ukazatele zásobníku (SP) je označit vrchol prvku v zásobníku.
4). Který zásobník se používá v 8085?
Zásobník použitý v 8085 je Last In First Out (LIFO).
5). Je ukazatel zásobníku registr?
Ano, ukazatel zásobníku (SP) je registr adres, který vždy označuje horní část prvku v zásobníku.
