Au lieu d'utiliser un tableau, nous pouvons également utiliser une liste chaînée pour implémenter la pile. La liste chaînée alloue la mémoire de manière dynamique. Cependant, la complexité temporelle dans les deux scénarios est la même pour toutes les opérations, c'est-à-dire push, pop et peek.

Dans l'implémentation de liste chaînée de la pile, les nœuds sont conservés de manière non contiguë dans la mémoire. Chaque nœud contient un pointeur vers son nœud successeur immédiat dans la pile. On dit que la pile est dépassée si l'espace restant dans le tas mémoire n'est pas suffisant pour créer un nœud.

Le nœud le plus haut de la pile contient toujours null dans son champ d'adresse. Discutons de la manière dont chaque opération est effectuée dans l'implémentation de liste chaînée de la pile.

faire pendant que java

Ajout d'un nœud à la pile (opération Push)

L'ajout d'un nœud à la pile est appelé pousser opération. Pousser un élément vers une pile dans une implémentation de liste chaînée est différent de celui d'une implémentation de tableau. Afin de pousser un élément sur la pile, les étapes suivantes sont impliquées.

1. Créez d’abord un nœud et allouez-lui de la mémoire.
2. Si la liste est vide, l'élément doit être poussé comme nœud de départ de la liste. Cela inclut l'attribution d'une valeur à la partie données du nœud et l'attribution d'une valeur nulle à la partie adresse du nœud.
3. S'il y a déjà des nœuds dans la liste, alors nous devons ajouter le nouvel élément au début de la liste (pour ne pas violer la propriété de la pile). Pour cela, attribuez l'adresse de l'élément de départ au champ d'adresse du nouveau nœud et faites du nouveau nœud le nœud de départ de la liste.

Complexité temporelle : o(1)





Implémentation en 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'); } } 

Supprimer un nœud de la pile (opération POP)

La suppression d'un nœud du haut de la pile est appelée populaire opération. La suppression d'un nœud de l'implémentation de liste chaînée de la pile est différente de celle de l'implémentation de tableau. Afin de sortir un élément de la pile, nous devons suivre les étapes suivantes :

'Qu'est-ce que 10 sur 100'

Vérifiez l'état de sous-versement :La condition de dépassement de capacité se produit lorsque nous essayons de sortir d'une pile déjà vide. La pile sera vide si le pointeur de tête de la liste pointe vers null.Ajustez le pointeur de la tête en conséquence :Dans la pile, les éléments ne sont extraits que d'une seule extrémité, par conséquent, la valeur stockée dans le pointeur de tête doit être supprimée et le nœud doit être libéré. Le nœud suivant du nœud principal devient désormais le nœud principal.

Complexité temporelle : o(n)

quand se termine le premier trimestre

Implémentation en 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'); } } 

Afficher les nœuds (Traversing)

Afficher tous les nœuds d'une pile nécessite de parcourir tous les nœuds de la liste chaînée organisée sous forme de pile. À cette fin, nous devons suivre les étapes suivantes.

1. Copiez le pointeur de tête dans un pointeur temporaire.
2. Déplacez le pointeur temporaire sur tous les nœuds de la liste et imprimez le champ de valeur attaché à chaque nœud.

Complexité temporelle : o(n)

Implémentation 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; } } } 

Programme piloté par menu en C implémentant toutes les opérations de pile à l'aide de liste chaînée :

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