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.
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:
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.
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 .
Anwendungen von Stack
Im Folgenden sind die Anwendungen des Stapels aufgeführt:
int main() { cout<<'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 ' <strong>javaTpoint</strong> ' 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 'a', then 'b', and then 'c'; 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 'ab' 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';>
'hello';>