En lugar de usar una matriz, también podemos usar una lista vinculada para implementar la pila. La lista enlazada asigna la memoria dinámicamente. Sin embargo, la complejidad del tiempo en ambos escenarios es la misma para todas las operaciones, es decir, empujar, abrir y mirar.

En la implementación de la pila de lista vinculada, los nodos se mantienen de forma no contigua en la memoria. Cada nodo contiene un puntero a su nodo sucesor inmediato en la pila. Se dice que la pila está desbordada si el espacio que queda en el montón de memoria no es suficiente para crear un nodo.

El nodo superior de la pila siempre contiene nulo en su campo de dirección. Analicemos la forma en que se realiza cada operación en la implementación de lista vinculada de la pila.

Agregar un nodo a la pila (operación Push)

Agregar un nodo a la pila se conoce como empujar operación. Empujar un elemento a una pila en una implementación de lista vinculada es diferente a una implementación de matriz. Para empujar un elemento a la pila, se requieren los siguientes pasos.

cómo convertir int a cadena java

1. Primero cree un nodo y asígnele memoria.
2. Si la lista está vacía, el elemento debe incluirse como nodo inicial de la lista. Esto incluye asignar valor a la parte de datos del nodo y asignar nulo a la parte de dirección del nodo.
3. Si ya hay algunos nodos en la lista, entonces tenemos que agregar el nuevo elemento al principio de la lista (para no violar la propiedad de la pila). Para ello, asigne la dirección del elemento inicial al campo de dirección del nuevo nodo y convierta el nuevo nodo en el nodo inicial de la lista.

Complejidad del tiempo: o(1)

pagar en git





Implementación de C:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Eliminar un nodo de la pila (operación POP)

Eliminar un nodo de la parte superior de la pila se conoce como estallido operación. Eliminar un nodo de la implementación de la lista vinculada de la pila es diferente de hacerlo en la implementación de la matriz. Para sacar un elemento de la pila, debemos seguir los siguientes pasos:

Verifique la condición de desbordamiento insuficiente:La condición de desbordamiento insuficiente ocurre cuando intentamos salir de una pila que ya está vacía. La pila estará vacía si el puntero principal de la lista apunta a nulo.Ajuste el puntero de la cabeza en consecuencia:En la pila, los elementos se extraen solo de un extremo, por lo tanto, se debe eliminar el valor almacenado en el puntero principal y se debe liberar el nodo. El siguiente nodo del nodo principal ahora se convierte en el nodo principal.

Complejidad del tiempo: o(n)

implementación de C

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Mostrar los nodos (Atravesar)

Para mostrar todos los nodos de una pila es necesario atravesar todos los nodos de la lista vinculada organizada en forma de pila. Para ello debemos seguir los siguientes pasos.

1. Copie el puntero principal en un puntero temporal.
2. Mueva el puntero temporal a través de todos los nodos de la lista e imprima el campo de valor adjunto a cada nodo.

Complejidad del tiempo: o(n)

Implementación C

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Programa controlado por menú en C que implementa todas las operaciones de la pila utilizando una lista vinculada:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }