Der Stapel ist nichts anderes als die lineare Datenstruktur, in der das Einfügen und Löschen nur an einem Ende erfolgt. Die Einfügeoperation hat einen speziellen Namen, der als PUSH bekannt ist, und die Löschoperation hat auch einen speziellen Namen, der als POP bekannt ist. PUSH und POP sind zwei grundlegende Operationen, die nur in einem bestimmten Stapel ausgeführt werden können. Es ist eine Gruppe von Speicherstellen, und die Speicherstellen beziehen sich entweder auf den Lesespeicher oder den Schreibspeicher. Dies wird zum Speichern von Binärinformationen während der Ausführung des Programms verwendet. Wenn wir ein Programm ausführen, wird der Inhalt dieses Programms im Stapel gespeichert. Es folgt Zuletzt rein, zuerst raus (LIFO) und wird nur zum Speichern und Abrufen der Daten verwendet, nicht jedoch zum Speichern der Daten. Die kurze Erklärung des Stapels / Stapelzeigers wird unten diskutiert.
Was ist Stack / Stack Pointer?
Definition: Der Stapel ist ein Speichergerät, das zum Speichern von Informationen oder Daten in einer Art LIFO (Last In First Out) verwendet wird. Immer wenn wir die Daten in Form von LIFO eingeben, ist das Element, das zuerst gelöscht werden muss, das letzte Einfügeelement, sodass das zuletzt eingefügte Element zuerst herausgenommen wird. Es ist die Speichereinheit in einem Adressregister, das als Stapelzeiger (SP) bezeichnet wird. Der Stapelzeiger zeigt immer das oberste Element im Stapel an, dh an welcher Stelle die Daten eingefügt werden müssen.
Arten von Stapeln
Es gibt zwei Arten von Stapeln: Registerstapel und Speicherstapel.
Stapel registrieren
Der Registerstapel ist ebenfalls eine in der Speichereinheit vorhandene Speichervorrichtung, verarbeitet jedoch nur eine kleine Datenmenge. Die Stapeltiefe ist im Registerstapel immer begrenzt, da die Größe des Registerstapels im Vergleich zum Speicher sehr klein ist.
Push-Operation im Registerstapel
Schritt 1: Der Stapelzeiger wird um 1 erhöht.
SP ← SP + 1
Schritt 2: Geben Sie die Daten in den Stapel ein.
1000 [SP] ← CT
Wobei DR das Datenregister ist
Schritt 3: Überprüfen Sie, ob der Stapel voll ist oder nicht
wenn (sp = 0) dann (voll ← 1)
Schritt 4: Markiere nicht leer
leer ← 0
Pop-Operation im Register-Stapel
Schritt 1: Lesen Sie Daten vom Stapel.
DR ← M [SP]
Schritt 2: Stapelpunkt verringern.
SP ← SP-1
Schritt 3: Überprüfen Sie, ob der Stapel leer ist oder nicht
wenn sp = 0, dann leer ← 1
Die Stapelorganisation des 64-Bit-Registerstapels ist in der folgenden Abbildung dargestellt.
Register Stack Organization
Speicherstapel
Im Speicherstapel ist die Stapeltiefe flexibel. Es belegt eine große Menge an Speicherdaten, während im Registerstapel nur eine begrenzte Anzahl von Speicherwörtern gespeichert wird.
Push-Betrieb im Speicherstapel
Schritt 1: SP ← SP-1
Schritt 2: 1000 [SP] ← CT
Pop-Operation im Memory Stack
Schritt 1: DR ← M [SP]
Schritt 2: SP ← SP-1
Im Vergleich zur Registereinheit speichert die Speichereinheit eine große Datenmenge. Die Abbildung des Speicherstapels ist in der folgenden Abbildung dargestellt.
Speicherstapel
Die gesamte Speichereinheit ist in drei Teile unterteilt, die erste Speichereinheit hat das Programm (nichts als Anweisungen), der zweite Teil sind Daten (Operanden) und der dritte Teil ist Stapel. Die Programmanweisungen werden immer im Programmzähler (PC) gespeichert, die Datenregister werden durch das Adressregister (AR) identifiziert. Die für den Stapel und das erste Element oder Element verwendete Adresse 3000 bis 4001 wird bei 4001 gespeichert.
Stapel- / Stapelzeiger im 8085-Mikroprozessor
Die Programmiereransicht von 8085 Mikroprozessor enthält Allzweckregister und Sonderregister . Die Universalregister sind A, B, C, D, E, H, L, und die Spezialregister sind SP (Stapelzeiger) und PC (Programmzähler). Die Programmiereransicht des 8085-Mikroprozessors ist in der folgenden Abbildung dargestellt.
Programmiereransicht von 8085
Der Stapelzeiger ist ein 16-Bit-Register, das eine Speicheradresse enthält. Angenommen, der Inhalt des Stapelzeigers (SP) ist FC78H, dann interpretiert der Mikroprozessor 8085 diese. Die Speicherorte enthalten nützliche Informationen von FC78H bis FFFH und von FC77H bis 0000H enthält der Speicherort keine nützlichen Informationen. Die Interpretation des Stapelzeigers ist in der folgenden Abbildung dargestellt.
Interpretation des Stapelzeigers
Grundfunktionen von Stack / Stack Pointer
Es gibt zwei Operationen des Stapels: PUSH-Operation und POP-Operation.
PUSH-Betrieb
Der PUSH bedeutet, ein Element in den Stapel zu schieben oder einzufügen. Die PUSH-Operation erhöht immer den Stapelzeiger und die POP-Operation verringert immer den Stapelzeiger. Im Falle einer Push-Operation müssen wir prüfen, ob ein freier Speicherplatz verfügbar ist oder nicht. Wenn freier Speicherplatz verfügbar ist, können wir zum Push-Vorgang wechseln. Wenn kein freier Speicherplatz verfügbar ist, tritt eine Fehlermeldung auf, die überläuft. Der Überlauf ist bei Druckbetrieb jeweils zu prüfen. Die grundlegende Funktionsweise von Push und Pop ist in der folgenden Abbildung dargestellt.
Grundlegende Bedienung von PUSH und POP
Abbildung (a) ist der Stapel. Wenn Sie das Element verschieben möchten, bei dem das Element in den Stapel eingefügt wird, müssen Sie (s, a) drücken, wobei 's' nichts anderes als ein Stapel ist. Im Stapel platzieren wir das 'a'-Element und diese Operation ist in Abbildung (b) dargestellt. In der Abbildung (3) wird angenommen, dass der Stapel drei Elemente a, b, c enthält und der Stapel mit einem Element gefüllt ist.
Wenn Sie ein viertes Element -d mit push (s, d) einfügen möchten, aber kein Platz zum Einfügen des Elements verfügbar ist, zeigt dies an, dass der Stapel übergelaufen ist. Die Überlaufterminologie wird verwendet, wenn der Stapel voll ist und der Algorithmus der Push-Operation unten gezeigt wird.
push (Stapel [], oben, maximaler Stapel, Gegenstand)
if (top == maxstack-1)
{
'Überlauf' drucken
}}
sonst
{
top = top + 1
Stapel [oben] = Gegenstand
}}
Ende
POP-Betrieb
Der POP bedeutet das Löschen des Elements oben im Stapel. Im Falle einer Pop-Operation müssen wir prüfen, ob der Stapel anfangs leer ist oder nicht. Wenn der Stapel anfänglich leer ist, tritt eine Unterlaufsituation auf. Angenommen, der Stapel ist noch leer. Sie möchten die Elemente in den Stapel einfügen, aber es befinden sich keine Elemente im Stapel. Dies führt zu einem Stapelunterlauf.
Der Unterlauf ist bei Pop-Betrieb jeweils zu prüfen. Bei der Pop-Operation wird unabhängig davon, welches oberste Element im Stapel vorhanden ist, das gepoppt oder gelöscht werden soll, nicht erwähnt, welches Element gepoppt wird. Standardmäßig wird das oberste Element gepoppt. Der Algorithmus der Pop-Operation ist unten gezeigt.
Pop (Stapel [], oben, Element)
if (top == - 1)
{
'Unterlauf' drucken
}}
sonst
{
item = stack [top]
top = top-1
}}
Beispiel
Die Elemente werden in der Reihenfolge A, B, C, D, E eingefügt. Sie repräsentieren den Stapel von fünf Elementen. In Abbildung (a) möchten wir das Element 'A' auf dem Stapel verschieben, dann wird die Oberseite Null (oben = 0), ähnlich wie die Oberseite = 1, wenn das Element 'B' gedrückt wird, und die Spitze = 2, wenn das Element 'C' wird gedrückt, top = 3, wenn das 'D'-Element gedrückt wird, und top = 4, wenn das' E'-Element gedrückt wird.
Was auch immer die Elemente, die ich genommen habe, in den Stapel gelegt werden, jetzt ist der Stapel voll. Wenn Sie ein anderes Element verschieben möchten, befindet sich kein Platz im Stapel, sodass der Überlauf angezeigt wird. Jetzt ist der Stapel voll, wenn Sie das Element 'E' einfügen möchten. Zuerst muss das Element gelöscht werden. Die Push-Operation ist in der folgenden Abbildung dargestellt.
Push-Betrieb
Wir müssen die Pop-Operation verwenden, um die Elemente im Stapel zu löschen. Erwähnen Sie also einfach, dass pop () keine Argumente in das Pop schreibt, da es standardmäßig das oberste Element löscht. Das erste 'E' -Element wird als nächstes 'D' -Element gelöscht ... 'A'. Wenn die oberen Elemente gelöscht werden, verringert sich der obere Wert. Wenn top = -1 ist, zeigt der Stapel einen Unterlauf an. Die Pop-Operation ist in der folgenden Abbildung dargestellt.
POP-Betrieb
Dies ist also die Erklärung, wie die Elemente mithilfe der Push- und Pop-Operation in den Stapel eingefügt und daraus gelöscht werden.
Anwendungen
Die Anwendungen des Stapels / Stapelzeigers sind
- Stringumkehr
- Ausgewogene Klammer
- UNDO / FINGER
- Systemstapel für Aktivierungsdatensätze
- Infix, Präfix, Postfix, Ausdruck
FAQs
1). Was ist der Stapelzeiger im Arm?
Das Stapelzeigerregister (R13), das als Zeiger auf den aktiven Stapel in ARM verwendet wird.
2). Warum ist der Stapelzeiger 16 Bit?
Der Stapelzeiger (SP) und der Programmzähler (PC), die zum Speichern des vorherigen Speicherorts und der Speicherortadresse verwendet werden, betragen 16 Bit, so dass der Stapelzeiger (SP) ebenfalls 16 Bit beträgt.
3). Welche Rolle spielt der Stapelzeiger?
Die Rolle des Stapelzeigers (SP) besteht darin, die Oberseite des Elements im Stapel anzuzeigen.
4). Welcher Stack wird in 8085 verwendet?
Der in 8085 verwendete Stapel ist Last In First Out (LIFO).
5). Ist der Stapelzeiger ein Register?
Ja, der Stapelzeiger (SP) ist ein Adressregister, das immer die Oberseite des Elements im Stapel anzeigt.
