Piles, files

Les piles et les files sont deux structures de données qui permettent de stocker séquentiellement des valeurs. On distingue deux modes de stockage :

• LIFO (ou FILO) :: Last In First Out (ou First In Last Out). Il s'agit des piles : le dernier élément à être ajouté à la pile sera le premier élément à en être supprimé.
• FIFO :: First In First Out. Il s'agit des files : le premier élément à être ajouté à la file sera le premier élément à en être supprimé.

Dans chacun des cas ci-dessous, dire si la situation correspond à un mode de stockage LIFO ou FIFO.

• des assiettes rangées dans un placard :

  il s'agit du mode LIFO (la dernière assiette rangée sera la première assiette sortie)

• des élèves faisant la queue à la cantine :

  il s'agit du mode FIFO (le premier élève arrivé sera le premier élève servi)

Pile

On stocke les éléments selon le mode FILO. On ajoute et retire les éléments au sommet de la pile. Les éléments sont retirés d'une pile dans l'ordre inverse de leur ordre d'ajout.

On ne considère que le cas où les éléments sont des entiers. L'interface du type Pile est la suivante :

Notation fonction	Notation objet	Description
creer_pile_vide() -> Pile	Pile() -> Pile	Créer une pile vide
est_pile_vide(p:Pile) -> bool	p.est_vide() -> bool	Détermine si la pile p est vide.
empiler(p:Pile, c:int) -> None	p.empiler(c:int) -> None	Ajoute l'entier c au sommet de la pile p
depiler(p:Pile) -> int	p.depiler() -> int	Renvoie l'entier au sommet de la pile p, lorsque cela est possible.
affiche_pile(p:Pile) -> None	p.affiche() -> None	Affiche la pile p sans la modifier.

Les opérations d'empilement et de dépilement modifient la pile à laquelle elles s'appliquent. On parle d'effet de bord. Une pile est un objet mutable.

1. La pile p est constituée des éléments 1, 2 et 3 (3 est au sommet de la pile. Donner le contenu de p2 après l'exécution du code suivant :

   p2 = Pile()
   while not p.est_vide():
       p2.empiler(p.depiler())
   

   p2 est la pile 3, 2, 1 (1 est le sommet)

2. Quel est l'affichage alors réalisé par le code

   while not p2.est_vide():
       print(p2.depiler())   
   

   Cela affiche 1, 2, 3 (dans cet ordre).

File

On stocke les éléments selon le mode FIFO. On ajoute en fin de file et on retire les éléments au début de la file. Les éléments sont retirés d'une file dans le même ordre que leur ordre d'ajout.

On ne considère que le cas où les éléments sont des entiers. L'interface du type File est la suivante :

Notation fonction	Notation objet	Description
creer_file_vide() -> File	File() -> File	Créer une file vide
est_file_vide(f:File) -> bool	f.est_vide() -> bool	Détermine si la file f est vide.
enfiler(f:File, c:int) -> None	f.enfiler(c:int) -> None	Ajoute l'entier c à la fin de la file f
defiler(f:File) -> int	f.defiler() -> int	Renvoie l'entier au début de la file f, lorsque cela est possible.
affiche_file(f:File) -> None	f.affiche() -> None	Affiche la file f sans la modifier.

Les opérations d'enfilement et de défilement modifient la file à laquelle elles s'appliquent. On parle d'effet de bord. Une file est un objet mutable.

1. La file f est constituée des éléments 1, 2 et 3 (3 est à la fin de la file. Donner le contenu de f2 après l'exécution du code suivant :

   f2 = File()
   while not f.est_vide():
       f2.enfiler(f.defiler())
   

   f2 est la file 1, 2, 3 (3 est la fin de la file)

2. Quel est l'affichage alors réalisé par le code

   while not f2.est_vide():
       print(f2.defiler())   
   

   Cela affiche 1, 2, 3 (dans cet ordre).

Implémentation

On implémente l'interface du type Pile et du type File à l'aide d'objets de type Maillon.

Voir code correspondant écrit en TP.