🎯 Objectifs de la lecon
- •Implémenter une pile avec une liste Python
- •Implémenter une file avec une liste Python et collections.deque
- •Réaliser les opérations push, pop, enqueue et dequeue
Les piles et les files sont des structures de données linéaires fondamentales. Elles permettent de stocker et de manipuler des éléments selon des règles d'accès précises. Tu vas apprendre à les implémenter en Python et à utiliser leurs opérations principales.
Qu'est-ce qu'une pile ?
Une pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier à être retiré. On appelle l'opération d'ajout push et l'opération de retrait pop.
« Exemple : une pile d'assiettes. Tu poses une assiette sur le dessus (push), et tu prends celle du dessus (pop). »
Point fort : L'image concrète aide à comprendre l'ordre LIFO.
En Python, on peut implémenter une pile avec une simple liste. La méthode append() réalise le push, et pop() sans argument retire le dernier élément.
✔️ A retenir
Pile : LIFO. Push = append(), pop = pop() sur une liste.
Implémentation d'une pile avec une liste Python
Pour créer une pile vide, on initialise une liste vide : pile = []. Pour ajouter un élément, on utilise pile.append(element). Pour retirer le dernier élément, on utilise element = pile.pop().
On peut aussi vérifier si la pile est vide avec len(pile) == 0 ou directement if not pile. La taille de la pile est donnée par len(pile).
⚠️ Attention
Attention : pop() sur une liste vide provoque une erreur IndexError. Il faut toujours vérifier que la pile n'est pas vide avant de dépiler.
« Exemple : pile = []; pile.append(3); pile.append(5); x = pile.pop() donne x = 5 et pile = [3]. »
Point fort : Montre l'ordre LIFO : le 5 est retiré avant le 3.
Qu'est-ce qu'une file ?
Une file suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier à être retiré. L'ajout s'appelle enqueue et le retrait dequeue.
« Exemple : une file d'attente à la cantine. Le premier élève arrivé est le premier servi (dequeue). »
Point fort : L'image de la file d'attente rend le FIFO intuitif.
On peut implémenter une file avec une liste Python, mais le retrait en tête (pop(0)) est lent car il décale tous les éléments. Pour une file efficace, on utilise collections.deque.
Implémentation d'une file avec une liste Python
Avec une liste, l'ajout en queue se fait avec append() (enqueue). Le retrait en tête se fait avec pop(0) (dequeue).
« Exemple : file = []; file.append(2); file.append(4); x = file.pop(0) donne x = 2 et file = [4]. »
Point fort : Montre le FIFO : le 2 est retiré avant le 4.
⚠️ Attention
Attention : pop(0) a un coût en temps O(n) car tous les éléments sont décalés. Pour des files de grande taille, préfère collections.deque.
Implémentation d'une file avec collections.deque
Le module collections fournit la classe deque (double-ended queue). Elle permet des ajouts et retraits efficaces aux deux extrémités.
Pour créer une file vide : from collections import deque puis file = deque(). L'ajout en queue se fait avec file.append(element) (enqueue). Le retrait en tête se fait avec file.popleft() (dequeue).
« Exemple : file = deque(); file.append(7); file.append(9); x = file.popleft() donne x = 7 et file = deque([9]). »
Point fort : popleft() est en O(1), bien plus rapide que pop(0) sur une liste.
✔️ A retenir
File : FIFO. Enqueue = append(), dequeue = popleft() avec deque. Pour une pile, on utilise append() et pop() sur une liste.
Erreurs fréquentes et bonnes pratiques
Une erreur courante est d'utiliser pop() sur une pile vide. Vérifie toujours avec if pile: avant de dépiler.
Pour une file, ne confonds pas pop() (retire le dernier) avec popleft() (retire le premier). pop() sur une deque retire par la droite, ce qui n'est pas le comportement FIFO attendu.
Quand tu utilises une liste pour une file, évite pop(0) si la file contient beaucoup d'éléments. Préfère deque pour des performances constantes.
✔️ A retenir
Pile : liste avec append() et pop(). File : deque avec append() et popleft(). Toujours vérifier que la structure n'est pas vide avant de retirer un élément.
