Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Piles et Files

Au programme

Contenus Capacités attendues Commentaires
- Piles
- Files.
- Distinguer des structures par le jeu des méthodes qui les caractérisent.
- Choisir une structure de données adaptée à la situation à modéliser.
- On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files.

Documents

26 oct. 2020

Sous-sections de Piles et Files

Physique, Chimie et Informatique > Terminales Spé. NSI > Piles et Files

Les Piles

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

  • Son nom ;
  • Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.
Avertissement

Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé.
Un TDA peut être implémenté de plusieurs façons différentes.

Qu’est-ce qu’une pile ?

Info

Une pile est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des assiettes dans une pile d’assiettes contenue dans une boite de profondeur quelconque mais étroite (ce qui empêche de manipuler les assiettes par le côté).
On peut donc seulement :

  • Empiler une nouvelle assiette au-dessus des autres assiettes (ou d’aucune assiette si la pile est vide) ;
  • Retirer l’assiette située tout en haut de la pile ;
  • Regarder l’assiette située tout en haut de la pile ;
  • Regarder si la pile est vide.
Spécification d’une Pile de valeurs de type T
  • Créer une pile (type) :
    • fonction : creer_pile() ⟶\longrightarrow retourne une pile vide ;
    • complexité idéale : O(0)O(0) (pas tout à fait vrai mais suffisant pour comprendre la suite).
  • Empiler une valeur en haut de la pile :
    • fonction : empiler(p: Pile[T], valeur: T) ⟶\longrightarrow None ;
    • complexité idéale : 1 opération élémentaire.
  • Accéder à la valeur située tout en haut de la pile :
    • fonction : lire(p: Pile[T]) ⟶\longrightarrow retourne la dernière valeur de la pile ;
    • Complexité idéale : 1 opération élémentaire.
  • Retirer la dernière valeur de la pile :
    • fonction : depiler(p: Pile[T]) ⟶\longrightarrow T ;
    • complexité idéale : 1 opération élémentaire.
  • Tester si une pile est vide :
    • fonction : est_vide(p: Pile[T]) ⟶\longrightarrow retourne un booléen ;
    • complexité idéale : 1 opération élémentaire.
Avertissement

La spécification d’une pile montre qu’il n’existe aucune opération élémentaire pour :

  • accéder à une donnée qui n’est pas sur le haut de la pile ;
  • déterminer combien de données contient la pile.
  • …
À retenir

La valeur dépilée est toujours la dernière valeur à avoir intégré la pile : Last In, First Out (LIFO)

Exemple d’utilisation d’une pile

Tout navigateur possède un bouton permettant de retourner sur des pages que l’on a déjà consultées.
Expliquer quelle structure de données permet de réaliser cette opération simplement et décrire les opérations en jeu.

Implémentation d’une structure de Pile à l’aide d’une liste Python

L’idée est de définir le type Pile à l’aide d’une classe ne possédant qu’un seul attribut nommé contenu, qui référence une liste, puis de créer les méthodes de la spécification. On peut, par la suite, utiliser les méthodes des listes de Python.

  1. Définir une classe nommée Pile et faire en sorte qu’à l’initialisation de tout objet de type Pile, l’attribut contenu référence une liste vide.

  2. Écrire le code de la méthode est_vide de la spécification.

  3. Écrire le code de la méthode empiler de la spécification.

  4. Écrire le code de la méthode depiler de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de dépiler une pile vide.

  5. Écrire le code de la méthode lire de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de lire une pile vide.

  6. Tester le code.

  7. Vérifier que la complexité de chacune des méthodes est égale à la complexité annoncée dans la spécification.

Info

L’implémentation à l’aide des listes Python est efficace car, en moyenne, les méthodes append et pop, s’exécutent en temps constant. Tous les langages ne présentent cependant pas la structure de tableau dynamique et une autre implémentation doit alors être mise en œuvre.

Jeu de tests possible

if __name__ == "__main__":
    p = Pile()
    p.empiler(2)
    print(p.lire())
    p.empiler(42)
    p.empiler(89)
    p.empiler(23)
    print(p.lire())
    print(p.depiler())
    print(p.lire())
    print(p.depiler())
    print(p.lire())
    print(p.depiler())
    print(p.lire())
    print(p.depiler())
    print(p.depiler())

Implémentation d’une structure de Pile à l’aide d’une liste chaînée

