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

Rappel sur la notion d'interface
On appelle interface d’une structure de données l’ensemble des opérations et attributs à associer à cette structure de données pour permettre sa manipulation.

En POO, cela équivaut à l’ensemble des attributs et méthodes publiques.

  • 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 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
####################################################################################
# Déclaration des Types
####################################################################################
class Maillon():
    def __init__(self, data = None, suiv = None):
        self.data = data    # peut être de n'importe quel type !
        self.suiv = suiv    # adresse (en Python, on pointe directement vers un Maillon)

    def __repr__(self):
        return str(self.data) + "→"


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

    def __repr__(self):
        m = self.tete
        s = ""
        while m is not None:
            s += str(m)
            m = m.suiv
        return s
    
    ############################################################################
    def est_vide(self):
        """ Renvoie True si la liste est vide
        """
        return self.debut is None

    ############################################################################
    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 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 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

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 conteneur de données.

 

À l’aide de seulement 3 méthodes de la classe ListeC , réaliser l’interface complète de cette pile (méthodes est_vide, empiler, et depiler).

 

À l’aide uniquement des 3 méthodes de l’interface de Pile , réaliser une méthode de représentation (__repr__).

 

Avec un Tableau

Définir en Python une classe Pile en utilisant une liste Python comme conteneur de données.
À 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 = [] # attribut privé : on ne doit utiliser que l'interface élémentaire

    def __repr__(self):
        """ La même que précédemment ...
        """
        return

    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

Tamisage
Écrire une fonction pairs qui prend en entrée une pile d’entiers et qui la modifie en supprimant les entiers pairs, qui sont renvoyés dans une nouvelle pile.

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
8
6
3
2
5
4
1
>>> pairs(P)
8
6
2
4
>>> P
3
5
1
Donner l'ordre de complexité de cette fonction.

 

 

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].

 

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.

 

 

 

 

 

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

Définir une classe File en utilisant un maillon de liste chainée. (voir module listes_chainnees plus haut).

À l’aide uniquement des 3 méthodes de l’interface de File , réaliser une méthode de représentation (__repr__).

 

Avec 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):
        """ 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

Définir en Python une classe File en utilisant une liste Python comme conteneur de données.
À l’aide de seulement 2 méthodes et une fonction, réaliser l’interface complète de cette file.
Correction (ne pas regarder !)
class File:
    def __init__(self):
        self._l = [] # attribut privé : on ne doit utiliser que l'interface élémentaire

    def __repr__(self):
        """ La même que précédemment ...
        """
        return

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

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

    def emfiler(self, n):
        self._l.append(n)

 

 

Quelques exercices

Exercice : modélisation d'une 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
  • int nc : nombre de clients
  • list int etat_g : état de chaque guichet = temps que le client doit encore passer au guichet = un entier qui diminue au fil du temps (0 = guichet libre)
  • list int durees_client : durées (en unité de temps) que doivent passer chacun des clients au guichet, nombres entre duree_mini et duree_maxi
  • list File files : les files d'attentes (une seule ou bien une par guichet)

On peut par exemple commencer avec ces paramètres :

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

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

 

 

Correction
from piles_files import *
from random import randint

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


nc = 1000 # nombre de clients
duree_mini = 3
duree_maxi = 30
durees_client = [randint(duree_mini, duree_maxi) for _ in range(nc)]
durees_clients = sum(durees_client)
print("Dureée totale clients :", durees_clients)

def resultat(tick, ng, durees_clients):
    return round(100* durees_clients/ng/tick, 1)

##################################################################################
# Une unique FILE d'attente

# On remplit la file
file = File()
for i in range(nc):
    file.enfiler(durees_client[i])

# On démarre
tick = 0
while not file.est_vide() or any(etat_g):
    # recherche d'un guichet libre
    for g, etat in enumerate(etat_g):
        if etat == 0: 
            if not file.est_vide():
                etat_g[g] = file.defiler()+1 # un client va au guichet
    
    # une unité de temps s'écoule ...
    for g, etat in enumerate(etat_g):
        if etat > 0:
            etat_g[g] -= 1
    tick += 1
print("        File unique :", tick, resultat(tick, ng, durees_clients))

##################################################################################
# Une FILE d'attente par guichet

# On remplit les files, au hasard
files = []
for g in range(ng):
    files.append(File())
for i in range(nc):
    files[randint(0, ng-1)].enfiler(durees_client[i])


# On démarre
tick = 0
while any([not f.est_vide() for f in files]) or any(etat_g):
    for g, etat in enumerate(etat_g):
        if etat == 0:
            if not files[g].est_vide():
                etat_g[g] = files[g].defiler()+1 # un client va au guichet

    # une unité de temps s'écoule ...
    for g, etat in enumerate(etat_g):
        if etat > 0:
            etat_g[g] -= 1
    tick += 1
print("     File au hasard :", tick, resultat(tick, ng, durees_clients))



# On remplit les files, au fur et a mesure, la plus courte d'abord
files = []
for g in range(ng):
    files.append(File())
ncf = 4*ng  # nombre de clients en attente (pour que les client puissent comparer leur taille)
tailles_files = [0]*ng  # les tailles de chacune des files (on mémorise à chaque opération sur la file)

def minFile(tailles_files):
    """ Renvoie l'indice de la plus petite file
        dont les tailles sont dans tailles_files
    """
    mf = tailles_files[0] # taille de la file la plus courte
    f = 0  # indice de la file la plus courte
    for g, tf in enumerate(tailles_files[1:]):
        if tf < mf:
            mf = tf
            f = g+1
    return f


# On préremplit les files (pas complètement)
for i in range(ncf):
    f = minFile(tailles_files)
    files[f].enfiler(durees_client[i])
    tailles_files[f] += 1

# On démarre
tick = 0
nct = ncf # nombre de clients arrivés (en file d'attente, au guichet, ou bien sortis)
while any([not f.est_vide() for f in files]) or any(etat_g):

    ncp = 0 # nombre de clients quittant les files d'attente
    # on avance les files d'attente
    for g, etat in enumerate(etat_g):
        if etat == 0:
            if not files[g].est_vide():
                etat_g[g] = files[g].defiler()+1 # un client va au guichet
                tailles_files[g] -= 1
                ncp += 1
    #print(" ", ncp)
    # on recomplète les files d'attente
    for i in range(ncp):
        if nct+i >= len(durees_client):
            break
        f = minFile(tailles_files)
        files[f].enfiler(durees_client[nct+i])
        tailles_files[f] += 1
        #ncp += 1
    #print(nct)
    nct += ncp

    # une unité de temps s'écoule ...
    for g, etat in enumerate(etat_g):
        if etat > 0:
            etat_g[g] -= 1
    tick += 1

#print(nct)
print("File la plus courte :", tick, resultat(tick, ng, durees_clients))

 

Vous aimerez aussi...

Laisser un commentaire

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