Piles et Files

par · Publié · Mis à jour

Pile

Stack Of Plates Png - Dishes Stack Png Clipart@pikpng.com

Une Pile (ou Stack) est une structure de données linéaire dans laquelle les éléments sont accessibles selon une discipline LIFO (“Last-In First-Out”) : l’élément inséré en dernier est le premier à sortir.

  • Ajouter un élément dans la pile est appelé empiler ou pousser (push)
  • Supprimer un élément de la pile est appelé dépiler (pop)

L’accès aux objets de la pile se fait grâce à un unique pointeur vers le sommet de la pile, appelé top.

 

Interface

  • est_vide(S) renvoie vrai si la pile S est vide
  • push(S, e) empile la valeur e  sur la pile S
  • pop(S) extrait et renvoie la valeur sur le sommet de la pile S

 

Coût en temps

  • Obtenir l’élément placé sur le dessus d’une pile : cout constant \(\mathcal{O}(1)\)
  • Obtenir l’élément placé en bas d’une pile : coût linéaire \(\mathcal{O}(n)\)
  • Obtenir ne nombre d’éléments contenus dans une pile : coût linéaire \(\mathcal{O}(n)\)

 

Applications

  • Fonctionnalité Undo/Redo dans les logiciels
  • Analyse syntaxique
  • …

 

Implémentations

Avec une Liste chainée

Voici un module contenant une classe de liste chainée ListeC, possédant, en autres, les méthodes .est_vide() , .ajouter_debut(m) ,  .ajouter_fin(m) , .supprimer_debut(), ……..

Module listes_chainees.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-


####################################################################################
# Déclaration des Types
####################################################################################
class Maillon():
    def __init__(self, data = None):
        self.data = data
        self.suiv = None # adresse (en Python, on pointe directement vers un Maillon)

    def __repr__(self):
        return self.data.__repr__()


    # Structures récursives
    def taille_suite(self):
        if self.suiv is None:
            return 1
        return 1+self.suiv.taille_suite()


    def get_dernier_suite(self):
        if self.suiv is None:
            return self
        return self.suiv.get_dernier_suite()


####################################################################################
class ListeC():
    def __init__(self):
        self.debut = None # adresse (en Python, on pointe directement vers un Maillon)

    def __repr__(self):
        m = self.debut
        l = []
        while m is not None:
            l.append(m.__repr__())
            m = m.suiv
        return " ".join(l)


    def est_vide(self):
        """ Renvoie True si la liste est vide
        """
        return self.debut is None


    def taille(self):
        """ Renvoie le nombre de maillons de la liste
        """
        m = self.debut
        l = 0
        while m is not None:
            l += 1
            m = m.suiv
        return l


    def taille_r(self):
        """ Renvoie le nombre de maillons de la liste
            Version récursive
        """
        if self.est_vide():
            return 0
        return self.debut.taille_suite()


    ############################################################################
    def get_dernier(self):
        """ Renvoie le dernier maillon de la liste
            IndexError si la liste est vide
        """
        if self.est_vide():
            raise IndexError("list index out of range")
        m = self.debut
        while m.suiv is not None:
            m = m.suiv
        return m


    def get_dernier_r(self):
        """ Renvoie le dernier maillon de la liste
            IndexError si la liste est vide
            Version récursive
        """
        if self.est_vide():
            raise IndexError("list index out of range")
        return self.debut.get_dernier_suite()


    def get_maillon_indice(self, i):
        """ Renvoie le maillon d'indice i
            IndexError si l'indice ne pointe pas dans la liste
        """
        m = mp = self.debut
        j = 0
        while j <= i:
            if m is None:
                raise IndexError("list index out of range")
            mp = m
            m = m.suiv
            j += 1
        return mp

    ############################################################################
    def ajouter_fin(self, nM):
        """ Ajoute un maillon à la fin de la liste
            Si nM n'est pas de type Maillon, le maillon est créé
            Renvoie le maillon ajouté
        """
        if not isinstance(nM, Maillon):
            nM = Maillon(nM)
        if self.est_vide():
            self.debut = nM
        else:
            dm = self.get_dernier()
            dm.suiv = nM
        return nM


    def ajouter_debut(self, nM):
        """ Ajoute un maillon au début de la liste
            Si nM n'est pas de type Maillon, le maillon est créé
            Renvoie le maillon ajouté
        """
        if not isinstance(nM, Maillon):
            nM = Maillon(nM)
        if self.est_vide():
            self.debut = nM
        else:
            nM.suiv = self.debut
            self.debut = nM
        return nM


    def inserer_apres(self, i, nM):
        """ Insère un maillon après le maillon d'indice i
            Si nM n'est pas de type Maillon, le maillon est créé
            IndexError si l'indice ne pointe pas dans la liste
            Renvoie le maillon ajouté
        """
        m = self.get_maillon_indice(i)
        if m is None:
            raise IndexError("list index out of range")
        nM.suiv = m.suiv
        m.suiv = nM
        return nM


    ############################################################################
    def supprimer_debut(self):
        """ Supprime et renvoie le premier maillon de la liste
            IndexError si la liste est vide
        """
        if self.debut is not None:
            d = self.debut
            self.debut = self.debut.suiv
            return d
        else:
            raise IndexError("list index out of range")


    def supprimer_fin(self):
        """ Supprime et renvoie le dernier maillon de la liste
            IndexError si la liste est vide
        """
        if self.est_vide():
            raise IndexError("list index out of range")
        m = self.debut
        a = None                # avant dernier
        while m.suiv is not None:
            a = m
            m = m.suiv
        if a is None:
            self.debut = None
            return
        else:
            a.suiv = None
            return m


    def supprimer_indice(self, i):
        """ Supprime le Maillon d'indice i de la liste
            IndexError si l'indice ne pointe pas dans la liste
        """
        if self.est_vide():
            raise IndexError("list index out of range")
        if i > 0:
            m = self.get_maillon_indice(i-1)
            if m.suiv is None:
                raise IndexError("list index out of range")
            m.suiv = m.suiv.suiv
        else:
            self.supprimer_debut()



    ############################################################################
    def renverser(self):
        """ Inverse la liste "sur place"
        """
        m = self.debut      # adresse maillon courant
        p = None         # prochaine adresse à écrire

        while m is not None:
            s = m.suiv # adresse maillon suivant
            m.suiv = p
            p = m
            m = s

        self.debut = p


    ############################################################################
    def concatener(self, L):
        """ Concaténation la liste avec une autre Liste L
            Ne renvoie rien : modification de la liste "sur place"
        """
        d = self.get_dernier()
        d.suiv = L.debut


    ############################################################################
    def __add__(self, L):
        """ Concaténation la liste avec une autre Liste L
            Renvoie une nouvelle liste
        """
        nL = ListeC()
        nL.debut = self.debut
        nL.concatener(L)
        return nL


