Les piles et les files

Numérique et sciences informatiques

donnees

Les piles

Les piles sont fondées sur le principe du « dernier arrivé, premier sorti » ; on les dit de type LIFO (Last In,First Out). C’est le principe même de la pile d’assiette : c’est la dernière assiette posée sur la pile d’assiettes sales qui sera la première lavée.

pile
Pile : LIFO

Une réalisation concrète de la structure pile doit fournir dans l’idéal :

Action Instruction
Créer une pile P vide creer_pile_vide()
tester si une pile est vide est_vide(ma_pile) renvoie vrai si la pile pile est vide
Insérer un nouvel élément e au sommet de la pile Pile(push) empiler(ma_pile,e)
Enlever et retourner l'élément au sommet de la pile Pile (pop) depiler(ma_pile)
Compter le nombre d'éléments présents dans une pile Pile taille(ma_pile)
Créer une nouvelle pile ma_pile_2 à partir d'un élement x d'une pile existante ma_pile ma_pile_2 = cons(x,ma_pile)

Entraînement 2 :

Donner le contenu de ma_pile et de temp après cette série d'instruction :

ma_pile = creer_pile_vide()
empiler(ma_pile,3)
empiler(ma_pile,2)
temp = depiler(ma_pile)
empiler(ma_pile,5)
empiler(ma_pile,7)
empiler(ma_pile,9)

Implémentation en python

class Pile:
    """Classe définissant une structure de pile."""
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        """Renvoie le booléen True si la pile est vide, False sinon."""
        return self.contenu == []

    def empiler(self, elt):
        """Place l'élément elt au sommet de la pile"""
        self.contenu.append(elt)

    def depiler(self):
        """
        Retire et renvoie l’élément placé au sommet de la pile,
        si la pile n’est pas vide.
        """
        if not self.est_vide():
            return self.contenu.pop()


pile_1 = Pile()
pile_1.empiler(2)
pile_1.est_vide()
pile_1.empiler(1)
pile_1.empiler(2)
pile_1.empiler(3)
print(pile_1.contenu)
print(pile_1.est_vide())
print(pile_1.depiler())


Un exemple de classe python pour les piles avec POO (lvl 2)

Les Files

Une file est une structure linéaire dans laquelle les éléments sont ajoutés à une extrémité (le derrière de la file) et retirés de l'autre extrémité (le devant de la file). Elle fonctionne selon le principe FIFO (First In, First Out), c'est-à-dire que le premier élément ajouté à la file sera également le premier à en être retiré.

file
File : FIFO

Une réalisation concrète de ces structures doit fournir dans l’idéal :

  • une fonction de création d’une file vide ;
  • deux fonctions d’ajout et de suppression;
  • une fonction vérifiant si une file est vide.


on peut réaliser les opérations suivantes sur un objet de type File:

Action Instruction
Création de la file : On crée une file vide. creer_file_vide()
Tester si la file est vide : Vérifier si la file contient des éléments. est_vide(ma_file) renvoie vrai si la pile pile est vide
Enfiler (enqueue) : Ajouter un élément à la fin de la file. enfiler(ma_file,elt)
Défiler (dequeue) : Retirer et renvoyer l'élément du début de la file. defiler(ma_file)
Taille de la file : Obtenir le nombre d'éléments dans la file. taille(ma_file)

2. Implémentation d'une File en Python

Pour manipuler une file en Python, on peut utiliser la classe deque de la bibliothèque collections, qui permet d'ajouter ou de retirer des éléments de façon efficace.


from collections import deque

def creer_file_vide():
    """Crée une file vide."""
    return deque()

def est_vide(file):
    """Vérifie si la file est vide."""
    return len(file) == 0

def enfiler(file, elt):
    """Ajoute un élément à la fin de la file."""
    file.append(elt)

def defiler(file):
    """Retire et renvoie l'élément du début de la file."""
    if not est_vide(file):
        return file.popleft()  # Retire et retourne le premier élément
    return None

def taille(file):
    """Renvoie le nombre d'éléments dans la file."""
    return len(file)

3. Exemples d'Utilisation

Voici un exemple de programme qui utilise ces fonctions pour gérer une file :


# Création d'une file vide
ma_file = creer_file_vide()

# Enfiler des éléments
enfiler(ma_file, 3)
enfiler(ma_file, 2)

# Tester la taille de la file
print("Taille de la file:", taille(ma_file))  # Affiche 2

# Défiler un élément
temp = defiler(ma_file)
print("Élément défiler:", temp)  # Affiche 3

# Enfiler de nouveaux éléments
enfiler(ma_file, 5)
enfiler(ma_file, 7)
enfiler(ma_file, 9)

# Afficher le contenu de la file
print("Contenu de la file:", ma_file)  # Affiche [2, 5, 7, 9]

4. Exercices d'Entraînement

Entraînement 1 : Manipulation de base des files

Objectif : Enfiler plusieurs éléments dans une file et vérifier la taille.

Instructions :

  • Créez une file vide.
  • Enfilez les éléments 10, 20, 30, 40.
  • Affichez la taille de la file après chaque ajout.

