Zásobník je lineárna dátová štruktúra, ktorá nasleduje LIFO (Last-In-First-Out) princíp. Zásobník má jeden koniec, zatiaľ čo front má dva konce ( predné a zadné ). Obsahuje iba jeden ukazovateľ horný ukazovateľ ukazujúce na najvrchnejší prvok zásobníka. Vždy, keď sa prvok pridá do zásobníka, pridá sa na vrch zásobníka a prvok možno odstrániť iba zo zásobníka. Inými slovami, a stoh možno definovať ako kontajner, do ktorého je možné vkladať a vymazávať z jedného konca známeho ako vrch stohu.
Niektoré kľúčové body týkajúce sa zásobníka
- Nazýva sa zásobník, pretože sa správa ako zásobník v skutočnom svete, hromady kníh atď.
- Zásobník je abstraktný dátový typ s vopred definovanou kapacitou, čo znamená, že môže ukladať prvky obmedzenej veľkosti.
- Ide o dátovú štruktúru, ktorá sleduje určité poradie pri vkladaní a odstraňovaní prvkov, pričom toto poradie môže byť LIFO alebo FILO.
Fungovanie zásobníka
Stack funguje na vzore LIFO. Ako môžeme vidieť na obrázku nižšie, v zásobníku je päť pamäťových blokov; preto je veľkosť zásobníka 5.
koľko filmov s nemožnými úlohami existuje
Predpokladajme, že chceme uložiť prvky do zásobníka a predpokladajme, že zásobník je prázdny. Zobrali sme stoh veľkosti 5, ako je znázornené nižšie, v ktorom posúvame prvky jeden po druhom, kým sa stoh nezaplní.
Keďže náš zásobník je plný, pretože veľkosť zásobníka je 5. Vo vyššie uvedených prípadoch môžeme pozorovať, že prechádza zhora nadol, keď sme zadávali nový prvok v zásobníku. Zásobník sa naplní zdola nahor.
Keď vykonáme operáciu odstránenia na zásobníku, existuje len jeden spôsob vstupu a výstupu, pretože druhý koniec je zatvorený. Riadi sa vzorom LIFO, čo znamená, že hodnota zadaná ako prvá bude odstránená ako posledná. Vo vyššie uvedenom prípade sa najskôr zadá hodnota 5, takže sa odstráni až po vymazaní všetkých ostatných prvkov.
Štandardné operácie so zásobníkom
Nasledujú niektoré bežné operácie implementované v zásobníku:
Operácia PUSH
Kroky zapojené do operácie PUSH sú uvedené nižšie:
- Pred vložením prvku do zásobníka skontrolujeme, či je zásobník plný.
- Ak sa pokúsime vložiť prvok do zásobníka a zásobník je plný, potom pretečeniu nastane stav.
- Keď inicializujeme zásobník, nastavíme hodnotu top ako -1, aby sme skontrolovali, či je zásobník prázdny.
- Keď je nový prvok vložený do zásobníka, najprv sa zvýši hodnota vrcholu, t.j. top=top+1, a prvok sa umiestni na novú pozíciu top .
- Prvky budú vložené, kým nedosiahneme max veľkosť zásobníka.
Operácia POP
Kroky súvisiace s operáciou POP sú uvedené nižšie:
javascriptové operátory
- Pred odstránením prvku zo zásobníka skontrolujeme, či je zásobník prázdny.
- Ak sa pokúsime odstrániť prvok z prázdneho zásobníka, potom podtekanie nastane stav.
- Ak zásobník nie je prázdny, najskôr pristúpime k prvku, na ktorý ukazuje top
- Po vykonaní operácie pop sa vrchol zníži o 1, t.j. top=top-1 .
Aplikácie Stack
Nasledujú aplikácie zásobníka:
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';>