En terminale

• Piles (LIFO)
• Files (FIFO)
• Listes chainés
• listes vs dictionnaires
• Exercices

La notion de pile (stack pour les anglo-saxons) est assez simple à comprendre. On empile les données les unes par dessus les autres et on ne peut accéder qu'à la dernière donnée ajoutée. Si on la supprime, on peut alors accéder à la donnée située juste en dessous. Le dernier entré étant le premier accessible (Last In First Out) on nomme cela LIFO. Lire le contenu du dernier élément et l'effacer s'appelle dépiler.

Cela nous fait un peu penser aux listes. La méthode append, ajoute à la fin de la liste. Mais à la différence d'une vraie pile, on a aussi accés à un élément au milieu de la liste!

Les exemples concrêts sont simples et ne manquent pas. Si je fabrique un collier de perle, je ne peux sortir que la dernière perle enfilée. Pour laver une pile d'assiette...je vais forcément placer la suivante au dessus et je vais forcément laver en premier... celle qui est au dessus, donc la dernière ajoutée. Un autre exemple, la commande Ctrl-Z qui annule la dernière action (on remonte de la dernière action à la première).

Pour empiler (méthode push) en python on utilise append. Pour dépiler (pop), on utilise la méthode pop sur les listes, par exemple dernier=liste.pop() va renvoyer le dernier élément de la liste mais va aussi l'effacer! Attention, le pop sur une liste vide engendre une erreur!

L'unité centrale de l'ordinateur utilise une pile pour gérer les appels de fonctions. Imaginons une fonction1 avec des paramètres:

• Avant de passer les paramètres à la fonction1, l'UC en crée une copie et le place sur une pile
• la fonction1 dépile et utilise la copie (la pile est vide)
• si la fonction1 appelle une autre fonction2, l'UC va empiler le contenu de fonction2 par dessus celui de fonction1. Lorsque fonction2 devra retourner ses résultats à fonction1, on va dépiler..
• etc....

Par déduction, la programmation par récursivité (fonction qui s'appelle elle même) est un pile d'appels que l'on dépile lorsque l'on est arrivé au plus profond de la récursivité.

Dans une file, les élément se placent les uns à la suite des autres (on les enfile) mais seul le premier peut sortir de la file (on le défile). Le premier arrivé est le premier sorti (Last In First Out), on nomme cela FIFO.

Les exemples concrêts sont simples et ne manquent pas. Le plus simple, une file d'attente...le premier arrivé sera (normalement) le premier servi et réciproquement le dernier arrivé sera le dernier servi. Les serveurs d'impression, une file d'attente est crée et la première demande d'impression sera la première traitée.

Pour modéliser une file en Python, on utilise append pour ajouter et pop(0) pour lire et effacer le premier élément arrivé.

Dans une liste chainées, chaque élément de la liste est liée au suivant. Chaque élément est mis en mémoire avec deux informations. La valeur de l'élément et l'adresse de l'élément suivant!

Depuis le début de ce cours, vous devez vous demander: "pourquoi un cours sur les piles, les files...alors que les listes en Python en font bien plus?". Tout simplement parce que tout ce que nous sommes en train de décrire sont des objets abstraits, ils n'existent pas nécessairement dans tous les langages mais ce sont des structures de données à connaitre que nous pouvons créer si nécessaire. Par exemple, en C mais aussi en java (initialement), le tableau dynamique (que l'on peut étendre en fonction des besoins) n'existe pas. On doit choisir dès le début, puisque ce sont des langages fortement typés, la taille du tableau que l'on va utiliser. Si le tableau est trop petit...on est coincé. Lorsque l'on code nous l'objet 'tableau dynamique' en C, on dit que l'on implémente l'objet abstrait.

Les listes chainées permettent de construire un tableau dynamique dans ces langages, puisque chaque élément contient l'adresse mémoire du suivant, les données ne sont plus nécessairement stockées les unes à la suite des autres en mémoire: on n'a plus de problème de taille. De même, insérer un élément devient trivial. Admettons que l'on veuille insérer un élément entre

• l'élément_1 qui pointe vers l'adresse 0001 et l'élément_2 qui est donc à l'adresse 0001
• on crée un élément_1_bis qui pointe vers une adresse libre, par exemple 0101
• on change le pointeur de l'élément_1 vers l'adresse 0101

De même, supprimer un élément est très simple.

Nous avons vu en première que dans un dicitionnaire (aussi appelé tableau associatif) on retrouve les éléments par la valeur d'une clé qui est unique et non mutable dans le dictionnaire. Les dictionnaires python sont construits sur une structure abstraite nommée, table de hachage.

Le gros défaut des listes chainées, c'est que l'on ne peut pas accéder directement à un élément, il faut parcourir la liste.

En mémoire, les données arrivent un peu comme dans une liste python et sont empilées lorsqu'on en ajoute. Pourtant, contrairement aux listes, les dictionnaires n'utilisent pas d'index! En fait, lorsque vous fabriquez un dictionnaire, la clé est transformée en un nombre qui sera l'index de l'élément dans le tableau. Cette transformation de la clé en un nombre représentant l'index s'appelle le hachage.

Vous pouvez fabriquer votre propre fonction de hachage mais attention aux collisions! Si deux clés différentes renvoient la même valeur, il faut trouver une solution! On peut utiliser une liste chainée pour stocker les éléments de même clé, on utilise alors un espace de stockage supplémentaire et, on retrouvera pour les éléments ayant la même clé, les incovéniant de la liste chainée. On peut aussi aller chercher plus loin dans la table, un autre emplacement libre par une méthode que nous n'allons pas décrire ici mais qui permet de ne pas étendre inutilement la mémoire prévue.

On se rend compte que le choix de la fonction de hachage est important! Une fonction trop naïve risque de donner des clés identiques. En python vous pouvez utiliser la commande hash pour visualiser le hachage d'une chaine de caractère.

1. Utilisez le langage orienté objet pour créer un objet pile avec sa méthode push et pop, nombre d'éléments,affichage des éléments.
2. Utilisez le langage orienté objet pour créer un objet file avec sa méthode push et pop,nombre d'éléments,affichage des éléments.
3. Utilisez le langage orienté objet pour créer un objet chainé, qui permet la création, insertion, suppression, ajout d'un élément, nombre d'éléments, affichage des éléments.
4. Utilisez le langage orienté objet pour créer un objet de type dictionnaire à partir d'une table de hashage de votre cru. Si une clé possède un hachage déjà rencontré, on se contentera d'un message d'erruer de hachage...sauf si vous avez le courage et le talent d'aller plus loin.