Piles et files en NSI : comprendre les structures de données

Tu as déjà empilé des assiettes dans un placard ? Tu prends toujours celle du dessus, jamais celle du fond. Et dans une file d'attente à la cantine, le premier arrivé est le premier servi. Sans le savoir, tu viens de manipuler deux structures de données fondamentales : la pile et la file. En NSI, ces notions reviennent très souvent, aussi bien en Première qu'en Terminale, et elles tombent régulièrement au bac. Pas de panique : une fois que tu auras compris la logique, tout devient limpide. Dans cet article, on va décortiquer ensemble les piles et files en NSI, voir comment les coder en Python, et pourquoi elles sont partout dans ton ordinateur.

Pile et file : deux façons d'organiser les données

Une structure de données, c'est une manière d'organiser l'information pour pouvoir la retrouver, l'ajouter ou la supprimer efficacement. Une liste Python classique te permet d'accéder à n'importe quel élément par son indice. Mais parfois, on veut restreindre les opérations : on impose où on ajoute et où on retire. C'est exactement ce que font les piles et les files.

La pile : dernier arrivé, premier servi (LIFO)

Une pile (en anglais stack) est une structure où l'on ajoute et retire toujours du même côté, appelé le sommet. Imagine une pile de crêpes : tu poses une crêpe sur le dessus, et tu retires la crêpe du dessus. La dernière crêpe posée est la première mangée ! En informatique, on parle de LIFO : Last In, First Out (dernier entré, premier sorti).

Les opérations principales sur une pile sont :

• empiler (push) : ajouter un élément au sommet ;
• dépiler (pop) : retirer l'élément du sommet et le récupérer ;
• sommet (top ou peek) : consulter l'élément au sommet sans le retirer ;
• est_vide : vérifier si la pile est vide.

La file : premier arrivé, premier servi (FIFO)

Une file (en anglais queue) fonctionne comme une file d'attente au cinéma : on entre par un côté (la queue) et on sort par l'autre (la tête). Le premier arrivé est le premier servi. On parle de FIFO : First In, First Out.

Les opérations principales sur une file sont :

• enfiler (enqueue) : ajouter un élément à la queue ;
• défiler (dequeue) : retirer l'élément en tête et le récupérer ;
• tête (front) : consulter l'élément en tête sans le retirer ;
• est_vide : vérifier si la file est vide.

Retiens bien cette différence : pile = LIFO, file = FIFO. C'est la question piège classique en contrôle !

Comment coder une pile et une file en Python

Bonne nouvelle : Python fournit déjà tout ce qu'il faut dans le module collections, et une simple liste suffit aussi pour une pile. Voyons les deux cas.

Implémenter une pile avec une liste Python

En Python, une liste se comporte naturellement comme une pile grâce aux méthodes append (empiler) et pop (dépiler en fin de liste).

# Une pile représentée par une liste Python
pile = []

# Empiler des éléments
pile.append(10)   # pile = [10]
pile.append(20)   # pile = [10, 20]
pile.append(30)   # pile = [10, 20, 30]

# Consulter le sommet sans dépiler
sommet = pile[-1]  # sommet = 30

# Dépiler le sommet
element = pile.pop()  # element = 30, pile = [10, 20]

print(pile)  # affiche [10, 20]

Chaque append ajoute à la fin, et pop() sans argument retire le dernier élément : c'est exactement le comportement LIFO. Simple, non ?

Implémenter une file avec collections.deque

Pour une file, on pourrait aussi utiliser une liste, mais retirer le premier élément avec pop(0) est lent (Python doit décaler tous les autres éléments). La solution professionnelle est deque (double-ended queue), qui permet d'ajouter et retirer efficacement aux deux extrémités.

from collections import deque

# Une file représentée par un deque
file = deque()

# Enfiler des éléments (à droite)
file.append("Alice")   # file = deque(['Alice'])
file.append("Bob")     # file = deque(['Alice', 'Bob'])
file.append("Chloé")   # file = deque(['Alice', 'Bob', 'Chloé'])

# Défiler l'élément en tête (à gauche)
premier = file.popleft()  # premier = "Alice"

