Piles et Files


De nouvelles structures de données

Les Piles et les Files, tout comme les tableaux ou les listes, sont des structures permettant de stocker des données organisées en séquence.

Contrairement aux tableaux qui permettent un accès direct à tous leurs éléments (par lintermédiaire de leur indice) et aux listes chaînées dont la vocation est essentiellement de parcourir les éléments séquentiellement dans un ordre donné, les piles et les files restreignent la manière dont on peut stocker puis récupérer les données, et notamment lordre dans lequel les données sont récupérées par rapport à lordre dinsertion.

  • Avec une structure de pile, le dernier élément stocké sera le premier élément récupéré. Les piles sont souvent appelées des LIFO par les informaticiens de langue anglo-saxonne, pour Last In First Out.

    Opérations de base d'une Pile

    Une structure de pile, comme son nom lindique, simule informatiquement ce qui se passerait avec une pile dobjets dans le monde physique: en général, on dépose des objets au sommet de la pile, et on récupère lobjet placé tout en haut de la pile, cest-à-dire le dernier objet dépose.

  • Au contraire, avec une structure de file, le premier élément stocké sera aussi le premier élément récupéré. Cest pourquoi les files sont appelées des FIFO en anglais, pour First In First Out.

    OPérations de base d'une File

    Une structure de file simule ce qui se passe pour une file dattente dans le monde réel, par exemple devant un guichet de la Poste: la première personne arrivée et entrée dans la file sera aussi la première personne à en sortir pour accéder au guichet.

En résumé, ce qui distingue essentiellement les piles des files est lordre de sortie des éléments précédemment entrés, ce que montre très bien le schéma ci-dessous:

Différence entre LIFO et FIFO

On peut constater notamment quavec une pile (LIFO), les éléments sont récupérés dans lordre inverse de leur insertion, alors que lordre est inchangé avec une file (FIFO).

Les piles

Interface dune pile

Outre les deux opérations essentielles dempilement et de dépilement montrées auparavant, voici les opérations constituant linterface dune structure de pile. Cette interface est présentée ici avec le paradigme de la programmation fonctionnelle, mais il sera implémenté un peu plus loin à laide de la POO.

  • est_vide(pile) booléen indiquant si la pile est vide ou non;
  • taille(pile) entier naturel représentant le nombre déléments stockés dans la pile;
  • empiler(pile, élément) rajoute un nouvel élément au sommet de la pile;
  • dépiler(pile) retire et retourne lélément placé au sommet de la pile. Déclenche une erreur si la pile est vide;
  • consulter(pile) retourne lélément placé au sommet de la pile, mais sans le dépiler. Déclenche une erreur si la pile est vide.

Remarque: On constate notamment quil nexiste pas de moyen daccéder à un élément arbitraire dune pile, par son indice ou par toute autre méthode. Ce nest pas la destination dune pile: si on a besoin dun accès direct, on utilisera un tableau. Si on a besoin daccéder aux éléments dune pile séquentiellement, on utilisera de préférence une liste (chaînée ou non).

Implémentation dune pile

On propose une première implémentation des piles qui utilise de manière interne une liste python. Le mécanisme dempilement/dépilement sera réalisé à laide des méthodes list.append et list.pop de la classe list.

class Pile1:
   """
   Je représente une pile, implémentée grâce aux listes python.
   """

   def __init__(self):
      """
      Crée une pile vide
      """
      self._tableau = []

   def est_vide(self):
      """
      Renvoie True ssi je suis une pile vide.
      """
      return len(self._tableau) == 0

   def taille(self):
      """
      Renvoie ma taille (en nombre d'éléments empilés)
      """
      return len(self._tableau)

   def empiler(self, valeur):
      """
      Empile un nouvel élément en mon sommet.
      """
      self._tableau.append(valeur)

   def dépiler(self):
      """
      Dépile et renvoie la valeur de l'élément placé en mon
      sommet.

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Dépiler sur une pile vide")
      else:
         return self._tableau.pop()

   def consulter(self):
      """
      Renvoie la valeur de l'élément placé en mon
      sommet.

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Dépiler sur une pile vide")
      else:
         return self._tableau[self.taille() - 1]

   def vider(self):
      """
      Enlève tous les éléments empiles.
      """
      self._tableau = []

   def __str__(self):
      N = self.taille()

      chaîne = "("

      i = 0
      while i < N:
         chaîne += str(self._tableau[i])
         if i == N - 2:
            chaîne += " | "
         elif i < N - 2:
            chaîne += " "
         i += 1

      chaîne += ")"

      return chaîne

   def __repr__(self):
      return str(self)

