C3.1 : Les piles

Mise en évidence

1) Tester le petit jeu suivant : ranger les assiettes.

2) Donner l'interface d'une structure de données que l'on pourrait utiliser pour programmer ce jeu.

Les piles

Présentation

Les piles sont des structures de données dites linéaires (ou séquentielles), les données qu'elles contiennent sont ordonnées.

Les piles se caractérisent par le fait que les données qu'elles contiennent se manipulent en respectant le principe « dernier arrivé, premier sorti » (en anglais LIFO pour last in, first out). Autrement dit, les éléments sont ajoutés et enlevés du même côté.

Exemples

Dans un logiciel, la possibilité d'annuler les dernières actions est gérée à l'aide d'une pile.

Interface

L'interface minimale des piles permet les actions suivantes :

  • - Créer une structure vide ;
  • - Tester si la structure est vide ;
  • - Ajouter un élément à la structure : empiler ;
  • - Enlever (en renvoyant) un élément à la structure : dépiler.

Implémentation

Rappel : Comme toutes les structures de données, les piles peuvent être implémentées par des classes (ce que nous verrons dans cette activité), mais également à l'aide de fonctions...

Implémentation d'une classe Pile en Python

A faire :

1) Proposer une implémentation, en python, de l'interface minimale (constructeur, est_vide, empile et depile) d'une classe Pile basée sur l'utilisation d'un attribut de type list.

2) Compléter le programme principal de façon à vérifier le bon fonctionnement des différentes méthodes de la classe.

Afficher la correction 
class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

# Programme principal
p1 = Pile()
print(p1.est_vide())
p1.empile(8)
p1.empile(10)
print(p1.est_vide())
print(p1.depile())
print(p1.depile())
print(p1.est_vide())

Application

Dans toute cette partie, on utilisera la classe Pile du III.

Application 1 : Manipulation des piles

On considère la situation A.

1) En utilisant les méthodes de la structure de données de type pile, proposer une suite d'opérations qui permet de passer de la situation A à la situation B.

2) Proposer une suite d'opérations qui permet de passer de la situation B à la situation C.

Application 2 : Création d'une pile avec les premiers entiers

1) Écrire une fonction cree_pile_1_n(n:int) ->Pile qui prend un nombre entier n en paramètre et renvoie une Pile contenant les nombres entiers empilées de 1 à n.

2) Compléter le programme principal pour vérifier le bon fonctionnement des deux fonctions.

Afficher la correction 
class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def cree_pile_1_n(n:int)->Pile:
    p = Pile()
    for i in range(1, n + 1):
        p.empile(i)
    return p

# Programme principal
p5 = cree_pile_1_n(5)
print(p5.depile())
print(p5.depile())
print(p5.depile())
print(p5.depile())
print(p5.depile())

Application 3 : Transfert des éléments d'une pile dans une autre pile

1) Écrire une fonction transfert_pile_a_pile(p1:Pile, p2:Pile)->Pile qui prend deux Piles en paramètres et transfert les éléments de la première dans la deuxième.

2) Compléter le programme principal pour vérifier le bon fonctionnement des deux fonctions.

Afficher la correction 
class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def transfert_pile_a_pile(p1:Pile, p2:Pile)->Pile:
    while not p1.est_vide():
        p2.empile(p1.depile())

# Programme principal
pile1 = Pile()
pile1.empile(1)
pile1.empile(2)
pile1.empile(3)

pile2 = Pile()

transfert_pile_a_pile(pile1, pile2)

print(pile1.est_vide())
print(pile2.est_vide())
print(pile2.depile())
print(pile2.depile())
print(pile2.depile())
print(pile2.est_vide())

Application 4 : Nombre d'éléments d'une pile

Écrire une fonction long(p:Pile)->int qui :

Remarque : cette fonction ne devra pas avoir d'effet de bords.

Afficher la correction 
class Pile:
    def __init__(self):
        self.__valeurs = []

    def est_vide(self):
        return len(self.__valeurs) == 0

    def empile(self, val):
        self.__valeurs.append(val)

    def depile(self):
        if not(self.est_vide()):
            return self.__valeurs.pop()
        else:
            return None

def long(p:Pile) -> int:
    p0 = Pile()
    lg = 0
    # dépilage de p pour compter le nombre d'éléments
    while not p.est_vide():
        lg = lg + 1
        p0.empile(p.depile())
    # rempilage dans p pour que p retrouve son état initial
    while not p0.est_vide():
        p.empile(p0.depile())
    return lg

p1 = Pile()
print(long(p1))
p1.empile(1)
print(long(p1))
p1.empile(1)
print(long(p1))
p1.depile()
print(long(p1))