Piles et files avec deque

Comment utiliser cette page

Cette page comporte deux parties, qui modélisent toutes les deux le même historique de navigateur. La partie 1 (sections 1 à 8) utilise un dictionnaire manipulé par trois fonctions. La partie 2 (sections 9 et 10) reprend exactement les mêmes idées sous la forme d'une classe Historique, en programmation orientée objet. Chaque partie suit le même plan : vocabulaire ou principe, exemple concret, code, démonstration ou trace détaillée dans un tableau, puis tests.

1. Vocabulaire à connaître avant de commencer

Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.

2. L'exemple utilisé dans cette page

On reprend l'historique donné dans l'énoncé :

from collections import deque

historique = {"back": deque(['url_D3', 'url_C1', 'url_A8', 'url_A5']),
              "current": 'url_F',
              "forward": deque(['url_Z', 'url_alpha1'])}

Ce dictionnaire se lit ainsi : la page actuellement affichée est url_F. Avant d'arriver sur url_F, l'utilisateur a visité, dans l'ordre, url_D3, puis url_C1, puis url_A8, puis url_A5 — url_A5 est donc la page juste avant url_F, et c'est elle qui sera affichée si on clique une fois sur « précédent ». L'utilisateur avait aussi déjà commencé à avancer vers url_Z puis url_alpha1 avant de revenir en arrière : url_Z est donc la page juste après url_F, et c'est elle qui sera affichée si on clique sur « suivant ».

3. Pourquoi deque plutôt qu'une liste Python ordinaire ?

La fiche Les files a déjà montré que retirer le premier élément d'une liste Python avec l.pop(0) coûte O(n), car Python doit décaler tous les éléments restants d'une case. Le même problème se pose ici pour forward :

• Reculer ajoute une page en tête de forward (avec appendleft).
• Avancer retire une page en tête de forward (avec popleft).

Avec une liste Python classique, ces deux opérations s'écriraient l.insert(0, x) et l.pop(0), toutes deux en O(n). Avec collections.deque, appendleft(x) et popleft() sont toutes les deux en O(1), tout comme append(x) et pop() à l'autre extrémité. Comme back et forward jouent des rôles symétriques — une page qui sort de l'un entre dans l'autre — on utilise deque pour les deux, par cohérence.

4. Les trois fonctions du mini-projet

4.1 — reculer

1. Si back est vide, il n'y a pas de page précédente : on renvoie l'historique tel quel, sans le modifier.
2. Sinon, on ajoute la page courante en tête de forward (avec appendleft), car on pourra vouloir y revenir avec « avancer ».
3. On retire le sommet de back (avec pop), et cette page devient la nouvelle page courante.
4. On renvoie l'historique mis à jour.

def reculer(historique):
    """Retourne l'historique après un clic sur 'précédent'.
    Si back est vide, l'historique est renvoyé inchangé."""
    if len(historique["back"]) == 0:
        return historique
    historique["forward"].appendleft(historique["current"])
    historique["current"] = historique["back"].pop()
    return historique

4.2 — avancer

1. Si forward est vide, il n'y a pas de page suivante : on renvoie l'historique tel quel, sans le modifier.
2. Sinon, on ajoute la page courante en queue de back (avec append).
3. On retire le sommet de forward (avec popleft), et cette page devient la nouvelle page courante.
4. On renvoie l'historique mis à jour.

def avancer(historique):
    """Retourne l'historique après un clic sur 'suivant'.
    Si forward est vide, l'historique est renvoyé inchangé."""
    if len(historique["forward"]) == 0:
        return historique
    historique["back"].append(historique["current"])
    historique["current"] = historique["forward"].popleft()
    return historique

4.3 — nouvelle_url

1. On ajoute la page courante en queue de back (avec append).
2. La nouvelle URL devient la page courante.
3. On vide complètement forward (avec clear).
4. On renvoie l'historique mis à jour.

def nouvelle_url(historique, url):
    """Retourne l'historique après la visite d'une nouvelle page url.
    forward est entièrement vidé."""
    historique["back"].append(historique["current"])
    historique["current"] = url
    historique["forward"].clear()
    return historique

5. Démonstration interactive

On part de l'historique de l'exemple, et on applique dans l'ordre la première séquence de test de l'énoncé :

reculer, reculer, nouvelle_url, reculer, reculer, avancer

reculer(historique)
reculer(historique)
nouvelle_url(historique, 'url_B2')
reculer(historique)
reculer(historique)
avancer(historique)

6. Autres traces à dérouler (tableaux détaillés)

Ces tableaux se lisent comme la démonstration ci-dessus, mais sans animation : à chaque ligne, on note l'état complet de l'historique juste après l'instruction.