L’idée est de définir le type Pile à l’aide d’une classe ne possédant qu’un seul attribut nommé contenu, qui référence une liste chaînée, puis de créer les méthodes de la spécification.

  1. Écrire le code de la classe Cellule, cellule d’une liste chaînée.

  2. Définir une classe nommée Pile et faire en sorte qu’à l’initialisation de tout objet de type Pile, l’attribut contenu référence la liste vide.

  3. Écrire le code de la méthode est_vide de la spécification.

  4. Écrire le code de la méthode empiler de la spécification.
    Attention à bien choisir la façon d’empiler la valeur. On peut passer d’une complexité en O(1)O(1) à une complexité en O(N)O(N) !

  5. Écrire le code de la méthode depiler de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de dépiler une pile vide.

  6. Écrire le code de la méthode lire de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de lire une pile vide.

  7. Tester le code.

  8. Vérifier que la complexité de chacune des méthodes est égale à la complexité annoncée dans la spécification.

Jeu de tests possible

if __name__ == "__main__":
    p = Pile()
    p.empiler(2)
    print(p)
    p.empiler(42)
    p.empiler(89)
    p.empiler(23)
    print(p)
    print(p.depiler())
    print(p)
    print(p.depiler())
    print(p)
    print(p.depiler())
    print(p.depiler())
    print(p.depiler())
    print(p.depiler())

À retenir

À retenir

Une pile est une structure de données de type dernier entré, premier sorti (LIFO). Elle peut être implémentée facilement à l’aide d’une liste chaînée ou avec la structure de liste (tableau dynamique) de Python.

Exercices

Exercice 1
  • Compléter le code de la classe Pile (version liste chaînée) en ajoutant les méthodes vider et taille.
  • Évaluer approximativement le nombre d’opérations élémentaires de la structure Pile effectuées par la méthode taille.
Exercice 2

Pour améliorer la complexité de la méthode taille on ajoute l’attribut taille à la classe Pile.
Reprendre le code de la classe Pile en modifiant toutes les méthodes qui doivent l’être.

Solutions
Exercice 3

L’écriture polonaise inverse des expressions mathématiques place l’opérateur après ses opérandes. Cette notation ne nécessite ni l’utilisation des parenthèses ni la définition des règles de priorité des opérateurs. Ainsi l’expression l’expression (1+2×3)×4(1 + 2 \times 3) \times 4 s’écrit 1 2 3 × + 4 ×1\ 2\ 3\ \times\ +\ 4\ \times.

La valeur d’une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires. Pour cela, on observer un à un les éléments de l’expression et on effectue les actions suivantes :

  • si on voit un nombre, on le place sur la pile ;
  • si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l’opérateur, et on replace le résultat au sommet de la pile.

Si l’expression est bien écrite, il doit toujours y avoir deux nombres sur la pile lorsqu’un opérateur apparaît et à la fin du processus il ne doit rester qu’un seul nombre sur la pile. Ce nombre est le résultat.
L’opérateur unaire −- (l’opposé) devra être considéré comme un opérateur binaire dans cette implémentation : −3-3 sera donc écrit 0 3 −0\ 3\ -.

Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d’additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression. On supposera que les éléments de cette expression sont séparés par des espaces. Attention, cette fonction ne doit pas renvoyer de résultat si l’expression est mal écrite.

Solution
Physique, Chimie et Informatique > Terminales Spé. NSI > Piles et Files

Les Files

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

  • Son nom ;
  • Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.
Avertissement

Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé.
Un TDA peut être implémenté de plusieurs façons différentes.

Qu’est-ce qu’une file ?

Info

Une file est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des personnes dans une file d’attente (au guichet de la poste par exemple) :

  • à chaque fois qu’une personne arrive, elle se place à la fin de la file ;
  • lorsqu’un guichet se libère, c’est la personne arrivée en premier parmi celles qui attendent qui est servie.
Spécification d’une File de valeurs de type T
  • Créer une file (type) :
    • fonction : creer_file() ⟶\longrightarrow retourne une file vide ;
    • complexité : O(0)O(0) (pas tout à fait vrai mais suffisant pour comprendre la suite).
  • Enfiler une valeur à la fin de la file :
    • fonction : enfiler(f: File[T], valeur: T) ⟶\longrightarrow None ;
    • complexité : 1 opération élémentaire.
  • Accéder à la valeur située au début de la file :
    • fonction : lire(f: File[T]) ⟶\longrightarrow retourne la première valeur de la file ;
    • Complexité : 1 opération élémentaire.
  • Retirer la première valeur de la file :
    • fonction : defiler(f : File[T]) ⟶\longrightarrow T ;
    • complexité : 1 opération élémentaire.
  • Tester si une file est vide :
    • fonction : est_vide(f: File[T]) ⟶\longrightarrow retourne un booléen ;
    • complexité : 1 opération élémentaire.
Avertissement

La spécification d’une file montre qu’il n’existe aucune opération élémentaire pour :

  • accéder à une donnée qui n’est pas la première de la file ;
  • déterminer combien de données contient la file.
  • …
À retenir

La valeur retirée de la file est toujours la première valeur à l’avoir intégrée : First In, First Out (FIFO)

