Implémentation des processus d'ordonnancement

ArchMat 06

Résumé du cours

Pile

Information

Une pile est fondée sur le principe: Last In First Out

  • creer_pile() $\rightarrow$ Pile: crée une pile vide
  • est_vide(p: Pile) $\rightarrow$ bool: renvoie True si la pile est vide, False sinon.
  • empiler(p: Pile, e: T) $\rightarrow$ None: ajoute un élément e au sommet de la pile.
  • depiler(p: Pile) $\rightarrow$ T: retire et renvoie l’élément du sommet de la pile.
class Element:
    def __init__(self, d: int, s: object):
        self.donnees = d
        self.successeur = s


class Pile:
    def __init__(self):
        self.sommet = None

    def est_vide(self) -> bool:
        return self.sommet is None

    def empiler(self, e: int) -> None:
        self.sommet = Element(e, self.sommet)

    def depiler(self) -> int:
        # gestion d'erreur
        if not self.est_vide():
            # récupère la valeur du haut de la pile
            res = self.sommet.donnees
            # retire le sommet
            self.sommet = self.sommet.successeur
            return res
    
    def __str__(self):
        affiche = ""
        last = self.sommet
        while last is not None:
            affiche += str(last.donnees) + "\n"
            last = last.successeur
        return affiche

File

Information

Une file est fondée sur le principe: First In First Out

  • creer_file() $\rightarrow$ File: crée une file vide
  • est_vide(f: File) $\rightarrow$ bool: renvoie True si la file est vide, False sinon.
  • enfiler(f: File, e: T) $\rightarrow$ None: ajoute un élément e à la fin de la File.
  • defiler(f: File) $\rightarrow$ T: retire et renvoie l’élément du début de la file.
class File:
    def __init__(self):
        self.premier = None
        self.dernier = None

    def est_vide(self) -> bool:
        return self.premier == None

    def enfiler(self, e: int) -> None:
        nouveau = Element(e, None)

        if self.est_vide():
            # 1 seul élément: le premier est le dernier
            self.premier = nouveau
        else:
            # le dernier devient avant-dernier
            self.dernier.successeur = nouveau

        # le nouveau devient dernier
        self.dernier = nouveau

    def defiler(self) -> int:
        if not self.est_vide():
            res = self.premier.donnees
            self.premier = self.premier.successeur
            return res

    def __str__(self):
        c = self.premier
        s = ""
        while not c is None:
            s = s + str(c.donnees)+"|"
            c = c.successeur
        return "\u2BA4|" + s + "\u2BA0"