Créer une file avec une liste doublement chaînée

Une file est une structure de données linéaire qui suit le principe FIFO (First In First Out). Cela signifie que le premier élément ajouté à la file sera le premier à en sortir. Nous allons implémenter une file en utilisant une liste doublement chaînée.

Définition de la classe Noeud

La première étape consiste à définir une classe pour les nœuds de la liste doublement chaînée. Chaque nœud contiendra une valeur, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None
        self.precedent = None
    

Définition de la classe File

Ensuite, nous définissons la classe File qui utilisera les nœuds pour gérer les éléments de la file.

class File:
    def __init__(self):
        self.tete = None
        self.queue = None

    def estVide(self):
        return self.tete is None

    def enfile(self, valeur):
        nouveau_noeud = Noeud(valeur)
        if self.estVide():
            self.tete = nouveau noeud
            self.queue = nouveau_noeud
        else:
            self.queue.suivant = nouveau_noeud
            nouveau_noeud.precedent = self.queue
            self.queue = nouveau_noeud

    def defile(self):
        valeur = self.tete.valeur
        self.tete = self.tete.suivant
        if self.tete is not None:
            self.tete.precedent = None
        else:
            self.queue = None
        return valeur
    

Exemple d'utilisation

Voici un exemple d'utilisation de la classe File :

maFile = File()
maFile.enfile(1)
maFile.enfile(2)
maFile.enfile(3)
print(maFile.defile())  # Affiche 1
print(maFile.defile())  # Affiche 2
print(maFile.defile())  # Affiche 3