Piles

3.4.1. Piles#

3.4.1.1. Présentation sommaire#

Une pile est une structure de données organisée suivant le principe du dernier arriver, premier parti. On utilise souvent l’acronyme anglais LIFO : Last In, First Out.

Pile d'assiette

Il faut se représenter une pile d’assiette manipulée par un enfant : celui-ci n’a pas le droit de prendre plus de deux assiettes simultanément. Il ne peut donc prendre que la première assiette, celle du dessus de la pile. De même, il ne peut que poser une assiette sur le haut d’une pile.

On considère qu’il peut créer des piles et que certaines piles sont vides (il faut imaginer un emplacement vide dans le placard).

3.4.1.2. Quatre primitives essentielles#

  • Créer une Pile

P = Pile()

  • Est vide

P.est_vide()

True

  • Empiler

P.empiler(1)

P.empiler(2)

  • Dépiler

P.depiler()

2

type(P)

cours.structures.Pile

3.4.1.3. Exercices#

Écrire une classe qui permet de modéliser une pile.

class Pile:
  pass

p = Pile()
assert p.est_vide() == True
assert p.empiler(1) == None
assert p.est_vide() == False
assert p.empiler(2) == None
assert p.depiler() == 2
assert p.est_vide() == False
assert p.depiler() == 1
assert p.est_vide() == True

Compléter la classe avec une méthode len (on écrira _len pour éviter de redéfinir la fonction len() de Python.)

Hide code cell content 
def _len(self):
    return len(self._L)

p = Pile()
for i in range(10):
    p.empiler(1)
assert p.len() == 10
p = Pile()
for i in range(24):
    p.empiler(i)
assert p.len() == 24

Écrire une méthode top permettant de renvoyer l’élément de tête de la pile (sans le dépiler)

Hide code cell content 
def top(self):
    return self._L[-1]

p = Pile()
for i in range(16):
    p.empiler(i**2)
assert p.top() == 225

Écrire une méthode clear permettant de vider la pile.

Hide code cell content 
def clear(self):
    self._L = []

p = Pile()
for i in range(10):
    p.empiler(i**2)
p.clear()
assert p.est_vide() == True

Écrire une méthode dup permettant de dupliquer l’élément de tête

Hide code cell content 
def dup(self):
    self.empiler(self.top())

p = Pile()
for i in range(10):
    p.empiler(i**2)
p.dup()
assert p.depiler() == p.depiler()

Écrire une méthode swap permettant d’échanger les deux éléments du sommet de la pile

Hide code cell content 
def swap(self):
    if len(self._L) < 2:
        raise Exception('La taille de la pile doit être ≥ 2')
    self._L[-1],self._L[-2] = self._L[-2],self._L[-1]

p = Pile()
for i in range(10):
    p.empiler(i**2)
p.swap()
assert p.depiler() == 64
assert p.depiler() == 81
p = Pile()
p.empiler(1)
try:
    p.swap()
except Exception as msg: 
    print(msg) 

La taille de la pile doit être ≥ 2

On a désormais la classe «complète»

Hide code cell outputs 
class Pile:
    """
    Une classe pour avoir une interface basique de pile
    """
    def __init__(self):
        """
        Initialisation d'une variable interne
        """
        self._liste = []

    def __repr__(self):
        return f"{self._liste}"

    def empiler(self, a):
        self._liste = self._liste + [a]

    def depiler(self):
        return self._liste.pop()

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

    def len(self):
        return len(self._liste)

    def top(self):
        return self._liste[-1]

    def clear(self):
        self._liste = []

    def dup(self):
        self.empiler(self.top())

    def swap(self):
        if len(self._liste) < 2:
            raise Exception("La taille de la pile doit être ≥ 2")
        self._liste[-1], self._liste[-2] = self._liste[-2], self._liste[-1]
Contenu