6.1 — Deuxième séquence de l'énoncé

avancer, avancer, reculer, nouvelle_url, reculer (URL choisie pour nouvelle_url : 'url_G7')

(Les URL sont notées sans le préfixe url_ pour que le tableau tienne sur la page ; par exemple « F » désigne 'url_F'.)

6.2 — Quand back devient vide : tester reculer

On repart de l'historique de l'exemple, et on appelle reculer cinq fois de suite. back ne contient que 4 éléments : il devient vide après le 4^e appel, et le 5^e appel doit vérifier que rien ne change.

6.3 — Quand forward devient vide : tester avancer

On repart de l'historique de l'exemple, et on appelle avancer trois fois de suite. forward ne contient que 2 éléments : il devient vide après le 2^e appel, et le 3^e appel doit vérifier que rien ne change.

7. Tests en Python (avec assert)

Voici comment on peut écrire, en Python, les tests des deux sections précédentes : chaque assert vérifie une valeur du tableau correspondant.

def etat_initial():
    """Reconstruit l'historique de l'exemple, à chaque appel."""
    return {"back": deque(['url_D3', 'url_C1', 'url_A8', 'url_A5']),
            "current": 'url_F',
            "forward": deque(['url_Z', 'url_alpha1'])}


def test_sequence_1():
    """reculer, reculer, nouvelle_url, reculer, reculer, avancer"""
    h = etat_initial()
    reculer(h)
    reculer(h)
    nouvelle_url(h, 'url_B2')
    reculer(h)
    reculer(h)
    avancer(h)
    assert list(h["back"]) == ['url_D3', 'url_C1']
    assert h["current"] == 'url_A8'
    assert list(h["forward"]) == ['url_B2']
    print("Séquence 1 : OK")


def test_sequence_2():
    """avancer, avancer, reculer, nouvelle_url, reculer"""
    h = etat_initial()
    avancer(h)
    avancer(h)
    reculer(h)
    nouvelle_url(h, 'url_G7')
    reculer(h)
    assert list(h["back"]) == ['url_D3', 'url_C1', 'url_A8', 'url_A5', 'url_F']
    assert h["current"] == 'url_Z'
    assert list(h["forward"]) == ['url_G7']
    print("Séquence 2 : OK")


def test_reculer_quand_back_devient_vide():
    h = etat_initial()
    for _ in range(4):
        reculer(h)
    assert len(h["back"]) == 0
    assert h["current"] == 'url_D3'
    # Un 5e appel ne doit rien changer
    reculer(h)
    assert len(h["back"]) == 0
    assert h["current"] == 'url_D3'
    print("reculer avec back vide : OK")


def test_avancer_quand_forward_devient_vide():
    h = etat_initial()
    for _ in range(2):
        avancer(h)
    assert len(h["forward"]) == 0
    assert h["current"] == 'url_alpha1'
    # Un 3e appel ne doit rien changer
    avancer(h)
    assert len(h["forward"]) == 0
    assert h["current"] == 'url_alpha1'
    print("avancer avec forward vide : OK")

8. Complexité des trois fonctions

• reculer fait un test de longueur, un appendleft et un pop : trois opérations en O(1), donc reculer est en O(1).
• avancer fait un test de longueur, un append et un popleft : trois opérations en O(1), donc avancer est aussi en O(1).
• nouvelle_url fait un append et un clear : append est en O(1), et clear est également en O(1) sur un deque (contrairement à une liste, où vider en boucle coûterait O(n)).
• Ce résultat n'aurait pas été garanti avec des listes Python classiques à la place des deque : appendleft et popleft deviendraient insert(0, x) et pop(0), tous les deux en O(n).

9. La classe Historique (programmation orientée objet)

On reprend exactement les mêmes idées que dans la partie 1, mais sous forme d'une classe : back, current et forward deviennent des attributs d'un objet, et reculer, avancer, nouvelle_url deviennent des méthodes de cette classe. Le vocabulaire de la programmation orientée objet (classe, attribut, méthode, constructeur, self, __repr__) est détaillé dans la fiche Interfaces, implémentation bas niveau et POO.

9.1 — Ce qui change par rapport à la version fonctionnelle

9.2 — Code de la classe

1. Constructeur __init__ : reçoit l'URL de départ, et éventuellement des piles back et forward déjà remplies (vides par défaut).
2. reculer : si self.back est vide, ne fait rien ; sinon, ajoute self.current en tête de self.forward, puis remplace self.current par le sommet de self.back.
3. avancer : le symétrique exact, entre self.back et self.forward.
4. nouvelle_url : ajoute self.current en queue de self.back, remplace self.current par la nouvelle URL, puis vide self.forward.
5. __repr__ : renvoie une chaîne de caractères lisible, affichée par print(hist).

