logo

Hva er en stabel?

En stabel er en lineær datastruktur som følger LIFO (sist inn-først-ut) prinsipp. Stack har en ende, mens køen har to ender ( fremside og bakside ). Den inneholder bare én peker øverste peker peker mot det øverste elementet i stabelen. Når et element legges til i stabelen, legges det til på toppen av stabelen, og elementet kan bare slettes fra stabelen. Med andre ord, a stabel kan defineres som en beholder der innsetting og sletting kan gjøres fra den ene enden kjent som toppen av stabelen.

Noen nøkkelpunkter knyttet til stack

  • Det kalles som stabel fordi det oppfører seg som en virkelig stabel, hauger med bøker osv.
  • En stabel er en abstrakt datatype med en forhåndsdefinert kapasitet, noe som betyr at den kan lagre elementene med begrenset størrelse.
  • Det er en datastruktur som følger en rekkefølge for å sette inn og slette elementene, og den rekkefølgen kan være LIFO eller FILO.

Arbeid av Stack

Stack fungerer på LIFO-mønsteret. Som vi kan se i figuren nedenfor er det fem minneblokker i stabelen; derfor er størrelsen på stabelen 5.

java-sjekken er null

Anta at vi ønsker å lagre elementene i en stabel og la oss anta at stabelen er tom. Vi har tatt stabelen i størrelse 5 som vist nedenfor, der vi skyver elementene en etter en til stabelen blir full.

DS Stack Introduksjon

Siden stabelen vår er full da størrelsen på stabelen er 5. I de ovennevnte tilfellene kan vi observere at den går fra toppen til bunnen når vi skulle legge inn det nye elementet i stabelen. Stabelen blir fylt opp fra bunnen til toppen.

Når vi utfører sletteoperasjonen på stabelen, er det bare én vei for inn- og utgang da den andre enden er stengt. Den følger LIFO-mønsteret, som betyr at verdien som ble lagt inn først, fjernes sist. I tilfellet ovenfor angis verdien 5 først, så den fjernes først etter sletting av alle de andre elementene.

Standard stabeloperasjoner

Følgende er noen vanlige operasjoner implementert på stabelen:

    trykk():Når vi setter inn et element i en stabel, er operasjonen kjent som en push. Hvis stabelen er full, oppstår overløpstilstanden.pop():Når vi sletter et element fra stabelen, er operasjonen kjent som en pop. Hvis stabelen er tom betyr det at det ikke finnes noe element i stabelen, er denne tilstanden kjent som en underflyttilstand.er tom():Det avgjør om stabelen er tom eller ikke.er full():Det avgjør om stabelen er full eller ikke.'kikk():Det returnerer elementet på den gitte posisjonen.telle():Den returnerer det totale antallet elementer som er tilgjengelig i en stabel.endring():Det endrer elementet på den gitte posisjonen.vise():Den skriver ut alle elementene som er tilgjengelige i stabelen.

PUSH-operasjon

Trinnene involvert i PUSH-operasjonen er gitt nedenfor:

  • Før vi legger inn et element i en stabel, sjekker vi om stabelen er full.
  • Hvis vi prøver å sette inn elementet i en stabel, og stabelen er full, så flyte tilstand oppstår.
  • Når vi initialiserer en stabel, setter vi verdien av topp til -1 for å sjekke at stabelen er tom.
  • Når det nye elementet skyves i en stabel, økes først verdien av toppen, dvs. topp=topp+1, og elementet vil bli plassert i den nye posisjonen til topp .
  • Elementene vil bli satt inn til vi når maks størrelsen på stabelen.
DS Stack Introduksjon

POP-operasjon

Trinnene som er involvert i POP-operasjonen er gitt nedenfor:

amplitudemodulasjon
  • Før vi sletter elementet fra stabelen, sjekker vi om stabelen er tom.
  • Hvis vi prøver å slette elementet fra den tomme stabelen, så underflyt tilstand oppstår.
  • Hvis stabelen ikke er tom, får vi først tilgang til elementet som er pekt av topp
  • Når popoperasjonen er utført, reduseres toppen med 1, dvs. topp=topp-1 .
DS Stack Introduksjon

Applikasjoner av Stack

Følgende er applikasjonene til stabelen:

    Balansering av symboler:Stabel brukes til å balansere et symbol. For eksempel har vi følgende program:
 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';>
Minnehåndtering:Stabelen styrer minnet. Minnet er tilordnet i de sammenhengende minneblokkene. Minnet er kjent som stabelminne ettersom alle variablene er tilordnet i et stabelminne for funksjonskall. Minnestørrelsen som er tildelt programmet er kjent for kompilatoren. Når funksjonen er opprettet, blir alle variablene tilordnet i stabelminnet. Når funksjonen fullførte utførelsen, frigjøres alle variablene som er tildelt i stabelen.