if __name__ == "__main__":
    L1 = ListeC()
    L1.ajouter_fin(1)
    L1.ajouter_fin(Maillon(2))
    L1.ajouter_fin(Maillon(3))
    print(L1)

    L1.supprimer_indice(0)
    print(L1)

On peut utiliser les classes de ce module dans un autre programme en utilisant l’instruction :

from listes_chainees import *
Définir en Python une classe Pile  en utilisant une liste chaînée (objet de type ListeC du module listes_chainees) comme attribut.
A l’aide de seulement 3 méthodes de la classe ListeC , réaliser l’interface complète de cette pile.

 

Avec un Tableau

Définir en Python une classe Pile en utilisant une liste Python comme attribut.
A l’aide de seulement 2 méthodes et une fonction, réaliser l’interface complète de cette pile.
Correction (ne pas regarder !)
class Pile:
    def __init__(self):
        self.l = []

    def __repr__(self):
        return str(self.l)

    def is_empty(self):
        return len(self.l) == 0

    def pop(self):
        return self.l.pop()

    def push(self, n):
        self.l.append(n)

if __name__ == "__main__":
    p = Pile()
    p.push(1)
    p.push(2)
    p.push(3)
    print(p)
    print(p.pop())
    print(p)

 

Exercice : entre parenthèses
Implémenter en Python, en utilisant une pile, une fonction permettant de vérifier l’appariement de parenthèses ([] , ()  ou {}) dans une chaîne de caractères.

Exemples : [(x)+(y)]/{2*a-sin(x)}  → True

[-(b)+sqrt(4*(a*c)])/(2*a)  → False

Pour aller plus loin …

Modifier cette fonction de sorte qu’elle renvoie les associations de « parenthèses » : pour chaque indice de caractère de la chaîne, s’il s’agit d’une « parenthèse », l’indice de la « parenthèse » associée est spécifié.

Exemples : [(x)+(y)]/{2*a-sin(x)}  → [8, 3, None, 1, None, 7, None, 5, 0, None, 21, None, None, None , None, None, None, None, 20, None, 18, 10].

 

Exercice : RPN

L’écriture polonaise inverse des expressions mathématiques place l’opérateur après les opérandes. Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité.

