TP : Simulateur de Navigateur Web — Piles et Files en action

Thème : Structures de données linéaires (Pile, File)

---

Contexte

Chaque jour, vous utilisez un navigateur web (Chrome, Firefox, Safari...). Avez-vous déjà remarqué comment fonctionnent les boutons ← Retour et → Suivant ? Et comment Netflix gère votre file d'attente "À regarder ensuite" ?

Dans ce TP, vous allez recréer ces mécanismes en utilisant les structures Pile et File.

---

Partie 1 : Implémentation des structures

Exercice 1 : La classe Pile

Implémentez une classe Pile avec les méthodes suivantes :

class Pile:
    """Structure de données LIFO (Last In First Out)."""

    def __init__(self):
        """Initialise une pile vide."""
        pass

    def empile(self, element):
        """Ajoute un élément au sommet de la pile."""
        pass

    def depile(self):
        """
        Retire et renvoie l'élément au sommet.
        Renvoie None si la pile est vide.
        """
        pass

    def est_vide(self):
        """Renvoie True si la pile est vide."""
        pass

    def sommet(self):
        """
        Renvoie l'élément au sommet sans le retirer.
        Renvoie None si la pile est vide.
        """
        pass

    def taille(self):
        """Renvoie le nombre d'éléments dans la pile."""
        pass

    def __repr__(self):
        """Affichage de la pile."""
        pass

Tests à effectuer :

>>> p = Pile()
>>> p.est_vide()
True
>>> p.empile("A")
>>> p.empile("B")
>>> p.empile("C")
>>> p.sommet()
'C'
>>> p.depile()
'C'
>>> p.taille()
2

---

Exercice 2 : La classe File

Implémentez une classe File avec les méthodes suivantes :

class File:
    """Structure de données FIFO (First In First Out)."""

    def __init__(self):
        """Initialise une file vide."""
        pass

    def enfile(self, element):
        """Ajoute un élément en queue de file."""
        pass

    def defile(self):
        """
        Retire et renvoie l'élément en tête de file.
        Renvoie None si la file est vide.
        """
        pass

    def est_vide(self):
        """Renvoie True si la file est vide."""
        pass

    def tete(self):
        """
        Renvoie l'élément en tête sans le retirer.
        Renvoie None si la file est vide.
        """
        pass

    def taille(self):
        """Renvoie le nombre d'éléments dans la file."""
        pass

    def __repr__(self):
        """Affichage de la file."""
        pass

Tests à effectuer :

>>> f = File()
>>> f.est_vide()
True
>>> f.enfile("Premier")
>>> f.enfile("Deuxième")
>>> f.enfile("Troisième")
>>> f.tete()
'Premier'
>>> f.defile()
'Premier'
>>> f.taille()
2

---

Partie 2 : Simulateur de navigateur web

Principe de fonctionnement

Un navigateur utilise deux piles pour gérer l'historique :

• Pile historique : contient les pages visitées (la page actuelle est au sommet)
• Pile suivant : contient les pages "en avant" (après avoir cliqué sur Retour)

Action	Effet
Visiter une page	Empile dans historique, vide suivant
Clic sur ← Retour	Dépile historique → empile dans suivant
Clic sur → Suivant	Dépile suivant → empile dans historique

---

Exercice 3 : La classe Navigateur

class Navigateur:
    """Simulateur de navigateur web avec historique."""

    def __init__(self, page_accueil="https://www.google.com"):
        """
        Initialise le navigateur avec une page d'accueil.

        :param page_accueil: (str) URL de la page d'accueil
        """
        self.historique = Pile()
        self.suivant = Pile()
        # À compléter : empiler la page d'accueil

    def page_actuelle(self):
        """
        Renvoie l'URL de la page actuellement affichée.

        :return: (str) URL de la page actuelle ou None
        """
        # À compléter
        pass

    def visiter(self, url):
        """
        Visite une nouvelle page.
        - Empile l'URL dans l'historique
        - Vide la pile 'suivant' (on ne peut plus avancer)

        :param url: (str) URL de la page à visiter
        """
        # À compléter
        pass

    def retour(self):
        """
        Revient à la page précédente (bouton ←).
        - Dépile l'historique
        - Empile la page actuelle dans 'suivant'

        :return: (str) URL de la nouvelle page actuelle ou None si impossible
        """
        # À compléter
        pass

    def avancer(self):
        """
        Avance à la page suivante (bouton →).
        - Dépile 'suivant'
        - Empile dans l'historique

        :return: (str) URL de la nouvelle page actuelle ou None si impossible
        """
        # À compléter
        pass

    def peut_reculer(self):
        """Renvoie True si le bouton Retour est actif."""
        # À compléter
        pass

    def peut_avancer(self):
        """Renvoie True si le bouton Suivant est actif."""
        # À compléter
        pass

    def afficher_etat(self):
        """Affiche l'état actuel du navigateur."""
        retour = "←" if self.peut_reculer() else "✗"
        avancer = "→" if self.peut_avancer() else "✗"
        print(f"[{retour}] [{avancer}] | {self.page_actuelle()}")

