En lloc d'utilitzar la matriu, també podem utilitzar la llista enllaçada per implementar la pila. La llista enllaçada assigna la memòria de manera dinàmica. Tanmateix, la complexitat del temps en tots dos escenaris és la mateixa per a totes les operacions, és a dir, push, pop i peek.

convertidor de cadena a int

En la implementació de llistes enllaçades de la pila, els nodes es mantenen de manera no contigu a la memòria. Cada node conté un punter al seu node successor immediat a la pila. Es diu que la pila s'ha desbordat si l'espai que queda al munt de memòria no és suficient per crear un node.

El node superior de la pila sempre conté null al seu camp d'adreça. Anem a discutir la manera com es realitza cada operació en la implementació de llista enllaçada de la pila.

Afegir un node a la pila (operació push)

Afegir un node a la pila s'anomena empènyer funcionament. Empènyer un element a una pila en la implementació de la llista enllaçada és diferent de la d'una implementació de matriu. Per empènyer un element a la pila, s'involucren els passos següents.

1. Creeu primer un node i assigneu-hi memòria.
2. Si la llista està buida, l'element s'ha d'empènyer com a node inicial de la llista. Això inclou assignar valor a la part de dades del node i assignar null a la part d'adreça del node.
3. Si ja hi ha alguns nodes a la llista, hem d'afegir el nou element al començament de la llista (per no violar la propietat de la pila). Per a això, assigneu l'adreça de l'element inicial al camp d'adreça del nou node i feu que el nou node sigui el node inicial de la llista.

Complexitat temporal: o(1)





Implementació 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'); } } 

Eliminació d'un node de la pila (operació POP)

L'eliminació d'un node de la part superior de la pila s'anomena pop funcionament. La supressió d'un node de la implementació de la llista enllaçada de la pila és diferent de la implementació de la matriu. Per treure un element de la pila, hem de seguir els passos següents:

executa l'intèrpret d'ordres de l'script

Comproveu l'estat de desbordament:La condició de desbordament es produeix quan intentem sortir d'una pila ja buida. La pila estarà buida si el punter de capçalera de la llista apunta a null.Ajusteu el punter del cap en conseqüència:A la pila, els elements només apareixen des d'un extrem, per tant, el valor emmagatzemat al punter de capçalera s'ha de suprimir i el node s'ha d'alliberar. El següent node del node principal es converteix ara en el node principal.

Complexitat temporal: o(n)

Implementació 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'); } } 

Mostra els nodes (Traversing)

Per mostrar tots els nodes d'una pila cal travessar tots els nodes de la llista enllaçada organitzada en forma de pila. Per a això, hem de seguir els passos següents.

1. Copieu el punter de capçalera en un punter temporal.
2. Mou el punter temporal per tots els nodes de la llista i imprimeix el camp de valor adjunt a cada node.

Complexitat temporal: o(n)

C Implementació

 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 dirigit per menús en C que implementa totes les operacions de la pila mitjançant una llista enllaçada:

 #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; } } }