logo

Was ist ein Stapel?

Ein Stack ist eine lineare Datenstruktur, die dem folgt LIFO (Last-In-First-Out) Prinzip. Der Stapel hat ein Ende, während die Warteschlange zwei Enden hat ( Vorderseite und Rückseite ). Es enthält nur einen Zeiger oberer Zeiger zeigt auf das oberste Element des Stapels. Immer wenn ein Element zum Stapel hinzugefügt wird, wird es oben auf dem Stapel hinzugefügt und das Element kann nur aus dem Stapel gelöscht werden. Mit anderen Worten, a Ein Stapel kann als ein Container definiert werden, in den das Einfügen und Löschen von einem Ende aus erfolgen kann, das als Oberseite des Stapels bezeichnet wird.

Einige wichtige Punkte im Zusammenhang mit dem Stapel

  • Er wird als Stapel bezeichnet, weil er sich wie ein realer Stapel, Bücherstapel usw. verhält.
  • Ein Stack ist ein abstrakter Datentyp mit einer vordefinierten Kapazität, was bedeutet, dass er Elemente einer begrenzten Größe speichern kann.
  • Es handelt sich um eine Datenstruktur, die einer bestimmten Reihenfolge zum Einfügen und Löschen der Elemente folgt. Diese Reihenfolge kann LIFO oder FILO sein.

Funktionsweise des Stapels

Stack arbeitet nach dem LIFO-Muster. Wie wir in der folgenden Abbildung sehen können, befinden sich fünf Speicherblöcke im Stapel. Daher beträgt die Größe des Stapels 5.

Konvertieren Sie einen String in ein JSON-Objekt

Angenommen, wir möchten die Elemente in einem Stapel speichern und gehen davon aus, dass der Stapel leer ist. Wir haben den Stapel der Größe 5 genommen, wie unten gezeigt, in dem wir die Elemente nacheinander schieben, bis der Stapel voll ist.

Einführung in den DS-Stack

Da unser Stapel voll ist, beträgt die Größe des Stapels 5. In den oben genannten Fällen können wir beobachten, dass er von oben nach unten verläuft, wenn wir das neue Element in den Stapel eingegeben haben. Der Stapel wird von unten nach oben aufgefüllt.

Wenn wir den Löschvorgang für den Stapel ausführen, gibt es nur eine Möglichkeit zum Ein- und Aussteigen, da das andere Ende geschlossen ist. Es folgt dem LIFO-Muster, was bedeutet, dass der zuerst eingegebene Wert zuletzt entfernt wird. Im obigen Fall wird zuerst der Wert 5 eingegeben, sodass er erst nach dem Löschen aller anderen Elemente entfernt wird.

Standard-Stack-Operationen

Im Folgenden sind einige häufig auf dem Stapel implementierte Vorgänge aufgeführt:

    drücken():Wenn wir ein Element in einen Stapel einfügen, wird der Vorgang als Push bezeichnet. Wenn der Stapel voll ist, tritt die Überlaufbedingung auf.Pop():Wenn wir ein Element aus dem Stapel löschen, wird der Vorgang als Pop bezeichnet. Wenn der Stapel leer ist, bedeutet dies, dass kein Element im Stapel vorhanden ist. Dieser Zustand wird als Unterlaufzustand bezeichnet.ist leer():Es bestimmt, ob der Stapel leer ist oder nicht.ist voll():Es bestimmt, ob der Stapel voll ist oder nicht.'spähen():Es gibt das Element an der angegebenen Position zurück.zählen():Es gibt die Gesamtzahl der in einem Stapel verfügbaren Elemente zurück.ändern():Es ändert das Element an der angegebenen Position.Anzeige():Es werden alle im Stapel verfügbaren Elemente gedruckt.

PUSH-Betrieb

Nachfolgend sind die Schritte des PUSH-Vorgangs aufgeführt:

foreach-Schleifen-Typoskript
  • Bevor wir ein Element in einen Stapel einfügen, prüfen wir, ob der Stapel voll ist.
  • Wenn wir versuchen, das Element in einen Stapel einzufügen, und der Stapel voll ist, dann Überlauf Zustand auftritt.
  • Wenn wir einen Stapel initialisieren, setzen wir den Wert von top auf -1, um zu überprüfen, ob der Stapel leer ist.
  • Wenn das neue Element in einen Stapel verschoben wird, wird zunächst der Wert oben erhöht, d. h. oben=oben+1, und das Element wird an der neuen Position des platziert Spitze .
  • Die Elemente werden eingefügt, bis wir das erreichen max Größe des Stapels.
Einführung in den DS-Stack

POP-Betrieb

Die Schritte des POP-Vorgangs sind unten aufgeführt:

  • Bevor wir das Element vom Stapel löschen, prüfen wir, ob der Stapel leer ist.
  • Wenn wir versuchen, das Element aus dem leeren Stapel zu löschen, dann wird das Unterlauf Zustand auftritt.
  • Wenn der Stapel nicht leer ist, greifen wir zuerst auf das Element zu, auf das der zeigt Spitze
  • Sobald die Pop-Operation ausgeführt wird, wird die Spitze um 1 dekrementiert, d. h. top=top-1 .
Einführung in den DS-Stack

Anwendungen von Stack

Im Folgenden sind die Anwendungen des Stapels aufgeführt:

    Ausbalancieren von Symbolen:Der Stapel wird zum Ausbalancieren eines Symbols verwendet. Wir haben zum Beispiel folgendes Programm:
 int main() { cout&lt;<'hello'; cout<<'javatpoint'; } < pre> <p>As we know, each program has <em>an opening</em> and <em>closing</em> braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.</p> <ul> <tr><td>String reversal:</td> Stack is also used for reversing a string. For example, we want to reverse a &apos; <strong>javaTpoint</strong> &apos; string, so we can achieve this with the help of a stack. <br> First, we push all the characters of the string in a stack until we reach the null character. <br> After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack. </tr><tr><td>UNDO/REDO:</td> It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write &apos;a&apos;, then &apos;b&apos;, and then &apos;c&apos;; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state. <br> If we want to perform UNDO operation, and want to achieve &apos;ab&apos; state, then we implement pop operation. </tr><tr><td>Recursion:</td> The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained. </tr><tr><td>DFS(Depth First Search):</td> This search is implemented on a Graph, and Graph uses the stack data structure. </tr><tr><td>Backtracking:</td> Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure. </tr><tr><td>Expression conversion:</td> Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below: <pre>Infix to prefix Infix to postfix Prefix to infix Prefix to postfix Postfix to infix</pre> </tr><tr><td>Memory management:</td> The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completed its execution, all the variables assigned in the stack are released. </tr></ul> <hr></'hello';>
Speicherverwaltung:Der Stack verwaltet den Speicher. Der Speicher wird in den zusammenhängenden Speicherblöcken zugewiesen. Der Speicher wird als Stapelspeicher bezeichnet, da alle Variablen in einem Funktionsaufruf-Stackspeicher zugewiesen werden. Die dem Programm zugewiesene Speichergröße ist dem Compiler bekannt. Beim Erstellen der Funktion werden alle ihre Variablen im Stapelspeicher zugewiesen. Wenn die Funktion ihre Ausführung abgeschlossen hat, werden alle im Stapel zugewiesenen Variablen freigegeben.