Structures de Données Essentielles: Piles, Files, Listes

Correction :

Regarde par où les éléments entrent et sortent. a) On annule d'abord la dernière action : pile. b) Le premier document envoyé est imprimé le premier : file. c) Tu tiens déjà le nœud du morceau en cours, et insérer après lui coûte $O(1)$ sans rien décaler : liste chaînée.

Correction :

On dépile toujours le dernier arrivé. Après deux empilements, [4, 7] : on dépile 7. Puis [4, 2, 9] : on dépile 9, puis 2.

Valeurs dépilées : 7, 9, 2. Pile finale : [4].

Correction :

On défile toujours le premier arrivé. [4, 7] : on défile 4. Puis [7, 2, 9] : on défile 7, puis 2.

Valeurs défilées : 4, 7, 2. File finale : [9].

Erreur à éviter : répondre 7, 9, 2, comme pour la pile.

Correction :

On suit les liens depuis la tête jusqu'à None, en comptant.

def longueur(tete):
    n = 0
    courant = tete
    while courant is not None:
        n += 1
        courant = courant.suiv
    return n

Chaque nœud est visité une fois : coût $O(n)$, elle renvoie 4.

Erreur à éviter : oublier courant = courant.suiv, et la boucle ne s'arrête plus.

Correction :

Place le sommet en fin de liste, là où append et pop() ne décalent rien.

class Pile:
    def __init__(self):
        self.elements = []
    def est_vide(self):
        return len(self.elements) == 0
    def empiler(self, x):
        self.elements.append(x)
    def depiler(self):
        if self.est_vide():
            raise IndexError("pile vide")
        return self.elements.pop()

Sur une pile vide, on lève une exception : renvoyer None se confondrait avec un None empilé. Coût : $O(1)$ partout, $O(1)$ amorti pour empiler.

Erreur à éviter : un sommet en début de liste, avec insert(0, x) et pop(0), passe chaque opération en $O(n)$.

Correction :

Défiler une file de $k$ éléments décale les $k-1$ autres. Pour la vider, on additionne :

$$\sum_{k=1}^{n}(k-1) = \frac{n(n-1)}{2}$$

C'est $O(n^2)$ au total. Pour $n = 10\,000$ : $\frac{10\,000 \times 9\,999}{2}$, soit $49\,995\,000$ décalages.

Mieux : collections.deque et popleft(), en $O(1)$ ; vider la file coûte alors $O(n)$.

Correction :

On empile chaque ouvrant ; chaque fermant doit trouver au sommet l'ouvrant qui lui correspond.

def bien_parenthesee(s):
    paires = {")": "(", "]": "[", "}": "{"}
    pile = []
    for c in s:
        if c in "([{":
            pile.append(c)
        elif c in paires:
            if not pile or pile.pop() != paires[c]:
                return False
    return not pile

"[(])" échoue car ] trouve ( au sommet ; "(()" échoue car un ( reste dans la pile. Résultats : True, False, False.

Erreur à éviter : oublier le test final not pile, qui rejette "(()".

Correction :

Suis la file pas à pas : la distance d'une personne vaut celle de qui l'a enfilée, plus 1.

file     défilé  enfilés
[A]      A       C, B
[C, B]   C       D
[B, D]   B       E
[D, E]   D       F
[E, F]   E       aucun
[F]      F       aucun

Ordre : A, C, B, D, E, F. Distances : $0$ pour A, $1$ pour C et B, $2$ pour D et E, $3$ pour F.

Avec une pile : A, B, E, C, D, F ; E (distance 2) passerait avant C (distance 1).

Correction :

On retire le sommet, on inverse le reste, puis on glisse l'ancien sommet au fond.

def inserer_au_fond(p, x):
    if p.est_vide():
        p.empiler(x)
    else:
        haut = p.depiler()
        inserer_au_fond(p, x)
        p.empiler(haut)

def inverser(p):
    if not p.est_vide():
        haut = p.depiler()
        inverser(p)
        inserer_au_fond(p, haut)

Les éléments retirés attendent dans les appels en cours : la pile d'appels sert de pile cachée. Sur $k$ éléments, inserer_au_fond dépile $k$ fois. Le nombre $D(n)$ de dépilements de inverser vérifie donc $D(n) = D(n-1) + 1 + (n-1)$, avec $D(0) = 0$, d'où $D(n) = \frac{n(n+1)}{2}$ dépilements, soit $O(n^2)$.

Correction :

Le nouveau nœud reçoit ses deux liens, puis ses deux voisins pointent vers lui.

def inserer_apres(liste, n, v):
    nouveau = Noeud(v)
    nouveau.prec = n
    nouveau.suiv = n.suiv
    if n.suiv is None:
        liste.queue = nouveau
    else:
        n.suiv.prec = nouveau
    n.suiv = nouveau

Cas à part : n est la queue ; il n'a pas de suivant, c'est liste.queue qui change. Aucun parcours : 4 liens à écrire, en $O(1)$.

Erreur à éviter : écrire n.suiv = nouveau en premier. nouveau.suiv recevrait alors nouveau lui-même, et la fin de la liste serait perdue.