Voyez-vous le point commun entre la façon dont vous avez rangé votre lave-vaisselle et la gestion de l’historique de votre navigateur ? Entre la façon dont vous avez rangé vos courses dans votre réfrigirateur et la façon dont votre ordinateur choisit à quel processus allouer du temps de calcul ?

I. Les Piles

1. Définition et utilisation

Une Pile, Stack en anglais (comme Stack Overflow !), est une structure de données reposant sur le modèle du Last In, First Out (LIFO), ou Dernier Entré, Premier Sorti (DEPS) en français.

La façon la plus simple de se représenter une pile est une pile (!) d’assiettes : lorsqu’on les range, on empile les assiettes les unes sur les autres. Lorsque l’on met la table, on pioche dans la pile en commençant par le dessus et donc par la dernière assiette rangée !

On le voit, la pile en soit n’a donc qu’un seul attribut : sa tête, son premier élément.

La pile intervient très souvent dans la vie quotidienne et en programmation :

• la façon dont un professeur pioche la prochaine copie à corriger (le dernier élève à rendre est le premier corrigé !)
• la gestion d’un camion de livraison : on charge dans l’ordre inverse de la livraison, le dernier carton chargé est le premier livré
• le ctrl-Z de l’ordinateur
• la gestion de l’historique de navigation sur internet
• déterminer si une expression compte le bon nombre de parenthèses (on empile les ouvrantes et dépile les fermantes, voir plus bas)

2. Implémentation

Les méthodes primitves essentielles d’une pile sont :

• creation : crée et retourne une pile vide
• est_vide : indique si la pile est vide ou non
• empiler : ajoute un élément en haut de la pile. Les anglo-saxons disent push
• depiler : retire, et retourne, le premier élément de la pile. Les anglo-saxons disent pop

Il est aussi possible d’ajouter les méthodes suivantes mais qui ne sont pas indispensables :

• taille : retourne le nombre d’éléments dans la pile
• tete : retourne le premier élément sans le dépiler
• vider : dépile tous les éléments

Il existe plusieurs implémentations des piles. On peut utiliser des tableaux ou des listes chaînées par exemple. Nous faisons le choix ici d’utiliser des listes chaînées.

Voici une implémentation possible (qui ressemble beaucoup à celle d’une liste chaînée) :

creation() :
  pile.tête = null

  Retourne pile

est_vide(pile) :
  Si pile.tête == null :
    Retourne VRAI
  Sinon :
    Retourne FAUX

empiler(pile, nouveau) :
  nouveau.successeur = pile.tête
  pile.tête = nouveau

depiler(pile) :
  Si est_vide(pile) :
    Retourne ERREUR
  Sinon :
    top = pile.tête
    pile.tête = pile.tête.successeur
    Retourne top

Remarque : On peut aussi coder les piles à l’aide de tableaux. Dans ce cas, la tête est toujours l’élément d’indice 0. Voici un exemple d’implémentation :

creation() :
  pile = []
  Retourne pile

est_vide(pile) :
  Si longueur(pile) == 0 :
    Retourne VRAI
  Sinon :
    Retourne FAUX

empiler(pile, nouveau) :
  Insérer nouveau au début de pile

depiler(pile) :
  Si est_vide(pile) :
    Retourne ERREUR
  Sinon :
    top = pile[0]
    Supprimer pile[0] de la pile
    Retourner top

En python on obtient pour l’implémentation avec les listes chaînées :

class Element:
    """
    Classe décrivant les éléments utilisés dans les piles et files
    Un élément possède :
        - une donnée (de type quelconque)
        - un successeur (un autre élément)
    """

    def __init__(self, donnee):
        self.donnee = donnee
        self.successeur = None

    def afficher(self):
        print(str(self.donnee) + " --> " + str(self.successeur), end="\n\n")


