Stack yra linijinė duomenų struktūra, kuri seka LIFO (paskutinis pirmas išėjimas) principu. Stack turi vieną galą, o eilė turi du galus ( priekyje ir gale ). Jame yra tik viena rodyklė viršutinė rodyklė nukreipia į aukščiausią krūvos elementą. Kai elementas pridedamas prie krūvos, jis pridedamas krūvos viršuje, o elementą galima ištrinti tik iš krūvos. Kitaip tariant, a steką galima apibrėžti kaip konteinerį, į kurį galima įterpti ir ištrinti iš vieno galo, žinomo kaip krūvos viršus.
Kai kurie pagrindiniai dalykai, susiję su kaminu
- Jis vadinamas krūva, nes elgiasi kaip tikras krūvas, knygų krūvos ir pan.
- Stack yra abstraktus duomenų tipas, turintis iš anksto nustatytą talpą, o tai reiškia, kad jis gali saugoti riboto dydžio elementus.
- Tai duomenų struktūra, kuri vadovaujasi tam tikra tvarka įterpti ir ištrinti elementus, ir ta tvarka gali būti LIFO arba FILO.
Stacko darbas
Stack darbai pagal LIFO modelį. Kaip matome toliau pateiktame paveikslėlyje, krūvoje yra penki atminties blokai; todėl krūvos dydis yra 5.
javascript eilutės apkarpymas
Tarkime, kad norime saugoti elementus krūvoje ir tarkime, kad krūva tuščia. Mes paėmėme 5 dydžio krūvą, kaip parodyta žemiau, kurioje elementus stumiame po vieną, kol krūva prisipildys.
Kadangi mūsų krūva pilna, nes krūvos dydis yra 5. Aukščiau nurodytais atvejais galime pastebėti, kad jis eina iš viršaus į apačią, kai įvedėme naują elementą į krūvą. Kaminas užpildomas iš apačios į viršų.
Kai atliekame kamino trynimo operaciją, yra tik vienas įėjimo ir išėjimo būdas, nes kitas galas yra uždarytas. Ji atitinka LIFO šabloną, o tai reiškia, kad pirmiausia įvesta reikšmė bus pašalinta paskutinė. Pirmiau nurodytu atveju pirmiausia įvedama reikšmė 5, todėl ji bus pašalinta tik ištrynus visus kitus elementus.
Standartinės krūvos operacijos
Toliau pateikiamos kelios įprastos kamino operacijos:
vienvietis dizainas
PUSH veikimas
Toliau pateikiami PUSH operacijos veiksmai:
- Prieš įterpdami elementą į krūvą, patikriname, ar krūva pilna.
- Jei bandome įterpti elementą į krūvą, o krūva yra pilna, tada perpildymas atsiranda sąlyga.
- Kai inicijuojame krūvą, viršutinę reikšmę nustatome kaip -1, kad patikrintume, ar krūva tuščia.
- Kai naujas elementas įstumiamas į krūvą, pirmiausia padidėja viršutinės dalies reikšmė, t.y. top=top+1, ir elementas bus dedamas į naują vietą viršuje .
- Elementai bus įterpti tol, kol pasieksime maks kamino dydis.
POP operacija
Toliau pateikiami POP operacijos veiksmai:
- Prieš ištrindami elementą iš krūvos, patikriname, ar krūva tuščia.
- Jei bandysime ištrinti elementą iš tuščio krūvos, tada perteklius atsiranda sąlyga.
- Jei krūva nėra tuščia, pirmiausia pasiekiame elementą, kurį nurodo viršuje
- Atlikus iššokimo operaciją, viršutinė dalis sumažinama 1, t.y. viršus = viršus-1 .
Stack programos
Toliau pateikiamos kamino programos:
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';>