Les listes, les piles et les files

Les listes chaînées, piles et files sont des structures de données à une dimension permettant de stocker de manière linéaire une suite finie de données. On les dénomme parfois structures linéaires.

Pour s'imaginer ces structures linéaires, imaginez un garagiste devant gérer les clients de la journée. Chaque rendez-vous est inscrit sur une fiche qui contient toutes les informations nécessaires (nom du client, modèle du véhicule, travaux à faire...) et qu'il devra stocker et à laquelle il devra accéder le moment venu. Devant lui s'offrent plusieurs choix pour la gestion de ces fiches. Nous allons examiner les structures de liste chaînée, pile et file et voir comment elles peuvent s'appliquer à notre exemple.

La structure liste chaînée

Une liste (ou liste chaînée) est une structure décrivant une succession linéaire de données dans laquelle il est possible de lire, d'ajouter ou de supprimer des données au début, à la fin ou à l'intérieur de la liste.

Les listes chaînées sont une structure de donnée très souple et efficace. Il ne faut pas confondre cette structure de liste avec les listes Python qui sont en fait une structure bien plus riche, que l'on pourrait qualifier de tableau dynamique.

Dans une liste chaînée, chaque élément contient la donnée et un pointeur vers l'élément suivant. On accède à la liste via un pointeur vers son premier élément :

On peut imaginer pur notre exemple du garagiste une bannette contenant toutes les fiches client de la journée. Notre garagiste peut les parcourir une à une, insérer au milieu une nouvelle fiche pour un client qu'il voudrait intercaler etc...

Exemples d'opérations sur les listes

Voici quelques opérations possibles sur les listes chaînées

• Ajouter/retirer un élément au début, à la fin, à l'intérieur
• Concaténer de deux listes
• Scinder une liste en deux
• Accéder au n-ième élémént
• Rechercher la présence d'un élément

A vous de jouer

1. Décrire en langage naturel des algorithmes simples permettant de réaliser les opérations ci-dessus. Vous pourrez lorsque c'est utile vous aider de schémas.

Exemple : Ajout d'un élément au début de la liste chaînée

Nous verrons en TP la manière de programmer ces algorithmes en Python.

1. Citez un avantage de la liste chaînée par rapport au tableau de taille fixe ou dynamique (comme le type list en python).

La structure de pile

La structure de pile est un cas particulier de liste chaînée dans lequel on accède uniquement au premier élément de la liste : celui que l'on nomme le sommet de la pile. On représente en général cette structure sous forme verticale.

On peut prendre pour exemple une pile d'assiettes : La dernière assiette rangée sera la première que l'on ressortira. On parle parfois de pile LIFO (Last In First Out : dernier entré, premier sorti).

Opérations valides sur les piles

Les opérations permises sur les piles sont plus simples que sur les listes : il est permis

• d'empiler un nouvel élément (ajouter un élément au sommet de la pile)
• de dépiler le dernier élément saisi
• de consulter la valeur de l'élément au sommet de la pile sans le dépiler
• de tester si la pile est vide
• de connaître le nombre d'éléments dans la pile.

Vous voyez donc qu'il n'est pas possible d'accéder directement au n-ième élément d'une pile : Il faudrait dépiler les n-1 premiers éléments et de ce fait, détruire partiellement notre pile.

Exemples d'utilisation

Les piles sont extrèmement utiles en informatique et vous les utilisez quotidiennement, parfois même sans vous en rendre compte :

• La fonction annuler (Ctrl-Z) de votre traitement de textes par exemple est une pile : Quand vous tapez Ctrl-Z, vous annulez la dernière opération effectuée. Quand vous faites une nouvelle opération, celle-ci est mémorisée au sommet de la pile. Vous ne pouvez pas annuler l'avant dernière bopération sauf à annuler la dernière.
• Le bouton retour de votre navigateur internet fonctionne également à l'aide d'une pile. Les pages web consultées lors de votre navigation sur une page sont empilées et le bouton retour permet d'accéder à la dernière page présente sur la pile.
• Certaines calculatrices fonctionnent à l'aide du'une pile pour stocker les arguments des opérations : c'est le cas de beaucoup de calculatrices de la marque HP, dont la première calculatrice scientifique ayant jamais été produite : la HP 35 de 1972.