Questions :

  • Quelle est la taille de la file après chaque ajout ?
  • Quel est l'ordre des éléments dans la file à la fin ?

Entraînement 2 : Défiler des éléments

Objectif : Défiler les éléments d'une file.

Instructions :

  • Créez une file contenant les éléments 5, 10, 15, 20.
  • Défilez deux éléments et affichez le contenu de la file après chaque défilement.

Questions :

  • Quelle valeur contient la variable temp après chaque opération de défilement ?
  • Comment évolue le contenu de la file après chaque défilement ?

Entraînement 3 : Cas pratique

Objectif : Suivre une série d'actions sur une file.

Instructions :


ma_file = creer_file_vide()
enfiler(ma_file, 3)
enfiler(ma_file, 2)
temp = defiler(ma_file)
enfiler(ma_file, 5)
enfiler(ma_file, 7)
enfiler(ma_file, 9)

Questions :

  • Donnez le contenu de ma_file à la fin de l'exécution.
  • Que contient la variable temp après l'exécution ?

Entraînement 4 : Test de la file vide

Objectif : Tester si la file est vide après différentes opérations.

Instructions :

  • Créez une file vide.
  • Enfilez l'élément 100.
  • Défilez un élément.
  • Testez si la file est vide après chaque opération.

Questions :

  • Quelle méthode permet de tester si une file est vide ?
  • Quelle est la sortie des tests effectués ?

5. Applications des Files

Les files sont utilisées dans divers contextes informatiques, notamment :

  • Gestion des tâches : Les systèmes d'exploitation utilisent des files pour gérer les tâches (processus en attente).
  • Réseaux : Les paquets de données peuvent être traités en utilisant des files pour organiser leur transmission dans un ordre correct.
  • Simulations : Les files sont utilisées dans les simulations de systèmes tels que les caisses dans un supermarché.

6. Conclusion

Les files sont des structures de données très utiles et simples à comprendre. Leur gestion efficace est essentielle dans de nombreux domaines de l'informatique, notamment la gestion des processus, des événements, et des ressources. Grâce à ce chapitre, vous avez appris à créer, manipuler et tester des files à l'aide de Python.

N'oubliez pas de vous entraîner avec les exercices pour bien maîtriser l'utilisation des files !

Entraînement 3 :

Donner le contenu de ma_file et de temp après cette série d'instruction :

ma_file = creer_file_vide()
enfiler(ma_file,3)
enfiler(ma_file,2)
temp = defiler(ma_file)
enfiler(ma_file,5)
enfiler(ma_file,7)
enfiler(ma_file,9)

Implémentation en python

###########################################
#Extrait de la documentation python
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           # Terry arrives
queue.append("Graham")          # Graham arrives
queue.popleft()                 # The first to arrive now leaves
print(queue)
queue.popleft()                 # The second to arrive now leaves
print(queue)                    # Remaining queue in order of arrival
print("-----------------------------------------")


##################################################################

class File:
    def __init__(self):
        """Création de la file"""
        self.contenu = []

    def est_vide(self):
        """Teste si la file est vide et renvoie le booléen obtenu"""
        return self.contenu == []

    def enfiler(self, e):
        """Ajoute un élément à la fin de la file"""
        self.contenu.append(e)

    def defiler(self):
        """Supprime et renvoie le premier élément de la file"""
        return self.contenu.pop(0)

    def taille(self):
        """Renvoie le nombre d'éléments de la file"""
        return len(self.contenu)




def creer_file():
    """création de la file"""
    return[]

def est_vide(file):
    """teste si file est vide et renvoie le booléen obtenu"""
    return (file == [])

def enfiler(e,file):
    """file.append(e)"""
    file[len(file):] = [e]

def defiler(file):
    """return file.pop(0)"""
    del file[0]

def taille(file):
    """Renvoie le nombre d'élément de la file"""
    return len(file)

#########################################################
f = creer_file()
enfiler(1,f)
print(f)
enfiler(2,f)
enfiler(3,f)
print(f)
est_vide(f)
defiler(f)
print(f)
defiler(f)
defiler(f)
print(f)
print(est_vide(f))

Un exemple de classe python pour les files avec POO (lvl 2)


Entraînement 6 : proposer une fonction qui vide une file


Entraînement 7 : Exercices extraits de sujet de bac

  1. Jeu de la poussette : D'après 2022, Métropole, J2, Ex. 2
  2. Vérification syntaxique de parenthèses ou de balises : D'après 2022, Métropole, J1, Ex. 1
  3. Pile, file, programmation Python D'après l'exercice 5 du sujet Amérique du Nord J1 - 2021
  4. Traitement d'une pile : D'après 2022, Polynésie, J1, Ex. 4
  5. Traitement d'une pile D'après 2021, Centres Étrangers, J1, Ex. 5

Savoir faire

  • Savoir spécifier une structure de données par son interface.
  • Savoir distinguer interface et implémentation.
  • Savoir écrire plusieurs implémentations d’une même structure de données.
  • Savoir distinguer des structures par le jeu des méthodes qui les caractérisent.
  • Savoir choisir une structure de données adaptée à la situation à modéliser.

Fiche de cours