Tests à effectuer :

>>> nav = Navigateur()
>>> nav.afficher_etat()
[✗] [✗] | https://www.google.com

>>> nav.visiter("https://www.wikipedia.org")
>>> nav.visiter("https://www.youtube.com")
>>> nav.visiter("https://www.github.com")
>>> nav.afficher_etat()
[←] [✗] | https://www.github.com

>>> nav.retour()
'https://www.youtube.com'
>>> nav.afficher_etat()
[←] [→] | https://www.youtube.com

>>> nav.retour()
'https://www.wikipedia.org'
>>> nav.avancer()
'https://www.youtube.com'

>>> nav.visiter("https://www.python.org")
>>> nav.afficher_etat()
[←] [✗] | https://www.python.org
>>> nav.peut_avancer()
False  # La pile 'suivant' a été vidée

---

Exercice 4 : Historique complet

Ajoutez une méthode pour afficher tout l'historique de navigation :

def afficher_historique(self):
    """
    Affiche l'historique complet de navigation.
    La page actuelle est marquée d'une flèche.
    """
    # À compléter
    pass

Exemple de sortie :

Historique de navigation :
  1. https://www.google.com
  2. https://www.wikipedia.org
  3. https://www.youtube.com
→ 4. https://www.github.com (page actuelle)

---

Partie 3 : File d'attente Netflix

Contexte

Sur Netflix, vous pouvez ajouter des films à votre liste "À regarder". Les films sont regardés dans l'ordre d'ajout (FIFO), mais vous pouvez aussi mettre un film en priorité.

---

Exercice 5 : La classe ListeVisionnage

class ListeVisionnage:
    """Gestionnaire de file d'attente de visionnage."""

    def __init__(self):
        """Initialise une liste de visionnage vide."""
        self.file_attente = File()
        self.historique = Pile()  # Films déjà regardés

    def ajouter(self, titre):
        """
        Ajoute un film/série à la file d'attente.

        :param titre: (str) Titre du contenu à ajouter
        """
        # À compléter
        pass

    def regarder_suivant(self):
        """
        Regarde le prochain élément de la file.
        - Défile le contenu
        - L'ajoute à l'historique

        :return: (str) Titre du contenu regardé ou None
        """
        # À compléter
        pass

    def prochain(self):
        """
        Renvoie le prochain contenu sans le retirer.

        :return: (str) Titre du prochain contenu ou None
        """
        # À compléter
        pass

    def revoir_dernier(self):
        """
        Remet le dernier contenu regardé dans la file (en tête).
        Utile pour revoir un épisode.

        :return: (str) Titre du contenu remis en file ou None
        """
        # À compléter (utiliser une file temporaire ou une autre approche)
        pass

    def afficher(self):
        """Affiche l'état de la liste de visionnage."""
        print("=== Ma Liste Netflix ===")
        print(f"À regarder : {self.file_attente.taille()} élément(s)")
        print(f"Déjà vus : {self.historique.taille()} élément(s)")
        if not self.file_attente.est_vide():
            print(f"Prochain : {self.prochain()}")

Tests à effectuer :

>>> netflix = ListeVisionnage()
>>> netflix.ajouter("Stranger Things S5")
>>> netflix.ajouter("Wednesday S2")
>>> netflix.ajouter("Squid Game S3")
>>> netflix.afficher()
=== Ma Liste Netflix ===
À regarder : 3 élément(s)
Déjà vus : 0 élément(s)
Prochain : Stranger Things S5