class Pile:
    """
    Classe implémentant une pile à l'aide d'une liste chaînée
    """

    def __init__(self):
        """
        Constructeur
        Retourne une pile vide
        """
        self.tete = None

    def est_vide(self):
        """
        Teste si la pile est vide
        Renvoie True ou False selon la réponse
        """
        return self.tete == None

    def empiler(self, donnee):
        """
        Empile une nouvelle donnée à l'aide d'un élément sur la pile
        """
        element = Element(donnee)
        element.successeur = self.tete
        self.tete = element

    def depiler(self):
        """
        Dépile et retourne la première valeur de la pile
        Si la pile est vide, renvoie une erreur 
        """
        if self.est_vide():
            raise Exception('La liste est vide !')
        else:
            top = self.tete
            self.tete = self.tete.successeur

            return top.donnee

    def afficher(self):
        """
        Affichage de la liste
        """
        if self.est_vide():
            print("La pile est vide")
        else:
            s = ""

            pointeur = self.tete

            while pointeur != None:
                s += " --> " + str(pointeur.donnee)
                pointeur = pointeur.successeur

            print(s, end="\n\n")

On peut alors tester les parenthèses dans une chaîne de caractères :

def parentheses_correctes(chaine) :
    """
    Détermine si une chaîne de caractère est bien formée du point de vue des parenthèses
    Par exemple "(())" est bien formée mais pas "())" ni "(()"
    On empile un élément à chaque parenthèse ouvrante et on dépile à chaque fermante
    Si on termine la fonction avec une pile vide, la chaîne est bien formée
    Sinon ou si on a essayé de dépiler une chaîne vide, la chaîne est mal formée
    """
    pile = Pile()

    for caractere in chaine :
        if caractere == "(" :
            pile.empiler(1)
        elif caractere == ")" :
            if pile.est_vide() :
                return False
            else :
                pile.depiler()
    
    return pile.est_vide()

print(parentheses_correctes("(())"))

II. Les Files

1. Définition et utilisation

Une File, Queue en anglais, est une structure de données reposant sur le modèle du First In, First Out (FIFO), ou Premier Entré, Premier Sorti (PEPS) en français.

La façon la plus simple de se représenter une file est la queue à un guichet : la première personne arrivée sera la première servie.

La file a deux attributs : une tête (le premier élément, prochain à sortir) et une queue (dernier élément qui vient d’être inséré).

Voici des exemple d’utilisation de files :

• file d’attente
• gestion des appels dans un standart
• gestion des tâches par le processeur
• tri des paquets lors d’une transmission asynchrone (les paquets des différents messages arrivent dans le désordre, ils sont réassemblés au fur et à mesure dans leur ordre d’arrivée)

2. Implémentation

Les méthodes primitves essentielles d’une file sont :

• creation : crée et retourne une file vide
• est_vide : indique si la file est vide ou non
• enfiler : ajoute un élément à la queue de la file. Les anglo-saxons disent enqueue
• defiler : retire, et retourne, le premier élément de la pile. Les anglo-saxons disent dequeue

Une implémentation en utilisant les listes chaînées est la suivante :

creation() :
  file.tête = null
  file.queue = null

  Retourne file

est_vide(file) :
  Si file.tête == null :
    Retourne VRAI
  Sinon :
    Retourne FAUX

enfiler(pile, nouveau) :
  file.queue = nouveau
  nouveau.successeur = null

defiler(file) :
  Si est_vide(file) :
    Retourne ERREUR
  Sinon :
    top = file.tête
    file.tête = file.tête.successeur
    Retourne top

Une autre implémentation avec des tableaux donne :

creation() :
  file = []

  Retourne file

est_vide(file) :
  Si longueur(file) == 0 :
    Retourne VRAI
  Sinon :
    Retourne FAUX

enfiler(pile, nouveau) :
  Insérer nouveau à la fin de file

defiler(file) :
  Si est_vide(file) :
    Retourne ERREUR
  Sinon :
    top = file[0]
    Supprimer file[0] de file
    Retourne top

L’implémentation avec les listes chaînées donne en python :

