logo

Cos'è una pila?

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.

Introduzione allo stack DS

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
    spingere():Quando inseriamo un elemento in uno stack, l'operazione è nota come push. Se lo stack è pieno si verifica la condizione di overflow.pop():Quando eliminiamo un elemento dallo stack, l'operazione è nota come pop. Se lo stack è vuoto significa che non esiste alcun elemento nello stack, questo stato è noto come stato di underflow.è vuoto():Determina se lo stack è vuoto o meno.è pieno():Determina se lo stack è pieno o meno.'sbirciare():Restituisce l'elemento nella posizione data.contare():Restituisce il numero totale di elementi disponibili in uno stack.modifica():Cambia l'elemento nella posizione data.Schermo():Stampa tutti gli elementi disponibili nello stack.

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.
Introduzione allo stack DS

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 .
Introduzione allo stack DS

Applicazioni dello Stack

Di seguito sono riportate le applicazioni dello stack:

    Bilanciamento dei simboli:Lo stack viene utilizzato per bilanciare un simbolo. Ad esempio, abbiamo il seguente programma:
 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';>
Gestione della memoria:Lo stack gestisce la memoria. La memoria viene occupata nei blocchi di memoria contigui. La memoria è nota come memoria stack poiché tutte le variabili sono assegnate in una memoria stack di chiamate di funzione. La dimensione della memoria assegnata al programma è nota al compilatore. Quando viene creata la funzione, tutte le sue variabili vengono assegnate nella memoria dello stack. Una volta completata l'esecuzione della funzione, tutte le variabili assegnate nello stack vengono rilasciate.