Piles et Files

Pile

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 (top) de la pile.

Interface élémentaire

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

ATTENTION ! on ne peut dépiler un élément qu’une seule fois ! Une fois dépilé, il n’est plus sur la pile !

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 le nombre d’éléments contenus dans une pile : coût linéaire \(\mathcal{O}(n)\)

Applications

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

Opérations

Parcourir tous les éléments d’une pile (pour les afficher par exemple) :

Inconvénient : à la fin de l’opération, la pile initiale est vide !!

Pour éviter cela, on peut employer une pile temporaire, sur laquelle on empile les éléments avant de les afficher :

Mais cette pile temporaire se retrouve inversée par rapport à la pile initiale.

Il faut la reconstruire : on dépile la pile temporaire et on rempile celle d’origine.

Implémentations

Avec une Liste chaînée

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

####################################################################################
# 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):
        t = str(self.data)
        if self.suiv is not None:
            return t + "→"
        return t + "x"


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

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

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


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


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


    ############################################################################
    def ajouter_fin(self, v):
        """ Ajoute un élément à la fin de la liste chaînée
        """
        nM = Maillon(v)
        if self.est_vide():
            self.tete = nM
        else:
            dm = self.get_dernier()
            dm.suiv = nM


    def ajouter_debut(self, v):
        """ Ajoute un élément au début de la liste chaînée
        """
        nM = Maillon(v)
        if self.est_vide():
            self.tete = nM
        else:
            nM.suiv = self.tete
            self.tete = nM


    ############################################################################
    def supprimer_debut(self):
        """ Supprime et renvoie le premier élément de la liste chaînée
            IndexError si la liste est vide
        """
        if self.tete is not None:
            m = self.tete
            self.tete = self.tete.suiv
            return m.data
        else:
            raise IndexError("listeC index out of range")


    def supprimer_fin(self):
        """ Supprime et renvoie le dernier élément de la liste chaînée
            IndexError si la liste est vide
        """
        if self.est_vide():
            raise IndexError("listeC index out of range")
         
        m = self.tete
        if m.suiv is None: # 1 seul élément
            self.tete = None
            return m.data

        a = None                # avant dernier
        while m.suiv is not None:
            a = m
            m = m.suiv
        a.suiv = None
        return m.data

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

from listes_chainees import ListeC

Avec un Tableau

class Pile:
    def __init__(self):
        self.__l = [] # attribut privé : on ne doit utiliser que l'interface élémentaire
        # Pour internationaliser les méthodes :
        self.pop = self.depiler
        self.push = self.empiler
        self.is_empty = self.est_vide
    def __repr__(self): 
        l = [] 
        p = Pile()
        m = 0
        while not self.est_vide(): 
            c = self.depiler() 
            l.append(str(c)) 
            p.empiler(c)
            m = max(m, len(str(c)))

        # on reconstruit la Pile d'origine 
        while not p.est_vide(): 
            self.empiler(p.depiler())
        
        # Pour afficher une bordure : 
        for i in range(len(l)): 
            l[i] = "│" + l[i].ljust(m) +"│" 
        
        return "\n".join(l) + "\n└"+ m*"─" + "┘"
    
    def est_vide(self):
        return len(self.__l) == 0

    def depiler(self):
        return self.__l.pop()

    def empiler(self, n):
        self.__l.append(n)

Quelques exercices

>>> P = Pile()
>>> P.push(1)
>>> P.push(4)
>>> P.push(5)
>>> P.push(2)
>>> P.push(3)
>>> P.push(6)
>>> P.push(8)
>>> P
8
6
3
2
5
4
1
>>> pairs(P)
8
6
2
4
>>> P
3
5
1

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
• [-(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].

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 élémentaire

• est_vide(F) ou is_empty(F)renvoie vrai si la file F est vide
• 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 le nombre d’éléments contenus dans une file : coût linéaire \(\mathcal{O}(n)\)

Applications

• Mémoire tampon (buffer)
• Mise en attente
• …

Opérations

Parcourir tous les éléments d’une file (pour les afficher par exemple) :

Inconvénient : à la fin de l’opération, la file initiale est vide !!

Pour éviter cela, on peut employer une file temporaire, dans laquelle on enfile les éléments avant de les afficher :

La file initiale étant vide, il faut la re-remplir :

Implémentations

Avec une liste chainée

Avec deux piles

class File:
    def __init__(self):
        self.entree = Pile()
        self.sortie = Pile()

    def __repr__(self):
        """ La même que précédemment ... """ 
        return
    
    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

Avec un tableau

class File:
    def __init__(self):
        self.__p = []
        self.dequeue = self.defiler
        self.enqueue = self.enfiler
        self.is_empty = self.est_vide

    def __repr__(self):
        l = []
        p = File()

        while not self.est_vide():
            c = self.defiler()
            p.enfiler(c)
            l.append(str(c))
            
        while not p.est_vide():
            self.enfiler(p.defiler())

        t = " ".join(l)
        
        return " "+len(t)*"─" +"\n"+ "→"+t +"\n "+ len(t)*"─"

    def est_vide(self):
        return len(self.__p) == 0

    def enfiler(self, v):
        self.__p.append(v)

    def defiler(self):
        return self.__p.pop(0)

Quelques exercices

class Panier(File):
    def __init__(self):
        super().__init__()

ng = 10 # nombre de guichets 
etat_g = [0]*ng 

nc = 1000 # nombre de clients 
duree_mini = 3 
duree_maxi = 30