Jeu de tests possibles

if __name__ == "__main__":
    f = File()
    f.enfiler(1)
    f.enfiler(2)
    f.enfiler(3)
    f.enfiler(4)
    print(f.defiler())
    f.enfiler(5)
    print(f.defiler())
    print(f.defiler())
    print(f)
    print(f.defiler())
    print(f.defiler())
    print(f.defiler())

Implémentation d’une structure de file à l’aide d’une liste Python

L’idée est de définir le type File à l’aide d’une classe ne possédant qu’un seul attribut nommé contenu, qui référence une liste, puis de créer les méthodes de la spécification. On peut, par la suite, utiliser les méthodes des listes de Python.

  1. Définir une classe nommée File et faire en sorte qu’à l’initialisation de tout objet de type File, l’attribut contenu référence une liste vide.

  2. Écrire le code de la méthode est_vide de la spécification.

  3. Écrire le code de la méthode enfiler de la spécification.

  4. Écrire le code de la méthode defiler de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de défiler une file vide.

  5. Écrire le code de la méthode lire de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de lire une file vide.

  6. Tester le code.

  7. La complexité de chacune des méthodes est égale à la complexité annoncée dans la spécification ?

  8. Comment pourrait-on améliorer la complexité de la méthode defiler ? Modifier toutes les méthodes qui doivent l’être de façon à améliorer l’implémentation de la classe File.

Corrigé

Implémentation d’une structure de file à l’aide d’une liste chaînée

L’idée est de définir le type File à l’aide d’une classe ne possédant qu’un seul attribut nommé contenu, qui référence une liste chaînée, puis de créer les méthodes de la spécification.

  1. Écrire le code de la classe Cellule, cellule d’une liste chaînée.

  2. Définir une classe nommée File et faire en sorte qu’à l’initialisation de tout objet de type File, l’attribut contenu référence la liste vide.

  3. Écrire le code de la méthode est_vide de la spécification.

  4. Réfléchir au code de la méthode enfiler de la spécification et établir sa complexité.

  5. Afin de rendre le code performant, on utilise l’attribut queue. Cet attribut pointer toujours vers le dernier élément de la file.
    Ajouter l’attribut queue à la définition de la classe.

  6. Écrire le code de la méthode defiler de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de défiler une file vide.

  7. Écrire le code de la méthode lire de la spécification.
    Cette méthode doit lever une exception de type IndexError lorsqu’on essaie de lire une file vide.

  8. Tester le code.

Corrigé

Implémentation d’une structure de file à l’aide de deux piles

On considère dans cette partie le modèle d’un jeu de cartes où on disposerait d’une pioche, au sommet de laquelle on peut prendre des cartes (disposées face cachée), et d’une défausse au sommet de laquelle on peut reposer des cartes (disposées face apparente).
Chacun de ces paquets est une pile. Ils forment la réserve de cartes.
Les règles du jeu sont :

  • toute carte prise dans la réserve est retirée dans l’une de ces piles (la pioche) ;
  • toute carte remise dans la réserve est ajoutée à l’autre pile (la défausse). On doit ajouter à ces règles une relation entre les deux paquets : une fois la pioche vide, on retourne la défausse pour en faire une nouvelle pioche, laissant à la place une défausse vide.

Cette gestion des cartes correspond à une structure de file : une fois la pioche initiale vidée, les cartes sont piochées précisément dans l’ordre dans lequel elles ont été défaussées. La première défaussée est la première piochée (FIFO).

  1. Définir une classe nommée File et faire en sorte qu’à l’initialisation de tout objet de type File, les attributs entree et sortie soient créés en référencent deux piles vides.

  2. Écrire le code de la méthode est_vide de la spécification.
    Une file est vide lorsque les deux piles sont vides.

  3. Ajouter un nouvel élément à la file consiste à empiler cet élément sur la pile d’entrée. Écrire le code de la méthode enfiler de la spécification.

Pour retirer la valeur la plus ancienne dans la file deux cas sont à considérer :

  • la pile de sortie n’est pas vide : la valeur est la dernière de cette pile. Il suffit donc de dépiler la pile de sortie.
  • la pille de sortie est vide : il faut d’abord dépiler la pile d’entrée dans la pile de sortie puis dépiler cette pile de sortie.
  1. Écrire le code de la méthode defiler de la spécification.

  2. Écrire le code de la méthode lire de la spécification (le problème à considérer est très similaire à celui du retrait de la première valeur).

Corrigé

À retenir

À retenir

Une file est une structure de données de type premier entré, premier sorti (FIFO). Elle peut être implémentée facilement à l’aide d’une liste chaînée, avec la structure de liste (tableau dynamique) de Python ou à l’aide de deux piles.