Outre linterface décrite à la section précédente, on a rajouté quelques compléments utiles, comme les méthodes magiques __str__ et __repr__, ainsi quune méthode vider dont lusage est évident.

Complexité des opérations de linterface dune pile

La complexité (une manière savante pour parler du coût dexécution en temps mais aussi en usage de la mémoire) des opérations de linterface dépend de limplémentation choisie: à la fois la structure de donnée concrète choisie pour limplémentation, mais aussi éventuellement le choix des algorithmes, conditionnent lefficacité des méthodes.

Quen est-il avec notre première implémentation ? Lefficacité sera directement liée à lefficacité de limplémentation des listes en python.

  • Savoir si une liste est vide ou connaître la taille dune liste a un coût constant.
  • Nous avons déjà étudié le fait que les opérations append et pop ont un coût linéaire, car il peuvent nécessiter une réaffectation dans la mémoire de lordinateur, ainsi quune recopie de tous les éléments vers la nouvelle zone réservée en mémoire. On aura donc naturellement un coût linéaire pour les opérations dempilement et de dépilement, ce qui signifie que le temps dexécution de ces deux opérations sera proportionnel au nombre de données stockées dans la pile.

Notons que le coût en mémoire est forcément proportionnel au nombre de données, mais il est impossible de faire mieux que cela (on peut éventuellement faire pire si on ne prend pas garde à la structure de donnée choisie, mais les listes python sont optimales à ce niveau là).

Une implémentation plus efficace à laide des listes chaînées

Les opérations dempilement/dépilement étant au coeur de ce quest une pile, nous souhaitons naturellement les optimiser. Idéalement, il serait souhaitable que ces opérations aient un coût constant.

Rappelons-nous que les listes chaînées disposent de deux opérations qui ressemblent à sy méprendre à lempilement/dépilement: il sagit des opérations tête et queue. Plus précisément:

  • Lopération tête des listes chaînées rajoute un élément au début de la liste. Cela revient à empiler un élément, à condition de considérer que le sommet de la pile est le début de la liste.
  • Lopération queue des listes chaînées renvoie la liste privée de son élément de tête, ce qui revient à retirer celui-ci. On a donc bien réalisé un dépilement, puisque lon considère que le sommet de la pile est la tête de la liste. Il faudra simplement renvoyer la valeur de la tête initiale en plus de ce dépilement, mais cela ne changera pas la complexité.

Très important: Ces deux opérations ont un coût constant, cest tout lintérêt des listes chaînées.

Notons que si le coût en temps dexécution devient constant, le coût en usage de la mémoire reste linéaire: bien quune cellule consomme deux fois plus de mémoire quune simple case dans une liste python (il faut une deuxième case pour pointer sur la cellule suivante), le coût reste proportionnel (avec un coefficient de proportionnalité doublé) à la quantité de données.

Une autre manière de dire la même chose: dire que lon a un coût linéaire en mémoire signifie que doubler la quantité de données doublera la quantité de mémoire utilisée. Cela est vrai à la fois pour les listes python et pour les listes chaînées. Le fait quune liste chaînée consomme a priori deux fois plus de mémoire quune liste python ne change rien à cette proportionnalité, et nest probablement guère importante à lheure où le coût (financier) de la mémoire vive est relativement faible.

from listes import cellule, tête, queue, liste_vide, est_vide

class Pile2:
   """
   Je représente une pile, implémentée grâce à une
   liste chaînée immuable.
   """

   def __init__(self):
      """
      Crée une pile vide
      """
      self._liste = liste_vide()
      self._taille = 0

   def est_vide(self):
      """
      Renvoie True ssi je suis une pile vide.
      """
      return est_vide(self._liste)

   def taille(self):
      """
      Renvoie ma taille (en nombre d'éléments empilés)
      """
      return self._taille

   def empiler(self, valeur):
      """
      Empile un nouvel élément en mon sommet.
      """
      self._liste = cellule(valeur, self._liste)
      self._taille += 1

   def dépiler(self):
      """
      Dépile et renvoie la valeur de l'élément placé en mon
      sommet.

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Dépiler sur une pile vide")
      else:
         valeur = tête(self._liste)
         self._liste = queue(self._liste)
         self._taille -= 1
         return valeur

   def consulter(self):
      """
      Renvoie la valeur de l'élément placé en mon
      sommet.

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Dépiler sur une pile vide")
      else:
         return tête(self._liste)

   def vider(self):
      """
      Enlève tous les éléments empiles.
      """
      self._liste = liste_vide()
      self._taille = 0

   def __str__(self):
      chaîne = "("

      position = self._liste
      premier = True
      while not est_vide(position):
         chaîne += str(tête(position))
         if premier:
            chaîne += " | "
            premier = False
         elif not est_vide(queue(position)):
            chaîne += " "

         position = queue(position)

      chaîne += ")"

      return chaîne

   def __repr__(self):
      return str(self)

