En stack är en linjär datastruktur som följer LIFO (Last-In-First-Out) princip. Stacken har en ände, medan kön har två ändar ( fram och bak ). Den innehåller bara en pekare topppekare pekar på det översta elementet i stapeln. Närhelst ett element läggs till i stacken läggs det till på toppen av stacken, och elementet kan bara tas bort från stacken. Med andra ord, a stack kan definieras som en behållare i vilken insättning och radering kan göras från den ena änden som kallas toppen av stapeln.
Några nyckelpunkter relaterade till stack
- Det kallas som stack eftersom det beter sig som en verklig stack, högar med böcker, etc.
- En stack är en abstrakt datatyp med en fördefinierad kapacitet, vilket innebär att den kan lagra element av en begränsad storlek.
- Det är en datastruktur som följer någon ordning för att infoga och ta bort elementen, och den ordningen kan vara LIFO eller FILO.
Arbete av Stack
Stack fungerar på LIFO-mönstret. Som vi kan se i figuren nedan finns det fem minnesblock i stacken; därför är stackens storlek 5.
j-knappen
Anta att vi vill lagra elementen i en stack och låt oss anta att stack är tom. Vi har tagit högen av storlek 5 som visas nedan där vi trycker på elementen ett efter ett tills stapeln blir full.
Eftersom vår stack är full då storleken på stacken är 5. I ovanstående fall kan vi observera att den går från toppen till botten när vi skulle gå in i det nya elementet i stacken. Högen fylls upp från botten till toppen.
När vi utför raderingsoperationen på stacken finns det bara ett sätt att gå in och ut eftersom den andra änden är stängd. Den följer LIFO-mönstret, vilket innebär att det först angivna värdet tas bort sist. I ovanstående fall skrivs värdet 5 in först, så det kommer att tas bort först efter raderingen av alla andra element.
Standard stackoperationer
Följande är några vanliga operationer som implementeras på stacken:
PUSH-operation
Stegen som är involverade i PUSH-operationen ges nedan:
- Innan vi lägger in ett element i en stack kontrollerar vi om stapeln är full.
- Om vi försöker infoga elementet i en stack och stacken är full, då svämma över tillstånd uppstår.
- När vi initierar en stack sätter vi värdet på top som -1 för att kontrollera att stacken är tom.
- När det nya elementet skjuts in i en stack, ökar först värdet på toppen, dvs. top=top+1, och elementet kommer att placeras på den nya positionen för topp .
- Elementen kommer att infogas tills vi når max stapelns storlek.
POP-operation
Stegen som är involverade i POP-operationen ges nedan:
vad är myspace
- Innan vi tar bort elementet från stacken kontrollerar vi om stacken är tom.
- Om vi försöker ta bort elementet från den tomma stacken, då underflöde tillstånd uppstår.
- Om stacken inte är tom kommer vi först åt elementet som pekas av topp
- När popoperationen väl har utförts minskas toppen med 1, dvs. topp=topp-1 .
Tillämpningar av Stack
Följande är applikationerna för stacken:
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';>