Piles et Files

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.

  • Insérer 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 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

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

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

Définir en Python une classe Pile  en utilisant une liste chaînée (objet de type ListeC du module listes_chainees) comme attributAttribut Un attribut est un identifiant (un nom) décrivant une information stockée dans une base. Les attributs correspondent aux colonnes si la relation à laquelle il appartient est représentée sous forme de table..

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.

 

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

 

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

Line Queue ClipartUne 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

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

 

 

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 mode 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 de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code