TP1-PROG-10 - Les Piles#

Les piles sont des structures de données proches des listes. Elles permettent de gérer l’arrivé et le départ de ses éléments.

Définition : La pile#

La pile est une structure de données qui permet de gérer un ensemble d’éléments et leurs arrivées et départs dans le temps.

Dans une pile d’assiettes, il est possible d’accéder uniquement à la dernière ajoutée: celle qui se trouve au sommet.

Il n’est donc possible d’effectuer que les opérations suivantes :

  • créer une nouvelle pile vide

  • empiler un nouvel élément

  • récupérer un élément au sommet de la pile

Dans une pile, le dernier élément ajouté est le premier que l’on peut enlever

Cette structure s’appelle LIFO (Last In First Out en anglais)

Les opérations sur une pile en Python#

Ajouter un élément#

On ajoute un élément avec la fonction append() et on le supprime avec la fonction pop(). Simulons une pile avec des livres que nous avons sur notre bureau.

Commençons avec une pile vide.

pile = []

Nous allons maintenant ajouter 3 livres sur la pile, en utilisant la fonction append().

pile.append('Zola')
pile.append('Balzac')
pile.append('Hugo')

Voici la pile actuelle

pile

['Zola', 'Balzac', 'Hugo']

Enlever un élément#

Dans une pile, le seul livre qui peut être enlevé est le dernier ajouté. Nous utilisons la fonction pop() pour enlever un livre.

pile.pop()

'Hugo'

Mettons 3 autres livres sur la pile.

pile.append('Frisch')
pile.append('Murakami')
pile.append('Higgins')

Enlevons-en un.

pile.pop()

'Higgins'

Combien de livres restent sur la pile ?

len(pile)

4

Lesquels?

pile

['Zola', 'Balzac', 'Frisch', 'Murakami']

Exercice 1 : Fonctions d’ajout et de suppression#

Il est possible de simplifier les deux primitives

  1. ajouter un élément

  2. enlever un élément

à l’aide d’une fonction (un sous-programme). Chaque fonction prendra comme argument une pile. Cela permet

  • de pouvoir gérer plusieurs piles en même temps

  • de s’affranchir de la notion d’index

A vous de définir les deux fonctions ayant les signatures suivantes :

def ajouter(pile,element):
    # Modifier la méthode suivante
    pile.extend(element)

def supprimer(pile):
    # modifier les méthodes suivantes
    element = pile[len(pile)]
    print("Element supprimé : ",element)
    pile.pop(1)

Indication : Pour atteindre le dernier élément ajouté à la pile, il faut analyser le nombre d’éléments dans la pile et la correspondance avec l’index (longueur - 1)

Afficher les éléments#

Essayons d’afficher la pile des livres.

for livre in pile:
    print(livre)

Zola
Balzac
Frisch
Murakami

Le problème avec cette façon d’imprimer c’est que la pile n’est pas dans le bon ordre. Nous pouvons utiliser l’opérateur de tranche [::-1] pour inverser l’ordre d’une liste.

for livre in pile[::-1]:
    print(livre)

Murakami
Frisch
Balzac
Zola

Exercice 1bis (facultatif) : Fonction d’affichage de l’état de la pile#

Ecrivez une fonction qui affiche l’état d’une pile donnée en argument. L’affichage se fera selon l’ordre “logique” (le premier élément ajouté se trouve au bas de la pile)

Exercice 2 : Tour de Hanoï#

Connaissez-vous l’énigme des Tours de Hanoï ? C’est un jeu de réflexion qui consiste à déplacer des disques de diamètre différent d’une tour de départ à une tour d’arrivée en utilisant une tour intéremédiaire. Visuellement, l’état de départ ressemble à ceci :

hanoi_debut

Et l’objectif est d’arriver sur la tour de droite en passant par celle du milieu. L’entier de la solution est la suivante :

hanoi

  1. Décrivez l’algorithme de la solution avec un algorigramme (sur papier)

    1. Observez les différences (nombre de disques pair, impair) et similitudes (déplacements)

  2. Implémentez une fonction deplacer(pileDepart, pileArrivee) qui permet de déplacer nu disque

    1. Définissez 3 piles : p1, p2 et p3

    2. Utilisez vos fonctions ajouter(pile, element), supprimer(pile) et afficher(pile) de l’exercice 1

  3. Implémentez l’algorithme pour résoudre le problème des tours de Hanoï

  4. Vérifiez que votre algorithme fonctionne avec un nombre quelconque de disques