class File:
    """
    Classe implémentant une file à l'aide d'une liste chaînée
    """

    def __init__(self):
        """
        Constructeur
        Retourne une file vide
        """
        self.tete = None
        self.queue = None

    def est_vide(self):
        """
        Teste si la file est vide
        Renvoie True ou False selon la réponse
        """
        return self.tete == None

    def enfiler(self, donnee):
        """
        Enfile une nouvelle donnée à l'aide d'un élément sur la file
        """
        element = Element(donnee)
        if self.est_vide() :
            self.tete = element
            self.queue = element
        else :
            self.queue.successeur = element
            self.queue = element

    def defiler(self):
        """
        Défile et retourne la première valeur de la file
        Si la file est vide, renvoie une erreur 
        """
        if self.est_vide():
            raise Exception('La file est vide !')
        else:
            top = self.tete
            self.tete = self.tete.successeur

            return top.donnee

    def afficher(self):
        """
        Affichage de la file
        """
        if self.est_vide():
            print("La pile est vide")
        else:
            s = ""

            pointeur = self.tete

            while pointeur != None:
                s += " --> " + str(pointeur.donnee)
                pointeur = pointeur.successeur

            print(s, end="\n\n")

On peut en utilsant une pile et une file, tester si un chaîne est un palyndrome :

• on remplit une pile et une file avec les caractères dans l’ordre
• on dépile un caractère et on défile un caractère puis on les compare : s’ils sont différents, la chaîne n’est pas un palyndrome
• si on arrive à la fin de la pile/file sans erreur c’est que la chaîne est un palyndrome

def palyndorme(chaine):
    """
    Teste si une chaîne de caractères est un palyndrome (comme "radar" par exemple)
    On ôte les espaces avant d'empiler/enfiler et on ne tient pas compte des majuscules
    chaine est une chaîne de caractères
    Retourne True ou False selon que la chaîne est un palyndrome ou non
    """
    p = Pile()
    f = File()

    for caractere in chaine:
        if not caractere.isspace():
            p.empiler(caractere.lower())
            f.enfiler(caractere.lower())

    while not p.est_vide():
        if p.depiler() != f.defiler() :
            return False

    return True

print(palyndorme("Hello World"))
print(palyndorme("Esope reste ici et se repose"))

3. Une file = deux piles !

Il est possible d’implémenter une file à l’aide de deux piles : une pile de stockage et une de déstockage.

Lors de l’insertion d’une valeur dans la file, on empile sur la pile de stockage.

Lorsque l’on souhaite défiler une valeur, on constate qu’elle est inaccessible sur la pile stockage : il faut en effet dépiler la dernière valeur, tout au fond de la pile…

C’est là qu’intervient la pile de déstockage : on dépile tous les éléments de stockage vers déstockage. Cette seconde pile contient alors les mêmes éléments mais dans l’ordre contraire. On peut alors dépiler le premier élément de déstockage (qui était le dernier de stockage). Ceci fait, on rempile tous les éléments de déstockage sur stockage.

III. Comparaison des implémentations

La lecture des pseudo-codes peut laisser penser que l’implémentation à l’aide de tableaux (des listes en python) est plus simple à mettre en place que l’utilisation de listes chaînées. C’est en effet le cas.

Mais, dans bien des langages de programmation, lors de la création d’un tableau, on doit en préciser la taille et le type (on crée par exemple un tableau de 50 entiers).

Remarque : ce n’est pas le cas en python car le “langage” adapte automatiquement la taille des listes en fonction du nombre d’élément, lors des insertions il est parfois amené à recopier l’ensemble de la liste dans un nouveau tableau (voir ce site).

Les listes chaînées, elles, n’ont pas de taille fixes : elles peuvent être de longueur quelconque ce qui est un point avantageux pour cette implémentation.

En terme de temps d’accès à un élément, dans un tableau de taille \(n\), l’accès à un élément se fait en temps constant, complexité \(O(1)\). En effet la position de l’élement dans la mémoire de l’ordinateur est directement calculée à partir de son indice et de celle du premier élément du tableau.

Pour une liste chaînée, dans la mesure où chaque élément contient un pointeur vers le suivant, afin de trouver une élément il faut tous les lire jusqu’à trouver celui cherché. On est en complexité linéaire \(O(n)\). Si la liste ets deux fois plus longue, une recherche prendra environ deux fois plus de temps.

Sur ce plan, c’est l’implémentation à l’aide des tableaux qui est plus intéressante.