class Historique:
    """Historique de navigation d'un onglet."""

    def __init__(self, url_actuelle, back=None, forward=None):
        self.back = deque(back) if back is not None else deque()
        self.current = url_actuelle
        self.forward = deque(forward) if forward is not None else deque()

    def reculer(self):
        """Modifie self : passe à la page précédente (sommet de back).
        Ne fait rien si back est vide."""
        if len(self.back) == 0:
            return
        self.forward.appendleft(self.current)
        self.current = self.back.pop()

    def avancer(self):
        """Modifie self : passe à la page suivante (sommet de forward).
        Ne fait rien si forward est vide."""
        if len(self.forward) == 0:
            return
        self.back.append(self.current)
        self.current = self.forward.popleft()

    def nouvelle_url(self, url):
        """Modifie self : visite une nouvelle page url, et vide forward."""
        self.back.append(self.current)
        self.current = url
        self.forward.clear()

    def __repr__(self):
        return f"Historique(back={list(self.back)}, current={self.current!r}, forward={list(self.forward)})"

Remarque sur la complexité : reculer, avancer et nouvelle_url utilisent exactement les mêmes opérations sur deque que dans la partie 1 (section 8) ; elles sont donc, elles aussi, toutes les trois en O(1).

10. Trois onglets, trois objets indépendants

Chaque onglet ouvert dans le navigateur a son propre historique de navigation, totalement indépendant des autres. On crée donc un objet Historique différent pour chaque onglet : hist_A, hist_B et hist_C.

10.1 — Création des trois objets

hist_A = Historique('url_article1', back=['url_moteur', 'url_resultats1'], forward=[])
hist_B = Historique('url_boite_reception', back=[], forward=['url_message_supprime'])
hist_C = Historique('url_video1', back=['url_accueil_C'], forward=['url_video2', 'url_video3'])

10.2 — Jeu d'instructions de test

On applique, dans cet ordre, sept instructions réparties sur les trois onglets, pour vérifier qu'agir sur l'un ne modifie jamais les deux autres :

1. hist_A.reculer()
2. hist_B.avancer()
3. hist_C.nouvelle_url('url_commentaires')
4. hist_A.reculer()
5. hist_B.nouvelle_url('url_nouveau_message')
6. hist_C.reculer()
7. hist_A.avancer()

10.3 — Trace : état des trois objets à chaque étape

À chaque ligne, seul l'onglet concerné par l'instruction change d'état ; les deux autres restent identiques à la ligne précédente — c'est exactement ce qu'on attend de trois objets indépendants.

(Comme dans les tableaux de la partie 1, les URL sont abrégées : « moteur » désigne 'url_moteur', « commentaires » désigne 'url_commentaires', etc.)

10.4 — Affichage final, avec __repr__

>>> print(hist_A)
Historique(back=['url_moteur'], current='url_resultats1', forward=['url_article1'])
>>> print(hist_B)
Historique(back=['url_boite_reception', 'url_message_supprime'], current='url_nouveau_message', forward=[])
>>> print(hist_C)
Historique(back=['url_accueil_C'], current='url_video1', forward=['url_commentaires'])

11. Points clés à retenir

• L'historique d'un navigateur se modélise avec trois informations : deux piles, back et forward, encadrant une page courante, current — sous forme d'un dictionnaire (partie 1) ou des attributs d'un objet (partie 2).
• On utilise collections.deque plutôt qu'une liste Python car reculer et avancer ont besoin d'ajouter et de retirer des éléments à l'extrémité gauche d'une des deux piles ; avec deque, ces opérations sont en O(1) grâce à appendleft et popleft.
• Reculer et avancer sont deux opérations symétriques : la page courante passe dans l'autre pile, et le sommet de la pile visée devient la nouvelle page courante.
• Visiter une nouvelle page vide entièrement forward : on ne peut plus « avancer » vers un chemin de navigation qui n'existe plus.
• Il faut toujours tester si la pile concernée est vide avant de la manipuler (len(...) == 0) : sans ce test, pop() ou popleft() sur un deque vide lèverait une erreur.
• En version orientée objet, les méthodes modifient self directement et ne renvoient rien : on écrit hist.reculer(), jamais hist = hist.reculer().
• Chaque objet créé à partir de la classe Historique est indépendant des autres, à condition d'initialiser back et forward avec None comme valeur par défaut dans le constructeur, plutôt qu'avec un deque() partagé entre toutes les instances.