print(file)  # affiche deque(['Bob', 'Chloé'])

Ici, on enfile à droite avec append et on défile à gauche avec popleft. Résultat : le premier entré (Alice) est le premier sorti. C'est bien une file FIFO.

Une classe Pile complète (utile pour le bac)

Au bac, on te demande parfois d'écrire une classe avec des méthodes. Voici une implémentation propre et testable :

class Pile:
    def __init__(self):
        self.contenu = []

    def est_vide(self):
        return len(self.contenu) == 0

    def empiler(self, valeur):
        self.contenu.append(valeur)

    def depiler(self):
        if self.est_vide():
            raise IndexError("Pile vide")
        return self.contenu.pop()

    def sommet(self):
        if self.est_vide():
            raise IndexError("Pile vide")
        return self.contenu[-1]

# Test
p = Pile()
p.empiler(1)
p.empiler(2)
print(p.depiler())  # 2
print(p.sommet())   # 1

Tu peux t'entraîner à écrire la même chose pour une file avec deque. C'est un excellent exercice pour assimiler les structures de données en Terminale.

À quoi servent vraiment les piles et les files ?

Ces structures ne sont pas là pour décorer : elles sont au cœur de nombreux mécanismes informatiques que tu utilises tous les jours.

La pile : undo, appels de fonctions, analyse d'expressions

• Bouton Annuler (Ctrl+Z) : chaque action est empilée. Quand tu annules, on dépile la dernière action.
• Appels de fonctions : quand une fonction en appelle une autre, Python utilise une pile d'appels pour savoir où revenir. C'est aussi ce qui provoque l'erreur RecursionError quand tu récurses trop profondément.
• Vérification des parenthèses : pour savoir si une expression comme (3 + [4 * (5 - 1)]) est bien parenthésée, on empile les ouvrantes et on dépile à chaque fermante. Si la pile est vide à la fin, c'est bon !

La file : impressions, files d'attente, parcours en largeur

• File d'impression : les documents sont imprimés dans l'ordre d'arrivée.
• Serveur web : les requêtes des utilisateurs sont traitées dans l'ordre, ou dans une file de priorité.
• Parcours en largeur d'un graphe (BFS) : en Terminale, tu verras que pour explorer un graphe niveau par niveau, on utilise une file. C'est un classique du programme !

Tu veux t'entraîner sur ces cas concrets ? Va faire un tour sur les exercices NSI pour mettre les mains dans le code.

Méthode de révision et lien avec le bac NSI

Pour réussir sur les piles et files le jour J, voici une méthode simple et efficace :

• Apprends par cœur la différence LIFO / FIFO et associe chaque structure à une image mentale (assiettes vs file d'attente).
• Code au moins une fois une classe Pile et une classe File sans regarder ton cours. C'est le meilleur moyen de mémoriser.
• Entraîne-toi à tracer l'état d'une pile ou d'une file après une série d'opérations. Les exercices « à la main » tombent souvent au bac.
• Relie ces structures aux autres notions : récursivité, graphes, algorithmes de parcours. Tu montres ainsi que tu as une vision globale.

Pour consolider tout ça, jette un œil aux fiches de révision NSI et au cours complet NSI. Et si tu veux des explications complémentaires en vidéo ou des exercices corrigés pas à pas, le réseau AlloLycee propose des ressources utiles pour réviser sereinement. Pour les élèves qui visent une prépa ou une licence informatique, AlloBac peut aussi t'aider à structurer tes révisions.

Conclusion : tu as maintenant les clés

Les piles et les files ne sont pas juste des concepts abstraits : ce sont des outils puissants que tu retrouveras partout, du bouton « Annuler » aux algorithmes de graphes. En comprenant LIFO et FIFO, en sachant les coder en Python et en identifiant leurs cas d'usage, tu marques des points précieux au bac NSI. N'oublie pas : la programmation, ça s'apprend en pratiquant. Alors ouvre ton éditeur Python, écris une petite classe Pile, puis une classe File, et teste-les. Tu vas voir, c'est plus simple qu'il n'y paraît !