Les piles et les files sont deux structures de données linéaires qui permettent, au même titre que les listes, de gérer des séquences d'éléments. Ainsi, dans une pile et dans une file chaque élément est également repéré par sa position, il y a un premier, un dernier, chaque élément a un successeur (sauf le premier) et un prédecesseur (sauf le dernier).
Les opérations disponibles pour ces deux structures sont assez proches car dans les deux cas, on veut pouvoir :
Cependant, la politique d'ajout/retrait des éléments dans la séquence n'est pas la même. Le nom des opérations diffèrent également pour mieux distinguer les deux structures.
Il faut se représenter une pile comme... une pile de livres ! Seul le livre disposé sur le dessus est accessible : l'ajout et le retrait d'un livre ne peut donc se faire que sur le sommet de la pile.
On dit que les piles sont en mode LIFO (Last In, First Out qui signifie « dernier entré, premier sorti »).
Le jeu d'opérations disponibles pour une pile est :
construire_pile() : crée une pile videtaille(P) : accès au nombre d'éléments dans la pile Pempiler(P, e) : ajoute l'élément e au sommet de la pile P.depiler(P) : retire l'élément au sommet de la pile P. Précondition : P n'est pas vide.sommet(P) : pour accéder (en lecture) au sommet de la pile P (sans le retirer de la pile). Précondition : P n'est pas vide.En anglais, l'opération
empilerest souvent notéepush, l'opérationdepilerest souvent notéepopet l'opérationtailleest souvent notéetop.
Remarque : Certaines signatures algorithmiques peuvent légèrement varier. Par exemple, on peut parfois voir l'opération est_vide (qui teste si une pile est vide) à la place de taille (une pile est vide si et seulement si sa taille vaut 0) ou encore l'opération depiler qui renvoie également le sommet (donc l'opération sommet n'est plus nécessaire). C'est un choix libre qui ne change pas la nature de la structure de données abstraite mais la façon d'écrire des algorithmes.
Une pile contenant les éléments $\text{'a'}$, $\text{'b'}$ et $\text{'c'}$ ($\text{'a'}$ étant le sommet et donc $\text{'c'}$ le fond de la pile) sera représentée :
$$\text{>'a', 'b', 'c']}$$Exemple : On considère la pile P : $\text{>'a', 'b', 'c']}$. Voici comment la manipuler :
| Opération | Contenu de la pile |
|---|---|
empiler(P, 'e') |
$\text{>'e', 'a', 'b', 'c']}$ |
depiler(P) |
$\text{>'a', 'b', 'c']}$ |
depiler(P) |
$\text{>'b', 'c']}$ |
sommet(P) |
renvoie $\text{'b'}$ |
depiler(P) |
$\text{>'c']}$ |
empiler(P, 'm') |
$\text{>'m', 'c']}$ |
taille(P) |
renvoie 2 |
Les piles sont très utilisées en informatique. Voici quelques usages caractéristiques :
Certains de ces exemples seront abordés dans les activités.
Une pile est généralement implémentée par :
Selon le cas, il faudra veiller à ce que l'implémentation soit la plus efficace possible.
empiler et depiler seront plus efficaces si elles se font à la fin du tableau plutôt qu'au début car cela ne nécessite pas de décaler les autres éléments. Nous implémenterons une pile dans les activités.
Il faut se représenter une file comme... une file d'attente ! On ne peut entrer dans la file qu'en dernière position et on ne peut la quitter que si on est le premier. L'ajout d'un élément dans une file ne peut se faire qu'à la fin (en dernière position) et le retrait d'un élément ne peut se faire qu'au début (en première position).
On dit que les files sont en mode FIFO (First In, First Out qui signifie « premier entré, premier sorti »).
Le jeu d'opérations disponibles pour une file est :
construire_file() : crée une file videtaille(F) : accès au nombre d'éléments dans la file Fenfiler(F, e) : ajoute l'élément e en dernier dans la file F.defiler(F) : retire le premier élément de la file F. Précondition : F n'est pas vide.premier(F) : pour accéder (en lecture) au premier élément de la file F (sans le retirer de la file). Précondition : F n'est pas vide.En anglais, l'opération
enfilerest souvent notéepush, l'opérationdepilerest souvent notéepopet l'opérationtailleest souvent notéetop.
Remarque : Comme pour les piles, on pourrait remplacer l'opération taille par l'opération est_vide et choisir que defiler renvoie également le premier élément pour s'économiser l'opération premier.
Une file contenant les éléments $\text{'a'}$, $\text{'b'}$ et $\text{'c'}$ ($\text{'a'}$ étant le premier et $\text{'c'}$ le dernier) sera représentée :
$$\text{<'a', 'b', 'c'<}$$Exemple : Voici comment manipuler une file F :
| Opération | Contenu de la file F |
|---|---|
F = construire_file() |
$\text{<<}$ |
taille(F) |
renvoie 0 |
enfiler(F, 'a') |
$\text{<'a'<}$ |
enfiler(F, 'b') |
$\text{<'a', 'b'<}$ |
enfiler(F, 'c') |
$\text{<'a', 'b', 'c'<}$ |
premier(F) |
renvoie 'a' |
defiler(F) |
$\text{<'b', 'c'<}$ |
enfiler(F, premier(F)) |
$\text{<'b', 'c', 'b'<}$ |
Les piles sont très utilisées en informatique. Leur usage caractéristique concerne les files d'attentes :
Certains de ces exemples seront abordés dans les activités.
Il existe différentes façons d'implémenter une file, on peut par exemple utiliser :
Avec ces implémentations, il faudra en général faire un compromis sur l'efficacité des opérations car celles-ci nécessitent de travailler sur les deux extrémités de la file (pour enfiler/défiler).
defiler qui sera peu coûteuse et l'opération enfiler qui sera coûteuse.Il existe en réalité une implémentation plus efficace mais nous n'en parlerons pas ici.
Références :
Germain BECKER, Lycée Mounier, ANGERS
Ressource éducative libre distribuée sous Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International
