Leçon 11 : Piles et files

Commençons dans la cuisine : imagine une pile d'assiettes — on pose en haut et on prend en haut, donc la dernière posée sort en première. C'est une « pile » (stack), LIFO. Maintenant imagine une file à la caisse : le premier arrivé est le premier servi — c'est une « file » (queue), FIFO. En Python,

Une pile, c'est comme une pile d'assiettes : on pose en haut et on prend en haut — la dernière posée part en première. Une file, c'est comme une queue à la caisse : celui qui est arrivé en premier est servi en premier. C'est toute la différence — de quel côté on prend.

pile (stack): Une structure LIFO — dernier entré, premier sorti. En Python : une list avec append et pop en fin, les deux en O(1).
file (queue): Une structure FIFO — premier entré, premier sorti. En Python : collections.deque avec append et popleft, les deux en O(1).
deque: Une file à deux extrémités du module collections ; permet d'ajouter et de retirer en O(1) aux deux bouts, ce qui en fait la file FIFO efficace.