Types de données abstraits

Pile - File - File de priorité

En plus des structures de données concrètes vues jusqu'ici, on considère trois types de données abstraits (TDA) qui décrivent un comportement particulier.

• Pile (stack)
• File (queue)
• File de priorité (priority queue)

Ces types restreignent la manière dont les éléments peuvent être

• insérés
• accédés
• supprimés

Pile

Une pile (stack en anglais) est une structure linéaire qui ne permet d'insérer / d'accéder à / de supprimer que d'un seul coté appelé sommet.

Elle suit le principe dernier entré, premier sorti ou Last In, First Out (LIFO)

Les opérations de bases sont

• empiler (push)
• dépiler (pop)
• accéder à / modifier le sommet (top)

auxquelles s'ajoutent en général copier, comparer l'égalité ou l'équivalence, déterminer si la pile est vide, la vider, ...

Une pile peut être mise en oeuvre par presque toutes les structures concrètes vues ici

Structure	Sommet
tableau de taille variable	queue
tableau de capacité variable	queue
liste simplement chainée	tête
liste doublement chainée	tête ou queue
deque	tête ou queue

Les structures les plus naturelles sont les tableaux et la liste simplement chainée.

Les piles ont de nombreuses applications

• Bouton undo dans un traitement de texte

• Bouton back dans un browser web

• Stockage des addresses de retour lors d'appels de fonctions

• Dérécursification explicite d’un algorithme récursif

• Evaluation d'expressions (voir la suite)

File

Une file (queue en anglais) est une structure linéaire qui insère d'un coté (queue) et supprime de l'autre (tête).

Elle suit le principe premier entré, premier sorti ou First In, First Out (FIFO)

Les opérations de bases sont

• enfiler en queue (push)
• défiler en tête (pop)
• accéder à / modifier la tête (front)
• accéder à / modifier la queue (back)

auxquelles s'ajoutent en général copier, comparer l'égalité ou l'équivalence, déterminer si la file est vide, la vider, ...

Une file peut être mise en oeuvre par les structures concrètes permettant insertion en queue et suppression en tête.

• buffer circulaire

• liste simplement chainée stockant deux pointeurs (tête et queue)

• liste doublement chainée

• deque

Les files ont de nombreuses applications

• mémoriser temporairement des transactions en attente de traitement

• tampon (buffer) pour les caractères entrés au clavier

• file d'attente pour les serveurs d'impression

• distribution équitable du temps-machine entre les tâches dans un système d'exploitation

Nous l'utiliserons par la suite pour le parcours en largeur des structures d'arbre et de graphe

File de priorité

Une file de priorité (priority queue en anglais) est une structure linéaire associée à un critère de priorité permettant d'ordonner les éléments.

Les opérations de bases sont

• insérer un élément (push)
• accéder à l'élément le plus prioritaire (top)
• supprimer l'élément le plus prioritaire (pop)

auxquelles s'ajoutent en général copier, comparer l'égalité ou l'équivalence, déterminer si la file est vide, la vider, ...

La mise en oeuvre la plus efficace consiste à utiliser un tas (heap)

Les files de priorité ont de nombreuses applications

• Compression de données - code de Huffman (PKZIP, JPEG, MP3)

• Algorithmes sur les graphes - Dijkstra , Prim (ASD2)

• Simulation à événements discrets - clients en attente, collision de particules, …

• Statistiques - recherche de M plus grandes valeurs dans un ensemble

• Système d’exploitation - balance de charge, gestion des interruptions

Application

Une application classique du TDA pile consiste à évaluer une expression mathématique infixe telle que

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Elle est basée sur l'algorithme Shunting-yard de Edsger Dijkstra qui convertit les expressions infixes en expressions postfixes (chapitre 5)

Dans cette variante, nous utilisons 2 piles.

• une pile de valeurs numériques
• une pile d'opérateurs

Utilisons une classe stack simple pour nos piles

class stack:
    def __init__(self):
        self.__T = []
        
    def push(self,val):
        self.__T.append(val)
    
    def pop(self):
        return self.__T.pop()
    
    def top(self):
        return self.__T[len(self.__T)-1]
    
    def __str__(self):
        s = ""
        for el in self.__T: 
            s += el.__str__() + " "
        return s

Définissons les opérateurs disponibles et leurs mises en oeuvres

operateurs = [ "+", "-", "*", "/"]

def appliquer_operateur(gauche,operateur,droite):
    
    if   operateur == "+": 
        return gauche + droite
    
    elif operateur == "-": 
        return gauche - droite
    
    elif operateur == "*":
        return gauche * droite
    
    elif operateur == "/": 
        return gauche // droite
    
    raise ArithmeticError()

L'algorithme d'évaluation distingue les parenthèses, les opérateurs et les valeurs numériques. Les parenthèses droites évaluent les opérations

def evaluer_expression(expression):     
    pileOp = stack(); pileVal = stack()
    
    for el in expression.split(" "):    
        if el == "(": pass
        
        elif el in operateurs: pileOp.push(el)
        
        elif el != ")":  pileVal.push(int(el))
        
        else: # el est une parenthèse droite     
            droite = pileVal.pop()
            gauche = pileVal.pop()
            op = pileOp.pop()
            resultat = appliquer_operateur(gauche,op,droite)
            pileVal.push(resultat)
    
    return pileVal.pop()

evaluer_expression("( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )")

el  | pileOp     | pileVal    
----|------------|------------
(   |            |            
1   |            | 1          
+   | +          | 1          
(   | +          | 1          
(   | +          | 1          
2   | +          | 1 2        
+   | + +        | 1 2        
3   | + +        | 1 2 3      
)   | +          | 1 5        
*   | + *        | 1 5        
(   | + *        | 1 5        
4   | + *        | 1 5 4      
*   | + * *      | 1 5 4      
5   | + * *      | 1 5 4 5    
)   | + *        | 1 5 20     
)   | +          | 1 100      
)   |            | 101        

101

evaluer_expression("( ( 2 + 3 ) * ( 4 / ( 3 - 1 ) ) )")

el  | pileOp     | pileVal    
----|------------|------------
(   |            |            
(   |            |            
2   |            | 2          
+   | +          | 2          
3   | +          | 2 3        
)   |            | 5          
*   | *          | 5          
(   | *          | 5          
4   | *          | 5 4        
/   | * /        | 5 4        
(   | * /        | 5 4        
3   | * /        | 5 4 3      
-   | * / -      | 5 4 3      
1   | * / -      | 5 4 3 1    
)   | * /        | 5 4 2      
)   | *          | 5 2        
)   |            | 10         

10

ASD1 Notebooks on GitHub.io © Olivier Cuisenaire, 2018