III) PILES ET FILES D'ATTENTES

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-> )

1) Les piles (LIFO)

Les structures de pile ne devraient pas sembler étrangères aux utilisateurs de calculateurs HP... c'est une structure dans laquelle on empile et dépile des données. L'endroit par lequel entrent et sortent les données est appelé le Sommet. On appelle profondeur de la pile le nombre d'éléments qu'elle contient. Comme les opérations (empilage et dépilage) se font toutes au niveau du sommet, cette structure est aussi appelée LIFO - Last In First Out (Dernier rentré Premier sorti) -. Une bonne représentation d'une pile est la pile de plateaux dans les caféterias... pour accéder au deuxième plateau, il faut d'abord retirer le premier.

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:

SWAP : interverti le sommet et la deuxième case de la pile
ROT : fait une permutation circulaire sur les 3 premiers élements en partant du sommet.
DEEP : retourne la profondeur de la pile

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)

2) Les files d'attente

Le principe des files d'attente (ou queues) est simple ; pour continuer avec mes comparaisons, une file d'attente est comme une pile, mais avec une entrée et une sortie... C'est à dire que les données s'accumulent dans la file d'attente jusqu'à ce qu'elle soient traitées (sorties). Les premières données arrivées sont donc les premières traitées, les autres s'accumulant derrière et attendant leur tour... C'est pour cela que cette structure est également appelée FIFO - First In First Out (Premier rentré Premier sorti).

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

Vous remarquerez que dans le cas de la structure de file d'attente, les données ressortent dans l'ordre dans lequel elles sont rentrées (contrairement aux piles).

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 :

un qui pointe sur la tête de la liste chaînée (head)
un qui pointe sur la fin de la liste chaînée (tail)

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...