Uno Stack è una struttura di dati lineare che segue il LIFO (Last-In-First-Out) principio. Lo stack ha un'estremità, mentre la coda ha due estremità ( fronte retro ). Contiene un solo puntatore puntatore superiore puntando all'elemento più in alto dello stack. Ogni volta che un elemento viene aggiunto allo stack, viene aggiunto in cima allo stack e l'elemento può essere eliminato solo dallo stack. In altre parole, a lo stack può essere definito come un contenitore in cui l'inserimento e l'eliminazione possono essere effettuati da un'estremità nota come parte superiore dello stack.
Alcuni punti chiave relativi allo stack
- Si chiama stack perché si comporta come una pila del mondo reale, pile di libri, ecc.
- Uno Stack è un tipo di dati astratto con una capacità predefinita, il che significa che può memorizzare elementi di dimensione limitata.
- È una struttura dati che segue un ordine per inserire ed eliminare gli elementi e tale ordine può essere LIFO o FILO.
Funzionamento dello Stack
Lo stack funziona secondo il modello LIFO. Come possiamo osservare nella figura seguente ci sono cinque blocchi di memoria nello stack; pertanto, la dimensione dello stack è 5.
elenco degli stati
Supponiamo di voler memorizzare gli elementi in uno stack e supponiamo che lo stack sia vuoto. Abbiamo preso la pila di dimensione 5 come mostrato di seguito in cui spingiamo gli elementi uno per uno finché la pila non diventa piena.
Poiché il nostro stack è pieno poiché la dimensione dello stack è 5. Nei casi precedenti, possiamo osservare che va dall'alto verso il basso quando stiamo inserendo il nuovo elemento nello stack. La pila viene riempita dal basso verso l'alto.
Quando eseguiamo l'operazione di eliminazione sullo stack, esiste un solo modo per entrare e uscire poiché l'altra estremità è chiusa. Segue il modello LIFO, il che significa che il valore immesso per primo verrà rimosso per ultimo. Nel caso precedente viene inserito per primo il valore 5, quindi verrà rimosso solo dopo la cancellazione di tutti gli altri elementi.
Operazioni sullo stack standard
Di seguito sono riportate alcune operazioni comuni implementate sullo stack:
enumerazioni Java
Funzionamento a SPINTA
Di seguito sono riportati i passaggi coinvolti nell'operazione PUSH:
- Prima di inserire un elemento in uno stack, controlliamo se lo stack è pieno.
- Se proviamo a inserire l'elemento in uno stack e lo stack è pieno, allora il traboccamento si verifica la condizione.
- Quando inizializziamo uno stack, impostiamo il valore di top come -1 per verificare che lo stack sia vuoto.
- Quando il nuovo elemento viene inserito in uno stack, innanzitutto il valore del top viene incrementato, ovvero sopra=sopra+1, e l'elemento verrà posizionato nella nuova posizione di superiore .
- Gli elementi verranno inseriti fino a raggiungere il file massimo dimensione della pila.
Operazione POP
Di seguito sono riportati i passaggi coinvolti nell'operazione POP:
- Prima di eliminare l'elemento dallo stack, controlliamo se lo stack è vuoto.
- Se proviamo a eliminare l'elemento dallo stack vuoto, allora il file sottoflusso si verifica la condizione.
- Se lo stack non è vuoto, accediamo prima all'elemento puntato da superiore
- Una volta eseguita l'operazione pop, la parte superiore viene decrementata di 1, ovvero in alto=in alto-1 .
Applicazioni dello Stack
Di seguito sono riportate le applicazioni dello stack:
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';>