Terminale - Piles et Files

Introduction

Dans ce chapitre, on s'intéresse aux structures de données linéaires, autrement dit la façon de représenter des données "qui se suivent". En Python, la structure de données linéaire la plus connue est bien entendu la liste.

Comme tout langage de haut-niveau, Python permet de faire les choses simplement. Si je souhaite créer une liste de nombres et de chaînes de caractères, c'est très simple :

    liste = [1, 3.14, "bonjour"]

Dans un langage bas-niveau comme le C, les listes n'existent pas : on dispose à la place de tableaux, dont les différences avec les listes sont notables.

les tableaux sont constitués d'une suite de variables de même type stockés sur des emplacements consécutifs dans la mémoire de l'ordinateur. Il s'agit d'une structure statique : la quantité de mémoire allouée au stockage d'un tableau est fixée au moment de sa création. Pour accéder au contenu d'une des données du tableau, il suffit de connaitre l'emplacement $d$ du début du tableau dans la mémoire, la taille $k$ occupée en mémoire par une donnée, et de se déplacer jusqu'à l'emplacement $d + kp$, où $p$ est la position de l'élément dans le tableau. L'algorithme d'accès est à temps constant, c'est à dire qu'il est identique pour tous les éléments du tableau.
les listes sont nettement plus complexes car il s'agit d'une structure de données dynamique (la taille mémoire est modifiable en permanence, c'est une des raisons pour lesquelles on peut sans problème créer en Python des listes contenant des données de types incohérents). En pratique, chaque élément de la liste est stocké en mémoire en deux parties : la donnée elle- même, et un pointeur vers l'emplacement mémoire de la donnée suivante (ou vers une valeur particulière indiquant la fin de la liste). L'accès à un élément de la liste demande donc a priori un temps d'autant plus grand qu'il se situe loin dans la liste (il faut passer par tous les éléments précédents). On a donc un algorithme d'accès qui est linéaire : si la taille de la liste double, le temps d'exécution peut-être doublé dans le pire des cas.

En termes simplifiés, les données sont parfaitement ordonnées dans la mémoire avec les tableaux, et disposés un peu n'importe où avec les listes. Pour définir un tableau en Python, on peut par exemple utiliser le type array du module numpy.

Comme les tableaux, il existe 2 autres structures linéaires dont les accès mémoire sont optimisés : il s'agit des piles et des files.

Les piles

Une pile est une structure de données linéaire qui donne accès en priorité aux dernières données ajoutées. Ainsi, la dernière information ajoutée sera la première à en sortir. Autrement dit, on ne peut accéder qu'à l'objet situé au sommet de la pile.

On décrit souvent ce comportement par l'expression "dernier arrivé, premier sorti" ou encore LIFO pour Last In, First Out. Le principe est celui d'une pile d'assiettes.

Une pile d'assiettes est un exemple de pile !

Cette structure dispose de deux opérations élémentaires :

empiler(x) : correspond à l'insertion de la donnée x au sommet de la pile
depiler() : retire la dernière donnée de la pile et la retourne

Opérations élémentaires : empiler et dépiler

On peut également définir d'autres opérations comme :

est_vide() : retourne True si la pile est vide, False sinon
est_pleine() : retourne True si la pile est pleine, False sinon
sommet() : retourne le sommet de la pile, sans le dépiler
vider() : vide entièrement la pile, en retournant la liste des éléments dépilés

Implémentation

On peut réaliser une pile P de taille $n$ à partir d'une liste L de $n+1$ éléments, de la manière suivante :

le premier élément de L, L[0], représente le nombre d'éléments dans la pile : il vaut initialement 0, puis est modifié au fur et à mesure des empilements et dépilements. C'est encore l'indice de l'élément correspondant au sommet du la pile.
les éléments suivants sont les éléments de la pile, initialisés à None.

On "triche" un peu car on utilise une liste pour définir une pile. Il faudrait en toute rigueur utiliser un tableau avec le module numpy.

Voici un exemple d'une pile de taille 4 sous forme d'objet :

>>> P = Pile(4)
>>> P.empiler(6)
>>> P.empiler(5)
>>> P.sommet()
5
>>> P.depiler()
5
>>> P.depiler()
6
>>> P.depiler()
Erreur : la pile est vide

Manipulation de la pile P

L = [0, None, None, None, None]
L = [1, 6, None, None, None]
L = [2, 6, 5, None, None]
.
.
L = [1, 6, None, None, None]
.
L = [0, None, None, None, None]
.
.
.

Modification de la liste L

class Pile:

    def __init__(self, taille):
        self.taille = taille
        self.L = [0] + [None]*taille

    def est_vide(self):
        pass

    def est_pleine(self):
        pass

    def sommet(self):
        pass
        
    def depiler(self):
        pass

    def empiler(self, x):
        pass
    
    def vider(self):
        pass

Implémenter les méthodes de la classe Pile ci-dessus.

On n'utilise aucune méthode sur les listes comme append ou count : on se contente d'accéder aux différentes valeurs de L et de les modifier.

class Pile:

    def __init__(self, taille):
        self.taille = taille
        self.L = [0] + [None]*taille

    def est_vide(self):
        return self.L[0] == 0

    def est_pleine(self):
        return self.L[0] == self.taille

    def sommet(self):
        if self.est_vide():
            return None
        else:
            return self.L[self.L[0]]
        
    def depiler(self):
        if self.est_vide():
            print("La pile est vide")
            return None
        else:
            sommet = self.sommet() # On stocke le sommet (l'élément à dépiler) dans une variable temporaire
            self.L[self.L[0]] = None
            self.L[0] -= 1
            return sommet

    def empiler(self, x):
        if self.est_pleine():
            print("La pile est pleine")
        else:
            self.L[0] += 1
            self.L[self.L[0]] = x
    
    def vider(self):
        elements = []
        while not self.est_vide():
            elements.append(self.depiler())

        return elements

Les files

Une file est une structure de données dans laquelle on accède aux éléments suivant la règle du "premier entré, premier sorti. Autrement dit, on ne peut accéder qu'à l'objet situé au début de la file. On parle encore de FIFO pour First In, First Out.

Le principe est celui d'une file de clients à un guichet : le client qui passe en premier est celui qui est arrivé en premier.

Premier arrivé, premier servi !

Une structure de ce type dispose de deux opérations élémentaires :

enfiler(x) : insère la donnée x en queue de file
defiler() : retire la donnée située en tête de file

Opérations élémentaires : enfiler et défiler

Comme pour la pile, on peut définir d'autres opérations comme :

est_vide() : retourne True si la file est vide, False sinon
est_pleine() : retourne True si la file est pleine, False sinon
tete() : retourne l'élément en tête de file, sans le défiler
queue() : retourne l'élément en queue de file, sans le défiler
vider() : vide entièrement la file, en retournant la liste des éléments défilés

Implémentation

Une file F de taille $n$ peut se représenter à l'aide d'une liste L de $n+2$ éléments :

L[0] contient l'indice de la tête de la file
L[1] contient l'indice de la queue de la file
les $n$ cases restantes contiennent les éléments de la file, initialement égales à None

Quelques remarques :

Les indices de tête et de queue sont initialisés à 2
La file est vide si l'élément de tête L[L[0]] est égal à None
La file est pleine si l'élément de queue L[L[1]] est différent de None
Si l'indice de tête ou de queue dépasse la taille de la pile, on revient à l'indice initial 2

Voici un exemple d'implémentation d'une file de taille 3 en objet :

>>> F = File(3)
>>> F.enfiler(5)
>>> F.enfiler(37)
>>> F.defiler()
5
>>> F.enfiler(28)
>>> F.enfiler(49)
>>> F.enfiler(0)
La file est pleine
>>> F.defiler()
37
>>> F.defiler()
28
>>> F.defiler()
49
>>> F.defiler()
La file est vide

Manipulation de la file F

L = [2, 2, None, None, None]
L = [2, 3, 5, None, None]
L = [2, 4, 5, 37, None]
L = [3, 4, None, 37, None]
.
L = [3, 2, None, 37, 28]
L = [3, 3, 49, 37, 28]
.
.
L = [4, 3, 49, None, 28]
.
L = [2, 3, 49, None, None]
.
L = [3, 3, None, None, None]
.
.
.

Modification de la liste L

Implémenter une classe File conforme à l'exemple ci-dessus.

Comme pour la classe Pile, on se contente seulement d'accéder aux différents éléments de la liste L et de les modifier.

class File:

    def __init__(self, taille):
        self.taille = taille
        self.L = [2,2] + [None]*taille

    def tete(self):
        return self.L[self.L[0]]

    def queue(self):
        return self.L[self.L[1]]

    def est_vide(self):
        return self.tete() == None

    def est_pleine(self):
        return self.queue() != None
        
    def defiler(self):
        if self.est_vide():
            print("La file est vide")
            return None
        else:
            tete = self.tete()
            self.L[self.L[0]] = None
            self.L[0] += 1

            if self.L[0] == self.taille + 2: # Vérification du dépassement
                self.L[0] = 2

            return tete

    def emfiler(self, x):
        if self.est_pleine():
            print("La file est pleine")
        else:
            self.L[1] += 1

            if self.L[1] == self.taille + 2: # Vérification du dépassement
                self.L[1] = 2

            self.L[self.L[1]] = x
    
    def vider(self):
        elements = []
        while not self.est_vide():
            elements.append(self.defiler())

        return elements

Sommaire Exercices