Structures linéaires : listes chaînées, piles et files
Distinction interface / implémentation, listes chaînées (maillons, insertion en tête, parcours), piles (LIFO) et files (FIFO) : opérations, implémentations, applications (annulation, parenthésage, files d'attente).
1. Interface et implémentation
Définition
Une structure de données abstraite est définie par son interface (les opérations possibles et leur effet). Une implémentation réalise cette interface avec des outils du langage ; il peut en exister plusieurs, plus ou moins efficaces.
2. Listes chaînées
Définition
Une liste chaînée est une suite de maillons ; chaque maillon contient une valeur et une référence vers le maillon suivant (ou None pour le dernier). Ajouter en tête est immédiat ; accéder au $k$-ième élément demande de parcourir $k$ maillons.
Exemple · Implémentation
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
def longueur(m):
n = 0
while m is not None:
n = n + 1
m = m.suivant
return n
L = Maillon(1, Maillon(2, Maillon(3))) # 1 -> 2 -> 33. Piles et files
Propriété · Interfaces
Pile (LIFO, last in, first out) : est_vide, empiler, depiler (renvoie le sommet), sommet. File (FIFO, first in, first out) : est_vide, enfiler, defiler. En Python, une liste fait une bonne pile (append, pop()) ; pour une file efficace, on utilise collections.deque ou deux piles.
Exemple · Applications
Pile : historique « précédent » d'un navigateur, annulation (Ctrl+Z), vérification du parenthésage, pile d'appels des fonctions. File : file d'impression, file d'attente de requêtes, parcours en largeur.
Activité · Vérifier le parenthésage
() et [].def bien_parenthese(s):
pile = []
paires = {")": "(", "]": "["}
for c in s:
if c in "([":
pile.append(c)
elif c in ")]":
if not pile or pile.pop() != paires[c]:
return False
return pile == []S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
LIFO ou FIFO
★☆☆Une pile est-elle LIFO ou FIFO ? et une file ?
Suite d'opérations sur une pile
★☆☆On empile $1$, $2$, $3$, on dépile une fois, on empile $4$. Contenu (du bas vers le haut) ?
Suite d'opérations sur une file
★☆☆On enfile $1$, $2$, $3$, on défile une fois, on enfile $4$. Contenu (de la tête à la queue) ?
Pile Python
★☆☆Avec une liste p, quelles méthodes pour empiler et dépiler ?
Classe Pile
★★☆Écrire une classe Pile avec est_vide, empiler, depiler.
File avec deque
★★☆Comment enfiler et défiler avec collections.deque ?
Pourquoi pas pop(0)
★★★Pourquoi liste.pop(0) est-il coûteux pour une grande file ?
Liste chaînée
★☆☆Que vaut L.suivant.valeur pour la liste du cours ?
Longueur
★☆☆Que renvoie longueur(L) ?
Ajout en tête
★★☆Comment ajouter $0$ en tête de L ?
Somme d'une liste chaînée
★★☆Écrire une fonction somme(m) qui additionne les valeurs d'une liste chaînée.
k-ième élément
★★☆Écrire element(m, k) qui renvoie la valeur du $k$-ième maillon (à partir de $0$).
Coût d'accès
★★☆Comparer le coût d'accès au $k$-ième élément dans un tableau Python et dans une liste chaînée.
Parenthésage
★★☆Que renvoie la fonction de l'activité pour "([)]" ? pour "(())" ?
Annuler
★★☆Pourquoi une pile convient-elle pour la fonction « annuler » d'un éditeur ?
File d'impression
★☆☆Quelle structure pour gérer les documents envoyés à une imprimante ?
Inverser avec une pile
★★☆Comment inverser une chaîne avec une pile ?
File avec deux piles
★★★Expliquer comment réaliser une file avec deux piles entree et sortie.
Notation polonaise inverse
★★★Évaluer 3 4 + 2 * avec une pile.
Vrai ou faux
★★☆a) Dépiler une pile vide est une erreur. b) Une liste chaînée permet l'accès direct au milieu. c) Une interface peut avoir plusieurs implémentations.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.