Piles et Files

1. Introduction

Les listes Python sont très souples, mais en informatique, on a souvent besoin de structures plus contraintes pour gérer des données de manière spécifique. Deux structures fondamentales sont :

• La Pile (Stack)
• La File (Queue)

2. La Pile (Stack) - LIFO

Opérations (Interface)

Une Pile doit permettre de :

• empiler(e) (push) : Ajouter un élément au sommet.
• depiler() (pop) : Retirer l'élément du sommet.
• sommet() (peek) : Regarder l'élément du sommet sans le retirer.
• est_vide() : Savoir si la pile est vide.

Exemple d'exécution

P = Pile()      # []
P.empiler(10)   # [10]
P.empiler(20)   # [10, 20] (Sommet = 20)
x = P.depiler() # x vaut 20, P redevient [10]

3. La File (Queue) - FIFO

Opérations (Interface)

Une File doit permettre de :

• enfiler(e) (enqueue) : Ajouter un élément à la queue.
• defiler() (dequeue) : Retirer l'élément de la tête.
• tete() : Regarder le premier élément.
• est_vide() : Savoir si la file est vide.

Exemple d'exécution

F = File()      # []
F.enfiler(A)    # [A]
F.enfiler(B)    # [A, B] (Tête = A, Queue = B)
x = F.defiler() # x vaut A, F devient [B]

4. Implémentation en Python (POO)

Bien que les listes Python puissent servir de piles/files, il est pédagogique de créer nos propres classes pour respecter strictement l'interface.

Classe Pile

class Pile:
    def __init__(self):
        self.data = []
        
    def est_vide(self):
        return len(self.data) == 0
        
    def empiler(self, element):
        self.data.append(element)
        
    def depiler(self):
        if not self.est_vide():
            return self.data.pop()
        return None

Classe File

class File:
    def __init__(self):
        self.data = []
        
    def est_vide(self):
        return len(self.data) == 0
        
    def enfiler(self, element):
        self.data.append(element)
        
    def defiler(self):
        if not self.est_vide():
            # pop(0) retire le premier élément (indice 0)
            return self.data.pop(0) 
        return None