Créer une file avec deux piles

On a vu que les performances d'une pile à partir d'une liste chaînée en programmation objet n'était pas du tout optimale. Implémenter une pile en utilisant les tableaux fonctionnait déjà beaucoup plus rapidement. Cela était lié au fait que l'empilement d'un nouvel élément "maillon" dans le cas d'une liste chaînée était un surcout qui pouvait doubler voire tripler le temps d'éxécution lors d'empilement.

Dans le cas des files, si on utilisait un tableau, suivant que l'on mette la l'entrée ou la sortie à gauche ou à droite du tableau, l'une des deux opérations nécessitait une réindexation de tous les éléments présents et les performances s'écroulaient dramatiquement

Nous avons vu une autre possibilité qui est la création d'une file à partir d'une liste doublement chaînée. Au niveau des performances d'insertion et de suppression, les performances redeviennent en temps constant. Cependant, on se retrouve avec le problème que l'on avait pour les piles : la création systématique d'un objet pour chaque "maillon" fait baisser les performances.

N'y aurait il pas moyen de faire mieux ?

L'ennemi de mon ennemi est mon ami

Vous vous souvenez sans doute de cette phrase entendu lors de vos cours de mathématique : l'ennemi de mon ennemi est mon ennemi. On vous a peut être dit cela pour vous parler de la multiplication des nombres relatifs : un nombre négatif multiplié par un nombre négatif, cela donne un nombre positif. Dit autrement, se retourner deux fois vous ramène dans la même direction.

Quel rapport avec nos piles et nos files ?

Si on regarde le fonctionnement d'une file, elle ne modifie pas l'ordre lorsqu'un ensemble d'élément passe dedans. C'est le principe même d'une file d'attente : les premiers clients servis seront les premiers arrivés. À contrario, dans une pile, l'ordre est inversé. Le dernier arrivé sera le premier à ressortir.

Imaginons maintenant que j'utilise deux piles. Si je vide la première pile dans une seconde pile, et que je dépile ensuite les éléments de la seconde pile, j'ai inversé l'ordre qui avait été inversé ... j'ai donc rétabli l'ordre.

Les ennemis de mes ennemis sont mes amis. Moins par moins, ça fait plus. Passer successivement dans deux piles, c'est comme passer dans une file.

En pratique

L'algorithme en pratique pour utiliser deux piles pour faire une file est le suivant :

• Pour créer la file vide, je crée ma pile d'entrée et ma pile de sortie
• Pour savoir si ma file est vide, je teste si mes deux files sont vides simultanément
• Pour enfiler un élément, je l'empile dans la pile d'entrée
• Pour dépiler un élément :
• Soit la pile de sortie contient des éléments. Je dépile un élément
• Soit la pile de sortie ne contient aucun élément. Je dépile alors la totalité de la pile d'entrée dans la pile de sortie puis je dépile un élément.

A faire vous même

Vous allez pouvoir implémenter cette file au moyen de deux piles. Le code proposé par le bouton ci dessous vous donne l'interface de la classe de File avec deux piles que vous compléterez en utilisant la méthode au dessus.

Efficacité

On peut se poser la question de l'efficacité d'une file implémentée avec 2 piles au lieu d'une file avec un tableau. Il est assez facile de coder les deux (avec un tableau ou avec deux piles) et de comparer les temps d'éxécutions des deux implémentations. Le petit programme ci dessous, accessible en cliquant sur le bouton, vous propose de comparer les temps d'éxécution pour 10 000, 50 000 et 100 0000 opération d'enfilement/défilement. On voit très nettement que le temps d'éxécution "explose" lorsque l'on a un tableau unique en comparaison avec la méthode à deux piles.

En particulier, quand on passe de 50 000 à 100 000 opérations, le temps de traitement avec deux piles est multiplié par 2, alors que le temps de traitement avec un tableau unique est des insert est multiplié par 4. Dans le premier cas, les insertions/suppression sont en coût constant, donc pour 2 fois plus de donnés je double le temps, alors que dans le second cas, le temps d'insertion/suppression est linéaire en fonction de la taille, et doubler la taille des données va multiplier le temps de traitement par 4, c'est à dire le carré de 2.

Cliquez sur le bouton ci dessous pour vérifier vous même l'efficacité