File et pile
À partir de séquences, il est possible de construire des types abstraits de données (TAD), c'est-à-dire une structure de données et un ensemble d'opérations qu'il est possible de faire avec. La librairie standard Python propose une série de fonctions permettant d'utiliser une liste comme une file ou une pile, deux types abstraits de données très répandus qui sont des cas particuliers de séquences.
File
Une file est une séquence ordonnée d'éléments, c'est-à-dire une liste, tel que l'ajout d'un nouvel élément (enqueue) se fait à sa fin et le retrait d'un élément (dequeue) à sa tête. Une file est une liste de type FIFO (First-in First-out), c'est-à-dire que le premier élément qui y a été ajouté sera aussi le premier qui en sortira, comme l'illustre la figure 7.
En Python, on utilise la fonction append appliquée sur la liste pour ajouter un élément à sa fin et on utilise la fonction pop pour retirer un élément à son début. Voici un exemple qui crée une file vide, lui ajoute deux éléments, puis en retire un :
Remarquez qu'on a utilisé l'opérateur d'accès (.) sur la variable contenant la file pour appeler les fonctions append et pop. On reviendra plus loin dans ce livre sur la raison pour laquelle on doit procéder ainsi. L'exécution de ces instructions affiche le premier élément retiré de la file, ainsi que les éléments restants dans celle-ci :
1 [2, 3]
Pour retirer le premier élément, on a dû faire l'appel pop(0). La raison pour laquelle on doit spécifier un indice est que la fonction pop est plus générale et permet en fait de retirer n'importe quel élément dans une liste, en précisant son indice.
Notez qu'on peut obtenir le même résultat avec des opérations de slicing. En effet, l'ajout d'un élément en fin de liste peut se faire en affectant une valeur à queue[len(queue):], et la suppression du premier élément peut se faire en ne gardant que la fin de liste, à savoir queue[1:]. L'exemple précédent peut donc également s'écrire comme suit :
Pile
Une pile est également une séquence ordonnée d'éléments, mais tel que l'ajout d'un nouvel élément (push) et le retrait d'un élément (pop) se fait toujours du même côté, en haut de la pile. Une pile est une liste de type LIFO (Last-in First-out), c'est-à-dire que l'élément qui en sortira sera toujours celui qui y est entré en dernier comme l'illustre la figure 8.
En Python, il va falloir utiliser la fonction append, à appliquer sur la liste, pour lui ajouter un élément à sa fin et la fonction pop pour en retirer un élément à la fin.
Voici un exemple qui crée une pile vide, lui ajoute deux éléments, puis en retire un :
La fonction pop est, cette fois-ci, appelée sans paramètre. En effet, par défaut elle va retirer l'élément en fin de liste. L'exécution de ces instructions affiche le premier élément retiré de la pile, ainsi que les éléments restants dans celle-ci :
3 [1, 2]
De nouveau, on peut obtenir le même résultat avec des opérations de slicing. L'exemple précédent peut se réécrire comme suit :