>>> netflix.regarder_suivant()
'Stranger Things S5'
>>> netflix.regarder_suivant()
'Wednesday S2'
>>> netflix.afficher()
=== Ma Liste Netflix ===
À regarder : 1 élément(s)
Déjà vus : 2 élément(s)
Prochain : Squid Game S3

>>> netflix.revoir_dernier()
'Wednesday S2'
>>> netflix.prochain()
'Wednesday S2'

---

Exercice 6 : File avec priorité

Netflix permet aussi de mettre un contenu "en haut de la liste". Ajoutez cette fonctionnalité :

def ajouter_prioritaire(self, titre):
    """
    Ajoute un contenu en tête de file (sera regardé en premier).
    Nécessite de reconstruire la file.

    :param titre: (str) Titre du contenu prioritaire
    """
    # Indice : créer une nouvelle file, enfiler le titre prioritaire,
    # puis transvaser l'ancienne file
    pass

Test :

>>> netflix.ajouter("Film 1")
>>> netflix.ajouter("Film 2")
>>> netflix.ajouter_prioritaire("Film URGENT")
>>> netflix.prochain()
'Film URGENT'

---

Partie 4 : Système Undo/Redo

Exercice 7 : Éditeur de texte simplifié

Créez un éditeur qui permet d'annuler (Ctrl+Z) et de refaire (Ctrl+Y) des actions.

class EditeurTexte:
    """Éditeur de texte avec Undo/Redo."""

    def __init__(self):
        """Initialise l'éditeur."""
        self.texte = ""
        self.historique_undo = Pile()  # États précédents
        self.historique_redo = Pile()  # États annulés

    def ecrire(self, texte_ajoute):
        """
        Ajoute du texte.
        Sauvegarde l'état actuel dans l'historique.

        :param texte_ajoute: (str) Texte à ajouter
        """
        # À compléter
        pass

    def effacer(self, n=1):
        """
        Efface les n derniers caractères.

        :param n: (int) Nombre de caractères à effacer
        """
        # À compléter
        pass

    def undo(self):
        """
        Annule la dernière action (Ctrl+Z).

        :return: (bool) True si l'annulation a réussi
        """
        # À compléter
        pass

    def redo(self):
        """
        Refait la dernière action annulée (Ctrl+Y).

        :return: (bool) True si le redo a réussi
        """
        # À compléter
        pass

    def afficher(self):
        """Affiche le texte actuel."""
        undo_dispo = "Ctrl+Z" if not self.historique_undo.est_vide() else "-----"
        redo_dispo = "Ctrl+Y" if not self.historique_redo.est_vide() else "-----"
        print(f"[{undo_dispo}] [{redo_dispo}]")
        print(f"Texte : \"{self.texte}\"")

Tests :

>>> editeur = EditeurTexte()
>>> editeur.ecrire("Bonjour")
>>> editeur.ecrire(" le monde")
>>> editeur.afficher()
[Ctrl+Z] [-----]
Texte : "Bonjour le monde"

>>> editeur.undo()
True
>>> editeur.afficher()
[Ctrl+Z] [Ctrl+Y]
Texte : "Bonjour"

>>> editeur.redo()
True
>>> editeur.afficher()
[Ctrl+Z] [-----]
Texte : "Bonjour le monde"

>>> editeur.effacer(6)
>>> editeur.afficher()
[Ctrl+Z] [-----]
Texte : "Bonjour le"

---

Bonus : Comparaison des complexités

Opération	Pile (liste Python)	File (liste Python)	File (deux piles)
Empile/Enfile	O(1)	O(n)*	O(1) amorti
Dépile/Défile	O(1)	O(1)	O(1) amorti
Sommet/Tête	O(1)	O(1)	O(1)
Est_vide	O(1)	O(1)	O(1)

*L'insertion en début de liste Python est en O(n).

Exercice bonus : Implémentez une file efficace en utilisant deux piles.

---

Résumé des notions

Structure	Principe	Analogie	Cas d'usage
Pile	LIFO	Pile d'assiettes	Historique, Undo, Appels de fonctions
File	FIFO	File d'attente	Impression, Streaming, BFS

---

Auteurs : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.