Remarque: Calculer la taille dune liste chaînée a une complexité linéaire en la quantité de cellules (il faut parcourir toute la liste pour en connaître le nombre déléments). Afin déviter ce désagrément, on ajoute un attribut _taille qui permet de rendre le coût constant, au prix de devoir toujours tenir à jour cet attribut lors des empilements/dépilements.

Comparaison de lefficacité des deux implémentations

Résumons ici lefficacité des méthodes de nos deux implémentations:

Implémentation Pile1 (listes python) Pile2 (listes chaînées)
est_vide constant constant
taille constant constant
empiler linéaire constant
dépiler linéaire constant

À lavenir, nous utiliserons de préférence cette seconde implémentation, a priori plus efficace. Nous pourrons limporter grâce à la syntaxe suivante, qui permet de choisir limplémentation souhaitée au moment de limportation, et surtout de ne plus sen préoccupper par la suite (cest tout lavantage davoir deux implémentations respectant scrupuleusement la même interface).

from piles import Pile2 as Pile

Les files

Interface dune file

On a déjà détaillé les deux opérations essentielles à la structure de file: enfiler et défiler, qui permettent respectivement de rajouter et de retirer des éléments de la file. Voici linterface complète dune file:

  • est_vide(file) booléen indiquant si la file est vide ou non;
  • taille(file) entier naturel représentant le nombre déléments stockés dans la file;
  • enfiler(file, élément) rajoute un nouvel élément à lentrée de la file;
  • défiler(file) retire et retourne lélément placé à la sortie de la file. Déclenche une erreur si la file est vide;
  • consulter(file) retourne lélément placé à la sortie de la file, mais sans le défiler. Déclenche une erreur si la file est vide.

Remarque: Comme pour les piles, il nexiste pas de moyen daccéder à un élément arbitraire dune file.

Implémentation dune file

La première implémentation des files, tout comme pour les piles, utilisera une liste python.

Tout comme pour les piles, on utilisera:

  • append(élément) pour ajouter un élément en bout de liste;
  • pop(0) pour retirer lélément placé en début de liste:

Remarque: Le fait de placer en fin de liste pour retirer en début de liste na aucune importance: on aurait tout aussi bien pu faire le contraire avec insert(0, élément) pour insérer en début de liste et pop() pour retirer en fin de liste. Lessentiel, est que linsertion et la récupération se fassent de part et dautre de la liste.

Voici notre première implémentation:

class File1:
   """
   Je représente une file, implémentée grâce aux listes python.
   """

   def __init__(self):
      """
      Crée une file vide
      """
      self._tableau = []

   def est_vide(self):
      """
      Renvoie True ssi je suis une file vide.
      """
      return len(self._tableau) == 0

   def taille(self):
      """
      Renvoie ma taille (en nombre d'éléments emfilés)
      """
      return len(self._tableau)

   def enfiler(self, valeur):
      """
      Enfile un nouvel élément.
      """
      self._tableau.append(valeur)

   def défiler(self):
      """
      Défile et renvoie la valeur de l'élément placé premier
      dans la file (le plus ancien).

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Défiler sur une file vide")
      else:
         return self._tableau.pop(0)

   def consulter(self):
      """
      Renvoie la valeur de l'élément placé en position
      de défilement (la valeur la plus ancienne).

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Défiler sur une file vide")
      else:
         return self._tableau[0]

   def vider(self):
      """
      Enlève tous les éléments empiles.
      """
      self._tableau = []

   def __str__(self):
      N = self.taille()

      chaîne = "("

      i = 0
      while i < N:
         chaîne += str(self._tableau[i])
         if i < N - 1:
            chaîne += " ← "
         i += 1

      chaîne += ")"

      return chaîne

   def __repr__(self):
      return str(self)

Une implémentation plus efficace à laide dune liste chaînée variable

Comme pour notre première implémentation dune pile, tant les méthodes insert, append et pop induisent un coût (et donc une complexité) linéaire sur les opérations denfilement et de défilement.

Il existe plusieurs moyens dimplémenter une file tout en gardant des accès constants avec ces deux opérations. La première utilise une liste chaînée.

Cependant, nous avons immédiatemment un problème: la liste chaînée est une structure optimisée pour le rajout et le retrait en tête de liste, ce qui revient à dire quune liste chaînée est une excellente implémentation pour une pile. Cependant, pour une file, nous avons besoin daccéder efficacement à la dernière cellule dune liste chaînée, mais aussi de rajouter ou de retirer des éléments en bout de liste.

