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 == []⚠️ Une erreur dans ce cours ? Signalez-la
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 L ci-dessous ?
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 -> 3Longueur
★☆☆Avec le code ci-dessous, que renvoie longueur(L) ?
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 -> 3Ajout en tête
★★☆Avec le code ci-dessous, comment ajouter $0$ en tête de la liste chaînée L ?
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 -> 3Somme d'une liste chaînée
★★☆Les listes chaînées sont construites avec la classe Maillon ci-dessous. Écrire une fonction somme(m) qui additionne les valeurs d'une liste chaînée.
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 -> 3k-ième élément
★★☆Les listes chaînées sont construites avec la classe Maillon ci-dessous. Écrire element(m, k) qui renvoie la valeur du $k$-ième maillon (à partir de $0$).
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 -> 3Coû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 ci-dessous pour "([)]" ? pour "(())" ?
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 == []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.