Présentation des structures
Il est parfois utile d’avoir une structure de données permettant de se souvenir de l’ordre dans lequel les éléments ont été ajoutés. Les deux structures les plus élémentaires pour faire cela sont les files et les piles. Pour ces deux structures, seules deux actions élémentaires sont possibles : ajouter un élément, ou retirer un élément.
- Les files (aussi appelées FIFO, pour First In, First Out) : Quand on retire un élément d’une file, c’est celui qui y est depuis le plus longtemps qui est extrait. Il suffit de penser à une file à la caisse d’un supermarché.
- Les piles (aussi appelées LIFO, pour Last In, First Out) : Quand on retire un élément d’une pile, c’est celui qui y est depuis le moins longtemps qui est extrait. Ici, il suffit de penser à une pile d’assiettes.
Il n’y a pas de notion d’indice dans les files et les piles. Ainsi, si on veut enlever le plus ancien élément d’une pile, il faudra au préalable enlever tous ceux qui ont été ajoutés après lui.
En pratique, les piles et files peuvent être implémentées à l’aide de listes. Ajouter un élément à une file revient à l’ajouter au bout de la queue de la liste, et ajouter un élément à une pile revient à l’ajouter en tête de liste. Retirer un élément se fait dans les deux cas en récupérant la tête de la liste.
Les piles et les files dans l’informatique
Pour se rendre compte de l’importance de ces deux structures de données en informatique, nous présentons deux exemples de la vie réelle dans lesquelles elles sont utilisées.
Les files dans la communication
Pour que deux personnes communiquent, ils faut qu’elles s’envoient des messages; et pour que deux personnes se comprennent, il faut qu’elles s’envoient des messages dans un ordre logique. Vous aurez plus de facilité à comprendre la phrase “Un ordinateur permet de faire des erreurs plus rapidement que n’importe quelle autre invention humaine, à l’exception près des pistolets et de la tequila” que “faire invention et n’importe Un tequila près des à ordinateur de autre permet pistolets l’exception la quelle de des erreurs humaine, rapidement que plus”.
Pour les machines, c’est pareil : l’ordre est important, et doit être pris en compte. Certains modèles de communication (d’autres sont bien plus complexes) utilisent des files pour cela. Imaginons un modèle dans lequel on a un ordinateur A qui écrit des mots dans une file, et un ordinateur B qui les lit. Si l’ordinateur A envoie les mots dans l’ordre, alors B les lira dans le même ordre (car le premier élément inséré dans une file est aussi le premier à en sortir), et la communication sera possible.
Vous vous demandez peut-être pourquoi passer par une file et ne pas envoyer les infos directement ? L’intérêt est que les ordinateurs A et B ne vont pas forcément à la même vitesse (qualité du processeur, de la carte réseau…). Ainsi, si l’ordinateur A envoie très vite (directement) des messages à l’ordinateur B, celui-là en ratera certains. Passer par une file permet de stocker les messages, en en conservant l’ordre, pour faire abstraction de ces problèmes de synchronisation.
Les piles dans les langages de programmation
Quand un système d’exploitation exécute un programme, il lui attribue un peu de mémoire pour qu’il puisse faire ses calculs correctement. Cette mémoire est généralement séparée en deux zones : le tas qui permet de stocker les données, et la pile qui permet (entre autres) d’appeler des fonctions dans les programmes.
Dans la plupart des langages de programmation, quand on appelle une fonction f(a, b) à un endroit du code, il se passe la séquence (simplifiée) suivante :
- L’adresse de retour est mise sur la pile. Cela permettra de revenir juste après l’appel à f dans le code une fois f terminée.
- Le paramètre a est mis sur la pile.
- Le paramètre b est mis sur la pile.
- On indique au processeur qu’il doit exécuter le code de f. La pile est actuellement comme suit :
- On récupère un élément de la pile : le code de f connaît à présent b.
- On récupère un élément de la pile : le code de f connaît à présent a.
- On exécute le code de f.
- Une fois f terminée, on récupère un élément de la pile : le code de f connaît à présent l’adresse de retour.
- On indique au processeur qu’il doit exécuter le code à l’adresse de retour, pour reprendre le déroulement normal du programme.
Mais pourquoi utiliser une pile plutôt que des variables pour passer ces informations ? Eh bien le processeur ne connaît pas les détails de f ! Il est possible que f fasse appel à une autre fonction g par exemple. Si on utilisait des variables, l’adresse de retour de f serait écrasée par l’adresse de retour de g, et quand g serait terminée, on ne pourrait plus jamais revenir au moment de l’appel de f.
Pourquoi pas une file alors ? Là encore, le problème intervient si f appelle une fonction g. Comme l’adresse de retour de f est mise avant celle de g dans la file, quand il faudra revenir de l’appel à g, le processeur récupérera à la place l’adresse de retour de f (la plus ancienne dans la file) ! On n’exécutera donc jamais le code de f situé après l’appel à g.