Il est possible de palier à ces deux inconvénients en utilisant deux astuces:

  • Pour accéder à la dernière cellule dune liste chaînée en un temps constant (plutôt que linéaire en parcourant la liste dans son intégralité), il suffit de garder un pointeur vers cette dernière cellule;
  • Pour pouvoir ajouter des cellules en bout de liste, il suffit dutiliser une structure de cellule variable plutôt quimmuable. En terme dimplémentation dune cellule, on utilisera donc des tableaux [tête, queue] plutôt que des tuples (tête, queue).
from listes import (cellule_variable, 
                    tête, queue, 
                    liste_vide, est_vide, 
                    change_queue)

class File2:
   """
   Je représente une file, implémentée grâce à une liste
   chaînée variable.
   """

   def __init__(self):
      """
      Crée une file vide
      """
      self._première = liste_vide()
      self._dernière = self._première
      self._taille = 0

   def est_vide(self):
      """
      Renvoie True ssi je suis une file vide.
      """
      return est_vide(self._première)

   def taille(self):
      """
      Renvoie ma taille (en nombre d'éléments empilés)
      """
      return self._taille

   def enfiler(self, valeur):
      """
      Enfile un nouvel élément.
      """

      # On ajoute le nouvel élément à l'arrière de la liste:
      # C'est à ça que sert l'attribut self._dernière

      nouvelle_cellule = cellule_variable(valeur, liste_vide())

      if est_vide(self._dernière):
         # cas particulier: première valeur. 
         self._dernière = nouvelle_cellule
         self._première = self._dernière
      else:
         # On ajoute la nouvelle cellule en bout de liste,
         # mais on ne touche pas à la première cellule qui 
         # n'est pas ici modifiée par cette opération.
         change_queue(self._dernière, nouvelle_cellule)

         # Il ne faut pas oublier d'actualiser le pointeur
         # vers la dernière cellule, qui vient juste de
         # changer.
         self._dernière = nouvelle_cellule

      self._taille += 1

   def défiler(self):
      """
      Défile et renvoie la valeur de l'élément placé premier
      dans la file (le plus ancien).

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Défiler sur une file vide")
      else:
         valeur = tête(self._première)
         self._première = queue(self._première)
         self._taille -= 1

         if est_vide(self._première):
            # On vient de retirer la dernière cellule
            self._dernière = self._première

         return valeur

   def consulte(self):
      """
      Renvoie la valeur de l'élément placé en position
      de défilement (la valeur la plus ancienne).

      Déclenche une erreur si je suis vide.
      """
      if self.est_vide():
         raise IndexError("Défiler sur une file vide")
      else:
         return tête(self._première)

   def vider(self):
      """
      Enlève tous les éléments empiles.
      """
      self._première = liste_vide()
      self._dernière = self._première
      self._taille = 0

   def __str__(self):
      chaîne = "("

      position = self._première
      while not est_vide(position):
         chaîne += str(tête(position))
         if not est_vide(queue(position)):
            chaîne += " ← "
         position = queue(position)

      chaîne += ")"

      return chaîne

   def __repr__(self):
      return str(self)

Cette implémentation est relativement directe au vu de la description ci-dessus. Vous pouvez en observer le comportement en détail avec python tutor. Il y a cependant deux complications dans les méthodes enfiler et défiler:

  • On a un premier cas particulier lorsque lon enfile la première cellule sur une liste vide, car nous devons initialiser les deux pointeurs vers la première et la dernière cellule (qui pointent tous les deux vers la même unique cellule composant la liste chaînée);
  • De même, on a un second cas particulier lorsque lon défile le dernier élément de la file: lors de la destruction de lunique cellule, les deux pointeurs vers la première et la dernière cellule doivent à présent pointer vers une liste vide.

Voici létat de la file lorsquelle est vide:

File vide

Avec un unique élément:

File vide

Et enfin avec plusieurs élements:

File vide

Comparaison de lefficacité des deux implémentations

Résumons ici lefficacité des méthodes de nos deux implémentations:

Implémentation File1 (listes python) File2 (listes chaînées variables)
est_vide constant constant
taille constant constant
enfiler linéaire constant
défiler linéaire constant

À lavenir, nous utiliserons de préférence cette seconde implémentation, a priori plus efficace. Nous pourrons limporter grâce à la syntaxe suivante:

from files import File2 as File

Une troisième implémentation dune file ?

Nous verrons en TP quil est possible dimplémenter une file à laide de deux piles (en utilisant notre implémentation Pile2 précédente). Le coût moyen des opérations de linterface est constant pour cette nouvelle implémentation.