Pile et file en Python avec deque
En programmation, les piles et files, aka LIFO (last in, first out) et FIFO (first in, first out) sont des incontournables. Il s’agit de stocker des données, et surtout de l’ordre dans lequel on récupère celle-ci. Pour information, j’avais écris Exemple de file avec deux pointeurs en langage C qui est un exemple de liste chaînée utilisé comme une file en C.
Comme Python est un langage haut niveau, il offre une façon simple de mettre en
place l’un ou l’autre. On va voir qu’il correspond à une classe du module collections.
Pourquoi ne pas utiliser simplement une liste ?
Il est possible d’obtenir le même comportement avec une liste, surtout qu’elle offre un peu près les mêmes méthodes (pop), cependant, deque est spécialement prévu pour cette effet, et est donc optimisé dans ce sens. Il est donc préférable d’utiliser deque si l’on sait qu’on l’utilise comme fifo ou lifo.
Comment ça marche ?
Rien de bien compliqué, regardons cette suite de commande effectuer directement avec l’interpréteur.
- Fonctionnement comme pile (lifo)
>>> pile = deque([1, 2, 3, 4, 5])
>>> from collections import deque
>>> pile = deque([1, 2, 3, 4, 5])
>>> pile.pop()
5
>>> pile.pop()
4
>>> pile.append(6)
>>> pile
deque([1, 2, 3, 6])
- Fonctionnement comme file (fifo)
>>> pile = deque([1, 2, 3, 4, 5])
>>> pile.popleft()
1
>>> pile.popleft()
2
>>> pile.append(6)
>>> pile
deque([3, 4, 5, 6])
Et après ?
Le module vient avec d’autres méthodes pouvant être utile dans ce genre de cas tel que appendleft(), clear(), extend(), reverse(), rotate(n) et j’en passe. Pour plus de détails sur les possibilités, lisez la documentation officiel sur ce module.
Un billet assez simple, mais pouvant être utile pour mettre en place rapidement
une fifo ou lifo. Ce n’est qu’une méthode parmi d’autre d’obtenir ce qu’on veut,
mais l’avantage de deque est d’être très simple à l’emploi. Éventuellement, pour
les plus curieux, l’utilisation de queue.LifoQueue pourrait intéresser, mais l’idée de ce
billet est vraiment de garder une utilisation simplifié au maximum.