Exemples :  (1+2*3)*4 s’écrit en notation polonaise inverse 1 2 3 * + 4 *.

Pour évaluer une telle expression, on utilise une pile pour stocker tous les résultats intermédiaires. Les éléments de l’expression sont évalués un à un :

  • s’il s’agit d’un nombre, on le place au sommet de la pile,
  • s’il s’agit d’une opérande, on réalise l’opération avec les deux premiers nombres de la pile (le deuxième « par » le premier), puis on replace le résultat sur la pile.

Si l’expression est bien écrite, à la fin du processus, la pile ne comporte plus que le résultat final.

Écrire une fonction rpn(expr) permettant d’évaluer une expression polonaise inverse composée des opérateurs + - *  / , et dont les éléments sont séparés par des espaces.
Si l’expression est mal écrite, la fonction doit renvoyer une erreur de type SyntaxError.

 

Tamisage
Écrire une fonction pairs qui prend en entrée une pile d’entiers et qui modifie la pile en supprimant les entiers pairs et fournit en sortie la liste des entiers pairs supprimés.

Par exemple (avec la classe Pile à base de liste Python définie plus haut) :

>>> P = Pile()
>>> P.push(1)
>>> P.push(4)
>>> P.push(5)
>>> P.push(2)
>>> P.push(3)
>>> P.push(6)
>>> P.push(8)
>>> P
[1, 4, 5, 2, 3, 6, 8]
>>> pairs(P)
[4, 2, 6, 8]
>>> P
[1, 5, 3]
Donner l’ordre de complexité de cette fonction.

 

 

 

File

Une File (ou Queue) est une structure de données linéaire dans laquelle les éléments sont accessibles selon une discipline FIFO (“First-In First-Out”) : le premier élément inséré dans la liste est le premier à en sortir.

  • Insérer un élément dans la file est appelé enfiler (enqueue)
  • Supprimer un élément de la file est appelé défiler (dequeue)

L’accès aux objets de la file se fait grâce à deux pointeurs, l’un pointant sur l’élément qui a été inséré en premier et l’autre pointant sur celui inséré en dernier.

Interface

  • enfiler(F, e)  ajoute l’élément e  à la queue de la file F
  • defiler(F)  retire et renvoie l’élément à la tête de la file F

 

Coût en temps

  • Obtenir l’élément placé en tête de file : cout constant \(\mathcal{O}(1)\)
  • Obtenir l’élément placé en queue de file : coût linéaire \(\mathcal{O}(n)\)
  • Obtenir ne nombre d’éléments contenus dans une file : coût linéaire \(\mathcal{O}(n)\)

 

Applications

  • Mémoire tampon (buffer)
  • …

Implémentations

Liste chainée

Définir une classe File en utilisant des maillons de liste chainée.

 

Deux piles

Définir en Python une classe File à l’aide de deux objets entree et sortie de type Pile (en utilisant une des classes Pile définies plus haut).

Correction (ne pas regarder !)
class File:
    def __init__(self):
        self.entree = Pile()
        self.sortie = Pile()

    def __repr__(self):
        return self.entree.__repr__()
    
    def est_vide(self):
        return self.entree.est_vide() and self.sortie.est_vide()
        
    def enfiler(self, n):
        # On remet la pile d'entrée en place avant de pousser
        while not self.sortie.est_vide(): 
            self.entree.push(self.sortie.pop())
        self.entree.push(n)
        
    def defiler(self):
        if self.sortie.est_vide():
            raise IndexError("defilage d'une file vide")
        while not self.entree.est_vide():
            self.sortie.push(self.entree.pop())
        return self.sortie.pop()  # L'élément qu'il faut renvoyer

 

 

Exercice : file d'attente

L’objectif de l’exercice est de modéliser puis simuler le comportement d’une file d’attente (magasin, service public, …).

Plusieurs modes sont envisageables :

  • Une seule file pour plusieurs guichets
  • Une file par guichet,
    • chaque client choisit une file au hasard
    • chaque client choisit la file la moins longue

Puisqu’il s’agit de comparer des performances de durée entre plusieurs solutions, il faut compter le temps qui s’écoule. Le temps sera donc rythmé par une variable tick (horloge) qui augmentera à chaque itération et pourra représenter une unité de temps (par exemple des minutes).

Les données initiales du modèle sont les suivantes :

  • int ng : nombre de guichets
  • list int etat_g : état de chaque guichet = temps que le client doit passer au guichet = un entier qui diminue au fil du temps (0 = guichet libre)
  • list File files : les files d’attentes

 

 

 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *