Pourquoi utiliser deque pour une file plutôt qu'une liste avec pop(0) ?

La méthode pop(0) sur une liste standard est coûteuse en complexité algorithmique : elle est en O(n) car après la suppression du premier élément, tous les autres éléments doivent être décalés d'un indice vers la gauche. La classe deque du module collections est conçue pour des ajouts et suppressions efficaces aux deux extrémités, avec une complexité en O(1) pour popleft() et append(). C'est bien plus performant pour de grandes files.

Est-ce qu'on peut parcourir une pile ou une file sans la vider ?

Oui, mais avec précaution. Pour une pile implémentée avec une liste, tu peux la parcourir avec une boucle for (for element in ma_pile:), mais cela ne respecte pas l'ordre LIFO. Pour une file avec deque, c'est similaire. Cependant, le parcours classique de ces structures se fait en retirant les éléments (avec pop() ou popleft()). Si tu as besoin d'accéder aux éléments sans les supprimer, tu peux utiliser l'indexation (ma_pile[-1] pour le sommet de la pile) ou simplement faire une copie de la structure avant de la parcourir pour la vider.

Quelle est la différence entre une file et une file prioritaire (priority queue) ?

Une file classique (FIFO) traite les éléments strictement par ordre d'arrivée. Une file prioritaire traite en premier l'élément qui a la plus haute priorité (ou la plus faible, selon la définition), indépendamment de son ordre d'arrivée. En Python, on peut implémenter une file prioritaire avec le module heapq (basé sur un tas binaire) ou avec la classe PriorityQueue du module queue. C'est une structure différente et très utile pour des algorithmes comme celui de Dijkstra.

Comprendre les piles et les files avec Python

Introduction : Deux Principes Opposés pour Organiser les Données

En algorithmique et en programmation, la façon dont on organise et on accède aux données est cruciale pour l'efficacité d'un programme. Deux structures de données simples mais extrêmement puissantes sont la pile (stack) et la file (queue). Elles représentent des principes d'organisation fondamentaux que tu retrouveras dans de nombreux problèmes, que ce soit en NSI, en concours d'informatique ou dans le développement logiciel. Leur force réside dans leur simplicité et dans les règles strictes qui régissent l'ajout et la suppression d'éléments. Dans cet article, on va démystifier ces concepts et voir comment les implémenter et les utiliser efficacement en Python.

La Pile (Stack) : Le Principe LIFO

Imagine une pile d'assiettes. Tu ne peux ajouter une nouvelle assiette qu'au sommet de la pile, et tu ne peux retirer que l'assiette qui se trouve au sommet. C'est exactement le principe de la pile ou stack en anglais. On appelle cela le LIFO : Last In, First Out (dernier entré, premier sorti). L'élément ajouté en dernier sera le premier à être retiré.

Implémenter une pile en Python

En Python, une pile s'implémente très facilement avec une liste et deux opérations principales :

Empiler (push) : Ajouter un élément au sommet. On utilise la méthode append().
Dépiler (pop) : Retirer et renvoyer l'élément du sommet. On utilise la méthode pop() sans argument.

Voici un exemple concret :

ma_pile = [] ma_pile.append("A") # Empile "A" ma_pile.append("B") # Empile "B" print(ma_pile) # Affiche ['A', 'B'] element = ma_pile.pop() # Dépile le dernier élément print(element) # Affiche 'B' print(ma_pile) # Affiche ['A']

Les piles sont omniprésentes en informatique. Elles sont utilisées pour :

La gestion des appels de fonctions (la pile d'exécution).
L'évaluation d'expressions mathématiques (notation polonaise inverse).
Les algorithmes de parcours de graphes (DFS - Depth-First Search).
Le mécanisme d'annulation (Ctrl+Z) dans les logiciels.

La File (Queue) : Le Principe FIFO

Maintenant, imagine une file d'attente à la cantine. La première personne à être arrivée est la première à être servie. C'est le principe de la file ou queue. On parle de FIFO : First In, First Out (premier entré, premier sorti). L'ordre d'arrivée est respecté.

Implémenter une file en Python

Avec une liste simple, on pourrait utiliser append() pour ajouter à la fin et pop(0) pour retirer du début. Cependant, pop(0) est une opération coûteuse pour de grandes listes car elle nécessite de décaler tous les autres éléments. La solution optimale est d'utiliser la classe deque (double-ended queue) du module collections.

from collections import deque ma_file = deque() ma_file.append("Alice") # Enfile "Alice" ma_file.append("Bob") # Enfile "Bob" print(ma_file) # Affiche deque(['Alice', 'Bob']) premier = ma_file.popleft() # Défile le premier élément print(premier) # Affiche 'Alice' print(ma_file) # Affiche deque(['Bob'])

Les files sont essentielles dans de nombreux domaines :

La gestion des processus dans un système d'exploitation (ordonnancement).
La gestion des requêtes dans un serveur web (file d'attente des requêtes).
Les algorithmes de parcours de graphes (BFS - Breadth-First Search).
La mise en buffer des données dans les flux (streaming).

Cas Pratique : Vérificateur de Parenthèses avec une Pile

Un exercice classique en NSI est de vérifier si une expression mathématique a ses parenthèses correctement équilibrées. Une pile est la structure parfaite pour résoudre ce problème.

L'algorithme est le suivant :

Parcourir chaque caractère de l'expression.
Si c'est une parenthèse ouvrante '(', '[', '{', on l'empile.
Si c'est une parenthèse fermante ')', ']', '}', on vérifie :
- Si la pile est vide → Erreur.
- Si le sommet de la pile est la parenthèse ouvrante correspondante, on la dépile.
- Sinon → Erreur.
À la fin du parcours, la pile doit être vide. Sinon, il y a des parenthèses ouvrantes non fermées.

Voici une implémentation simplifiée pour les parenthèses rondes :

def parentheses_equilibrees(expression): pile = [] for caractere in expression: if caractere == '(': pile.append(caractere) elif caractere == ')': if not pile: # Si la pile est vide return False pile.pop() return len(pile) == 0 print(parentheses_equilibrees("(a+b)*(c-d)")) # True print(parentheses_equilibrees("((a+b)")) # False

Quand Utiliser une Pile ou une File ?

Le choix entre une pile et une file dépend de la sémantique de ton problème.

Choisis une Pile (LIFO) quand l'ordre de traitement doit être inversé par rapport à l'ordre d'arrivée, ou quand tu as besoin de revenir en arrière. Exemples : navigation web (historique avec bouton "retour"), exploration en profondeur, calculatrice.
Choisis une File (FIFO) quand tu dois traiter les éléments dans l'ordre exact où ils sont arrivés, pour assurer une forme d'équité. Exemples : gestion de tâches, traitement de messages, exploration en largeur, simulateur de file d'attente.

Comprendre cette distinction est une étape clé dans la conception d'algorithmes efficaces et logiques.

Conclusion et Pour Aller Plus Loin

Les piles et les files sont bien plus que de simples exercices de cours. Ce sont des outils conceptuels fondamentaux. En maîtrisant leur implémentation en Python (avec list pour les piles et deque pour les files) et en comprenant leur logique LIFO/FIFO, tu as acquis des compétences solides pour aborder des problèmes algorithmiques plus complexes. Pour t'entraîner, tu peux essayer d'implémenter une calculatrice en notation polonaise inverse (pile) ou simuler un serveur gérant une file de requêtes. Bonne programmation !