Stos to nic innego jak liniowa struktura danych, w której wstawianie i usuwanie odbywa się tylko na jednym końcu. Operacja wstawiania ma specjalną nazwę znaną jako PUSH, a operacja usuwania ma również specjalną nazwę znaną jako POP. PUSH i POP to dwie podstawowe operacje, które można wykonać tylko w określonym stosie. Jest to grupa lokalizacji pamięci, a lokalizacje pamięci są powiązane z pamięcią odczytu lub zapisu. Służy do przechowywania informacji binarnych podczas wykonywania programu, gdy wykonujemy dowolny program, zawartość tego programu będzie przechowywana na stosie. Wynika Last In First Out (LIFO) i jest używany tylko do przechowywania i pobierania danych, ale nie jest używany do przechowywania danych. Krótkie wyjaśnienie stosu / wskaźnika stosu jest omówione poniżej.
Co to jest wskaźnik stosu / stosu?
Definicja: Stos to urządzenie magazynujące, używane do przechowywania informacji lub danych w sposób LIFO (Last In First Out). Ilekroć wprowadzamy dane w formie LIFO, element, który ma zostać usunięty jako pierwszy, jest ostatnim elementem wstawiającym, więc ostatni wstawiany element jest wyjmowany jako pierwszy. Jest to jednostka pamięci w rejestrze adresowym zwanym wskaźnikiem stosu (SP). Wskaźnik stosu zawsze wskazuje najwyższy element stosu, co oznacza, w którym miejscu należy wstawić dane.
Rodzaje stosu
Istnieją dwa typy stosów, którymi są stosy rejestrów i stos pamięci.
Zarejestruj stos
Stos rejestrów jest również urządzeniem pamięci obecnym w jednostce pamięci, ale obsługuje tylko niewielką ilość danych. Głębokość stosu jest zawsze ograniczona w stosie rejestrów, ponieważ rozmiar stosu rejestrów jest bardzo mały w porównaniu z pamięcią.
Operacja wypychania w stosie rejestrów
Krok 1: Wskaźnik stosu zwiększa się o 1.
SP ← SP + 1
Krok 2: Wprowadź dane do stosu.
1000 [SP] ← CT
Gdzie DR jest rejestrem danych
Krok 3: Sprawdź, czy stos jest pełny, czy nie
if (sp = 0) then (full ← 1)
Krok 4: Zaznacz nie jest pusty
pusty ← 0
Operacja wyskakująca w stosie rejestrów
Krok 1: Odczytaj dane ze stosu.
DR←M[SP]
Krok 2: Zmniejsz punkt stosu.
SP ← SP-1
Krok 3: Sprawdź, czy stos jest pusty, czy nie
jeśli sp = 0 to puste ← 1
Organizacja stosu stosu rejestrów 64-bitowych jest pokazana na poniższym rysunku.
Zarejestruj organizację stosu
Stos pamięci
W stosie pamięci głębokość stosu jest elastyczna. Zajmuje dużą ilość danych w pamięci, podczas gdy w stosie rejestrów będzie przechowywana tylko skończona liczba słów pamięci.
Operacja wypychania na stosie pamięci
Krok 1: SP ← SP-1
Krok 2: 1000 [SP] ← CT
Operacja pop na stosie pamięci
Krok 1: DR←M[SP]
Krok 2: SP ← SP-1
W porównaniu z jednostką rejestru, jednostka pamięci przechowuje dużą ilość danych. Rysunek stosu pamięci pokazano na poniższym rysunku.
Stos pamięci
Całkowita jednostka pamięci jest podzielona na trzy części, pierwsza jednostka pamięci zawiera program (tylko instrukcje), druga część to dane (argumenty), a trzecia część to stos. Instrukcje programu są zawsze przechowywane w liczniku programu (PC), rejestry danych są identyfikowane przez rejestr adresowy (AR). Adres od 3000 do 4001 używany dla stosu, a pierwszy element lub element jest przechowywany pod adresem 4001.
Wskaźnik stosu / stosu w mikroprocesorze 8085
Widok programisty 8085 mikroprocesor zawiera rejestry ogólnego przeznaczenia i rejestry specjalnego przeznaczenia . Rejestry ogólnego przeznaczenia to A, B, C, D, E, H, L, a rejestry specjalnego przeznaczenia to SP (wskaźnik stosu) i PC (licznik programu). Widok programatora mikroprocesora 8085 pokazano na poniższym rysunku.
Widok programisty 8085
Wskaźnik stosu jest 16-bitowym rejestrem zawierającym adres pamięci, przypuśćmy, że zawartość wskaźnika stosu (SP) to FC78H, a następnie mikroprocesor 8085 interpretuje go. Lokalizacje pamięci zawierają przydatne informacje od FC78H do FFFH, a od FC77H do 0000H - lokalizacja pamięci nie zawiera przydatnych informacji. Interpretację wskaźnika stosu pokazano na poniższym rysunku.
Interpretacja wskaźnika stosu
Podstawowe operacje wskaźnika stosu / stosu
Istnieją dwie operacje na stosie: operacja PUSH i operacja POP.
Operacja PUSH
PUSH oznacza wpychanie lub wkładanie elementu do stosu. Operacja PUSH zawsze zwiększa wskaźnik stosu, a operacja POP zawsze zmniejsza wskaźnik stosu. W przypadku operacji wypychania musimy sprawdzić, czy jest wolne miejsce, czy nie. Jeśli wolne miejsce jest dostępne, możemy przejść do operacji wypychania, jeśli wolne miejsce nie jest dostępne, pojawia się komunikat o błędzie, czyli przepełnienie. Przelew należy sprawdzić odpowiednio w przypadku naciśnięcia. Na poniższym rysunku przedstawiono podstawowe operacje push i pop.
Podstawowa obsługa funkcji PUSH i POP
Rysunek (a) to stos. Jeśli chcesz wepchnąć element, który jest wstawiający element do stosu, musisz wcisnąć (s, a), gdzie „s” to nic innego jak stos. W stosie umieszczamy element „a” i ta operacja jest pokazana na rysunku (b). Zobacz rysunek (3), załóżmy, że stos zawiera trzy elementy a, b, c, a stos jest wypełniony elementem.
Jeśli chcesz wstawić czwarty element-„d” za pomocą push (s, d), ale nie ma miejsca na wstawienie elementu, oznacza to, że stos jest przepełniony. Terminologia przepełnienia jest używana, gdy stos jest pełny, a algorytm operacji wypychania pokazano poniżej.
push (stack [], top, max stack, item)
if (top == maxstack-1)
{
drukuj „przepełnienie”
}
jeszcze
{
top = top + 1
stos [góra] = przedmiot
}
koniec
Działanie POP
POP oznacza usunięcie elementu na szczycie stosu. W przypadku operacji pop musimy sprawdzić, czy stos jest początkowo pusty, czy nie. Jeśli stos jest początkowo pusty, występuje sytuacja niedomiaru. Załóżmy, że stos jest pusty, nadal chcesz zdjąć elementy ze stosu, ale w stosie nie ma żadnych elementów, co prowadzi do niedopełnienia stosu.
Niedomiar należy sprawdzić odpowiednio w przypadku operacji pop. W operacji wyskakującej, niezależnie od tego, który element górny znajduje się na stosie, powinien zostać usunięty lub usunięty, więc nie trzeba wspominać, który element zostanie usunięty, domyślnie zostanie usunięty najwyższy element. Poniżej przedstawiono algorytm działania pop.
pop (stos [], góra, element)
if (top == - 1)
{
drukuj „niedomiar”
}
jeszcze
{
item = stack [top]
top = top-1
}
Przykład
Elementy są wstawiane w kolejności A, B, C, D, E, reprezentuje stos pięciu elementów. Na rysunku (a) chcemy wepchnąć element „A” na stos, a następnie wierzchołek stanie się zerowy (góra = 0), podobnie góra = 1, gdy element „B” jest wciśnięty, góra = 2, gdy element „C” jest wciśnięty, top = 3, gdy element „D” jest wciśnięty, a top = 4, gdy element „E” jest wciśnięty.
Więc cokolwiek wziąłem elementy, jest umieszczane na stosie, teraz stos jest pełny. Jeśli chcesz przesunąć inny element, nie ma miejsca na stosie, więc wskazuje to na przepełnienie. Teraz stos jest pełny, jeśli chcesz zdjąć element „E”, należy najpierw usunąć element. Operację wypychania pokazano na poniższym rysunku.
Operacja Push
Musimy użyć operacji pop, aby usunąć elementy ze stosu. Więc po prostu wspomnij, że pop () nie zapisuje argumentów w pop, ponieważ domyślnie usuwa górny element. Pierwszy element „E” zostaje usunięty, następny element „D”… .. „A”. Kiedy usuwane są górne elementy, górna wartość maleje. Gdy top = -1, stos wskazuje niedomiar. Operacja pop jest pokazana na poniższym rysunku.
Działanie POP
To jest wyjaśnienie, w jaki sposób elementy są wstawiane i usuwane ze stosu za pomocą operacji push i pop.
Aplikacje
Zastosowania wskaźnika stosu / stosu to
- Odwrócenie strun
- Zrównoważony nawias
- UNDO / FINGER
- Stos systemowy dla rekordów aktywacji
- Infix, prefiks, postfix, wyrażenie
FAQs
1). Co to jest wskaźnik stosu w ramieniu?
Rejestr wskaźnika stosu (R13) używany jako wskaźnik do aktywnego stosu w ARM.
2). Dlaczego wskaźnik stosu jest 16-bitowy?
Wskaźnik stosu (SP) i licznik programu (PC) wykorzystywane do przechowywania poprzedniej lokalizacji i adresu miejsca w pamięci mają 16 bitów, więc wskaźnik stosu (SP) również ma 16 bitów.
3). Jaka jest rola wskaźnika stosu?
Rolą wskaźnika stosu (SP) jest wskazanie górnej części elementu stosu.
4). Który stos jest używany w 8085?
Stos używany w 8085 to Last In First Out (LIFO).
5). Czy wskaźnik stosu jest rejestrem?
Tak, wskaźnik stosu (SP) jest rejestrem adresowym, który zawsze wskazuje górę elementu na stosie.
