Una pila és una estructura de dades lineal que segueix el LIFO (últim en entrar, primer en sortir) principi. La pila té un extrem, mentre que la cua té dos extrems ( davant i darrere ). Conté només un punter punter superior apuntant a l'element superior de la pila. Sempre que s'afegeix un element a la pila, s'afegeix a la part superior de la pila i l'element només es pot suprimir de la pila. En altres paraules, a La pila es pot definir com un contenidor en què la inserció i la supressió es poden fer des d'un extrem conegut com a la part superior de la pila.
Alguns punts clau relacionats amb la pila
- S'anomena pila perquè es comporta com una pila del món real, piles de llibres, etc.
- Una pila és un tipus de dades abstracte amb una capacitat predefinida, el que significa que pot emmagatzemar els elements d'una mida limitada.
- És una estructura de dades que segueix algun ordre per inserir i eliminar els elements, i aquest ordre pot ser LIFO o FILO.
Funcionament de Stack
Stack funciona amb el patró LIFO. Com podem observar a la figura següent hi ha cinc blocs de memòria a la pila; per tant, la mida de la pila és 5.
comanda sed
Suposem que volem emmagatzemar els elements en una pila i suposem que la pila està buida. Hem agafat la pila de mida 5 com es mostra a continuació, en la qual anem empenyent els elements un per un fins que la pila s'ompli.
Com que la nostra pila està plena ja que la mida de la pila és de 5. En els casos anteriors, podem observar que va de dalt a baix quan estàvem introduint el nou element a la pila. La pila s'omple de baix a dalt.
Quan realitzem l'operació d'eliminació a la pila, només hi ha una manera d'entrada i sortida, ja que l'altre extrem està tancat. Segueix el patró LIFO, el que significa que el valor introduït primer s'eliminarà l'últim. En el cas anterior, primer s'introdueix el valor 5, de manera que només s'eliminarà després de la supressió de tots els altres elements.
Operacions de pila estàndard
A continuació es mostren algunes operacions habituals implementades a la pila:
101 milions
Operació PUSH
Els passos implicats en l'operació PUSH es detallen a continuació:
- Abans d'inserir un element en una pila, comprovem si la pila està plena.
- Si intentem inserir l'element en una pila, i la pila està plena, aleshores el desbordament es produeix la condició.
- Quan inicialitzem una pila, posem el valor de top com -1 per comprovar que la pila està buida.
- Quan el nou element s'empeny en una pila, primer, el valor de la part superior s'incrementa, és a dir, superior=top+1, i l'element es col·locarà a la nova posició del superior .
- Els elements s'aniran inserint fins arribar a la màx mida de la pila.
Funcionament POP
Els passos implicats en l'operació POP es detallen a continuació:
- Abans d'esborrar l'element de la pila, comprovem si la pila està buida.
- Si intentem eliminar l'element de la pila buida, aleshores el desbordament inferior es produeix la condició.
- Si la pila no està buida, primer accedim a l'element que apunta superior
- Un cop realitzada l'operació pop, la part superior es disminueix en 1, és a dir, superior=top-1 .
Aplicacions de Stack
Les següents són les aplicacions de la pila:
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';>