Exemple de calcul avec une pile

Le mode de calcul avec une pile s'appelle RPN (Reverse Polish Notation ou notation polonaise inverse). Dans cette logique postfixée, on saisit d'abord les arguments de l'opération puis en dernier, l'opération à réaliser.

Exemple : Pour faire 2+3 on empilera 2, puis 3 et enfin on invoquera la fonction +. Cette logique est extrèmement efficace et rapide, en particulier dans les enchaînements d'opérations car elle ne nécessite pas de saisir des parenthèses. elle permet aussi de faire moins d'erreurs de calcul car on est obligé de réfléchir aux priorités des opérations au moment de la saisie.

Voici une illustration en vidéo de l'utilisation de la calculatrice HP-45 (1974) qui est l'une des toutes premières caculatrices scientifiques.

A vous de jouer

• On tape sur la HP-45 la séquence de touche suivante : 12 ENTER 4 ENTER 3 x -. Quel est le calcul effectué ? Quel est le résultat sur le sommet de la pile ?
• On souhaite effectuer le calcul $(12-4)\times 3$. Quelle séquence de touche doit-on révoir ?

Implémentation en Python

L'implémentation des piles en python se fait facilement à l'aide des méthodes append() et pop() du type list :

• ma_pile.append(ma_valeur)   # permet d'empiler une valeur
  

• ma_pile.pop()               # permet de dépiler une valeur
  

• len(ma_pile)                # renvoie la longueur de ma_pile
  

A vous de jouer

Dans l'implémentation python proposée ci-dessus, quelle est la commande à taper pour connaître la valeur au sommet de ma_pile sans la dépiler ?

Nous verrons plus en détails en TP la manière de travailler avec les piles sous Python.

Les files

Dans une file, les éléments sont placés les uns à cotés des autres comme dans une pile, à la différence que seul l'on sort les éléments du plus ancien vers le plus récent. Cela correspond à ce qui se passe dans une file d'attente : si on reprend l'exemple de notre garagiste, il reçoit les clients le matin et réceptionne leurs fiches dans une file d'attente. Pour effectuer les travaux sur le véhicule, le garagiste va récupérer les fiches en commençant par le premier client arrivé, c'est à dire la première fiche entrée dans la file. C'est la loi du premier arrivé, premier servi ou FIFO (First In First out). C'est le comportement classique d'une file d'attente.

Exemple d'utilisation

Dans le domaine informatique, on retrouve par exemple les files dans les files d'impression où le premier document envoyé à l'imprimante sera le premier document à être imprimé.

Opérations valides sur les files

Les opérations permises sur les files sont similaires aux piles. Il est possible

• d'emfiler un nouvel élément (ajouter un élément à la fin de la file)
• de défiler le premier élément saisi (celui au début de la file)
• de consulter la valeur du premier élément au début de la file sans le sortir de la file
• de tester si la file est vide
• de connaître le nombre d'éléments dans la file.

Vous voyez donc qu'il n'est pas possible d'accéder directement au n-ième élément d'une file : Il faudrait défiler les n-1 premiers éléments et de ce fait, détruire partiellement notre file.

Implémentation en Python

L'implémentation des files en python se fait de manière analogue aux piles :

• ma_file.append(ma_valeur)   # permet d'emfiler une valeur
  

• ma_file.pop(0)              # permet de défiler une valeur
  

• len(ma_file)                # renvoie la longueur de ma_file
  

A vous de jouer

1. Dans l'implémentation python proposée ci-dessus, quelle est la commande à taper pour connaître la valeur du premier élément de la file ?
2. On considère la file constituée des entiers 25, 31, 1, 54, 13.
   1. On ajoute la valeur 35 à cette file puis on sort 2 valeurs. Quel est alors le contenu de la file.
   2. Le contenu de la file change-t-il si on effectue ces opération dans le sens contraire ? (on sort 2 valeurs puis on ajoute 35)

Nous verrons plus en détails en TP la manière de travailler avec les piles sous Python.