require("../global.php"); entete(); ?>
Contrairement à ce que vous imaginez, nous n'allons pas parler de volts ou d'attentes interminables aux caisses des supermarchés ;-) C'est pas de ma faute si ces structures s'appelent comme ça ! En fait, pour vous donner une petite idée préalable, disons que les piles tiennent plus de l'empilement que des batteries, et que les files d'attentes ont quand même quelque chose à voir avec les queues des supermarchés dans le sens où elles illustrent la philosophie du "Premier arrivé, premier servi".
Commençons par le plus simple (à mettre en oeuvre 8-> )
Une propriété essentielle des piles est qu'elles restituent les données rentrées à l'envers :
EXEMPLE : (Le sommet est vers le haut de l'écran)
INSTRUCTION | SORTIE | ETAT DE LA PILE |
Initialise_pile | xxxx | ^^^ |
Empile 1 | xxxx | -1- ^^^ |
Empile 2 | xxxx | -2- -1- ^^^ |
Empile 3 | xxxx | -3- -2- -1- ^^^ |
Depile | 3 | -2- -1- ^^^ |
Depile | 2 | -1- ^^^ |
Depile | 1 | ^^^ |
Nous avons donc empilé 1-2-3 et la pile nous a ressorti 3-2-1, donc elle a rendu la séquence de nombres à l'envers.
Passons maintenant à l'implémentation...
Pour les piles (et les files), j'ai préparé une unité prête à être utilisée; mais ce n'est pas parce que j'ai tout fait qu'il n'y a plus rien à faire... Comme précédemment, je vous laisse le soin d'améliorer le code en y adjoignant les tests pour vérifier si la mémoire du tas est suffisante. J'ai volontairement omis d'implanter une fonction qui retourne la profondeur (très facile à faire !) et vous devrez surement faire quelques modifications mineures si vous souhaitez utiliser autre chose que des entiers comme données..
Cependant, l'unité telle qu'elle est fonctionne parfaitement.
Vous trouverz une version non commentée en annexe. Voici la version commentée:
Notez que nous n'avons besoin à chaque fois de ne passer que le pointeur qui pointe sur le sommet de la pile.
Voir Listing 3, commenté..
Voila, comme vous le voyez, c'est très court ! Je vous propose à titre d'exercice de vous amuser à implanter les procedures suivantes:
Le champ d'application des piles est vaste... Elle peuvent servir par exemple à stocker des résultats intermédiaires ou encore être utilisées pour faire des analyseurs syntaxiques...
"And now, something different..." (J. Clees)
Je vais refaire le même shéma que pour les piles mais en utilisant cette fois-ci une file. La représentation est horizontale. E indique l'entrée et S la sortie...
INSTRUCTION | SORTIE | ETAT DE LA FILE |
Initialise File | xxxx | E-S |
Entrer_elem 1 | xxxx | E-1-S |
Entrer_elem 2 | xxxx | E-2-1-S |
Entrer_elem 3 | xxxx | E-3-2-1-S |
Sortir_elem | 1 | E-3-2-S |
Sortir_elem | 2 | E-3-S |
Sortir_elem | 3 | E-S |
Passons à l'implémentation :
J'ai à nouveau fait une unité minimale que vous retrouverez prête à l'emploi dans les annexes...
Je vous demanderai de bien noter que l'implantation de cette structure est plus délicate que celle de la pile donc faites plus attention ! Cette fois ci, nous avons besoin de deux pointeurs :
Voir Listing 4, commenté..
Et c'est tout pour les structures de files...
Ces structures ont également beaucoup d'applications ; elles peuvent par exemple servir à stocker des données en attente de traitement (si le processeur est trop occupé pour les traiter pour l'instant...) ou peuvent également servir de stockage temporaire... A vous de trouver les meilleures applications ou plutôt, essayez de voir où elles peuvent servir maintenant que vous connaissez leur existance...
PiedDePage(); ?>