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 dynamiquement. 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 la pile en liste chaînée, les nœuds sont maintenus 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. La pile est dite survolée si l’espace laissé dans le tas de 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 la pile en liste chaînée.
Ajout d’un nœud à la pile (opération Push)
L’ajout d’un nœud à la pile est appelé opération push. 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. Pour pousser un élément sur la pile, les étapes suivantes sont impliquées.
- Créez d’abord un nœud et allouez-lui de la mémoire.
- 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 de null à la partie adresse du nœud.
- S’il y a déjà des nœuds dans la liste, 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.
- Vérifiez la condition de sous-écoulement: La condition de sous-écoulement 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 sur null.
- Ajustez le pointeur de tête en conséquence: Dans la pile, les éléments ne sont extraits que d’une 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 maintenant le nœud principal.
- Copiez le pointeur de tête dans un pointeur temporaire.
- Déplacez le pointeur temporaire à travers tous les nœuds de la liste et imprimez le champ de valeur attaché à chaque nœud.
Complexité temporelle : o(1)
Implémentation C :
Suppression d’un nœud de la pile (opération POP)
La suppression d’un nœud du haut de la pile est appelée opération pop. La suppression d’un nœud de l’implémentation de la liste chaînée de la pile est différente de celle de l’implémentation du tableau. Pour extraire un élément de la pile, nous devons suivre les étapes suivantes :
Complexité temporelle : o(n)
Implémentation C
Afficher les nœuds (Traversants)
Afficher tous les nœuds d’une pile nécessite de traverser tous les nœuds de la liste chaînée organisée sous forme de pile. À cette fin, nous devons suivre les étapes suivantes.
Complexité temporelle : o (n)