Pile impérative

Une pile impérative est une implémentation du type abstrait pile avec une interface impérative.

Voici les détails de ces opérations :

Implémentation

Utilisant une pile fonctionnelle

L'implémentation d'une pile impérative peut se faire facilement grâce à une pile fonctionnelle et un objet en-tête. Il suffit pour cela de stocker dans l'objet en-tête, une référence à la pile fonctionnelle. Pour empiler ou dépiler la pile impérative, il suffit de remplacer cette référence par le résultat de l'opération correspondante sur la pile fonctionnelle référencée. Cette implémentation a exactement les mêmes caractéristiques de performance que la pile fonctionnelle.

Utilisant un tableau

Mais il est possible d'améliorer la performance de la pile impérative, en tout cas, la performance amortie. Pour cela, on peut employer un objet en-tête comme dans le cas précédent, mais celui-ci contiendra une référence à un tableau (et non à une pile fonctionnelle) et un champs indiquant le premier index libre du tableau. Certains langages de programmation (comme le C par exemple) nécessite également un champ indiquant la taille du tableau référencé, car les tableaux de ces langages ne contiennent pas leur propre taille.

Pour empiler, il suffit de stocker l'objet à empiler dans la première place libre du tableau et d'incrémenter le champ contenant l'index de cette place. Pour dépiler, il suffit de décrémenter ce champ (mais attention aux fuites de mémoire, il est prudent de stocker une valeur comme NIL dans place qui sera libéré). Pour récupérer l'objet au sommet de la pile, il suffit de consulter la place avant la première place libre et pour déterminer si la pile est vide, il suffit de vérifier si la première place libres est la place numéro 0.

Le seul problème avec cette solution est que le tableau peut se remplir. Il faut alors allouer un tableau plus grand et déplacer les objets de l'ancien tableau au nouveau. Lorsque cela se produit, la durée de l'opération est linéaire. Pourtant, il est possible d'amortir ce coût, à savoir que le coût de n opérations consécutives reste également linéaire pour un coût moyen constant par opération.

Pour y arriver, il faut, lorsque le tableau doit être ré-alloué, que le nouveau tableau soit plus grand du précédent par un facteur multiplicatif de l'ancien. On peut par exemple augmenter la taille de 50% ou d'un facteur 2 (doubler la taille). Il est tentant d'augmenter la taille d'une nombre constant de places, par exemple 100 places supplémentaires, mais cela ne permet pas d'obtenir un coût moyen constant, à moins qu'il soit connu que la probabilité d'avoir une suite d'opérations empiler est faible.

De la même manière qu'il faut augmenter la taille du tableau lorsqu'il n'y a plus de place, il faut diminuer la taille ce celui-ci lorsque le nombre d'éléments de la pile tome en dessous d'un certain seuil. Pour cela, il faut laisser un peu de place après cette diminution. Sinon, une suite alternante d'opérations empiler et dépiler provoquerait un changement de taille à chaque opération, avec une performance catastrophique comme résultat.

En général, la performance d'une pile implémenté sous la forme de tableau est très bonne. Des suites d'opérations qui n'augmentent pas considérablement la taille de la pile sont exécutées très rapidement. Empiler un objet revient à stocker l´objet dans un tableau et d'incrémenter un index, ce qui est très rapide, surtout par rapport à l'allocation d'une cellule comme dans le cas de l'implémentation sous la forme de liste chaînée. Dépiler un objet est également très rapide, alors que dans le cas de la liste chaînée, la cellule doit être tracée et libérée par le ramasse-miettes ce qui peut être assez coûteux.

La localité d'une pile implémenté sous la forme de tableau est excellente. À suivre...

Exemples de code

C