Structures de données IFT-10541 Abder Alikacem Les piles Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de donnéesIFT-10541

Abder AlikacemAbder Alikacem

Les piles

Département d’informatique et de génie logiciel

Édition Septembre 2009

! +

Plan

• Introduction et exemples d’application• Description en terme de type abstrait• Implantation

Piles

Piles :

LIFO : last in, first outDAPS : dernier arrivé, premier sorti

ex. : assiettes

livresfacturespile d’exécutionévaluation d’expressions

in out

pile

Files

Files :

FIFO : first in, first outPAPS : premier arrivé, premier sorti

ex. : assiettesfacturesbanquechaîne de montageimprimantetâches à exécuter

out in

file

Piles et files

Structures de données auxiliaires• car utilisées par d’autres structures

(comme les listes ordonnées)

Utilité :• support à des applications• support à d’autres structures de données• modélisation de la réalité• en informatique : système d’exploitation

gestion interne évaluation d ’expressions etc.

Piles

Spécification Une pile est une structure de données abstraite contenant des éléments

homogènes (de type non précisé) à 1 point d’accès et permettantd’ajouter une valeur à la pile (empiler ou push);de lire la dernière valeur ajoutée ;d’enlever la dernière valeur ajoutée (dépiler ou pop);de tester si la pile est vide.

On ne « connait » donc de la pile que le dernier élément empilé (sonsommet).

Spécification physique liste chaînéeoutableau statique ou dynamique

Piles

• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :

pile

Piles


• ajouter un nouvel élément sur la pile (empiler)

in

pile

Piles



pile

Piles



• enlever un élément de la pile (dépiler)

out

pile

Piles




out

pile

Piles




• consulter le premier élément de la pile

pile

Piles




• consulter le premier élément de la pile

pile

Piles




• regarder le premier élément de la pile

• indiquer si la pile est vide

pile

Piles






• vérifier si un élément est sur la pile

pile

?

Piles







pile

?

Piles







pile

?

Piles







pile

?

!

Piles






• regarder si un élément est sur la pile

• remplacer un élément sur la pile

pile








pile

Piles








les noms anglais pour ces opération sont: PUSH—EMPILER, POP—DÉPILER, TOP—SOMMET, PEEP—EXAMINER et CHANGE—CHANGER.

pile

Piles

Préoccupation de la programmation par objet

initialiser une pile (constructeurs); détruire une pile de ses éléments (destructeur); Constructeur de copie; Surcharge de l’opérateur =

Piles

pile

Vue externe

La pile est une structure monolithique, c.-à-d. qu'une pile n'est pas construite à l'aide de sous-piles. Pour cette raison les opérations de Mise à jour ne vont pas créer de nouvel objet Pile mais uniquement modifier l'état de la pile qui reçoit le message.

Piles

Pile = liste + gestion adaptée

manipulations (empiler et dépiler) par le même point d’accès

in

out

pile pile

out

in

• empiler (push) :


• empiler (push) :• L L +1 x (ou : L L +|L|+1 x)



• dépiler (pop) :



• dépiler (pop) :• L -1L (ou : L -|L|L)




• sommet (top) :




• sommet (top) :• L1 (ou : L|L|)





• pile vide ?





• pile vide ?• L = ?






• élément sur la pile (peep) ?






• élément sur la pile (peep) ?• x L?














• remplacer un élément sur la pile• x = L?; L -?L; L L +? y


Piles : spécifications de l’interface

empiler : p p + x• prototype :

void empiler(TypeEl x);

/** * \brief Empiler un élément dans la pile * * \pre Il y a assez de mémoire pour empiler x * * \post La pile comprend un élément de plus * \post La pile est inchangée sinon * * \exception bad_alloc si pas assez de mémoire * */

dépiler : -p • prototype :

void depiler();/**

* \brief Dépiler la pile * * \pre La pile a au moins un élément * * \post La pile comprend un élément de moins * \post La pile est inchangée sinon * * \exception logic_error si la pile est vide * */


sommet : !p • prototype :

TypeEl sommet();/**

* \brief Consulter le sommet de la pile * * \pre La pile a au moins un élément * * \post La pile est inchangée * \post Une copie de l’élément au sommet est retournée

* * \exception logic_error si la pile est vide * */


pile vide : p = ?• prototype :

bool estVide();/**

* \brief Vérifier si la pile est vide * * \post La pile est inchangée * \post VRAI ou FAUX est retourné selon que la pile est vide ou non * */


appartenance : x p?• prototype :

bool appartient(TypeEl x);/**

* \brief Vérifier si un élément appartient à la pile * * \post La pile est inchangée * \post VRAI ou FAUX est retourné selon que x à la pile ou non *

*/


remplacement : p p - x/y• prototype :

void remplacer(TypeEl x, TypeEl y);

/** * \brief Remplacer un élément dans la pile* * \pre x appartient à la pile**\post Le premier x trouvé (en débutant au sommet) est remplacé par

y*\post La pile est inchangée sinon* *\exception logic_error si pas dans la pile * */


La classe Piletemplate <typename T>class Pile{private:

//...Modèle d’implantationpublic:

// constructeurs et destructeursPile(); //constructeurPile(const Pile&) throw(bad_alloc); //constructeur copie~Pile(); //destructeur

// Modificateursvoid empiler(T) throw (bad_alloc);T depiler()throw(logic_error);

//Sélecteursbool estVide(){ return sommet == 0;}int taille() { return cpt;}T& sommet() throw (logic_error); // élément au sommet

//surcharge d'opérateursPile<T>& operator = (const Pile<T>&) throw

(bad_alloc);friend ostream& operator << (ostream& , const Pile& );

};

Piles : modèles d’implantation

• en tableau : (accès : indice 0)

0 1 2 3 4 ... 99

pile


0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile


• en tableau : (accès par la fin)

0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile



0 1 2 3 4 ... 99

pile


Piles : implantation dans un tableau

Implantation dans un tableau dynamique

{ private :

T* tab; int sommet; int tailleMax;

public: …

Tableau tab réservé dans le tas

Constructeur avec un paramètre : taille maximum

==> bonne implantation si on peut évaluer la taille maximum à l’utilisation de la pile


template <typename T, in MAX = 100 >class Pile {private :

T* tab; int sommet; int tailleMax;

public:Pile(const int max = MAX) throw (bad_alloc);// constructeur : init taille maxi... ~Pile (void); // destructeur

};

Implantation dans un tableau dynamique


template <Typename T>Pile<T> :: Pile (int max) throw (bad_alloc){

tab = new T [max];sommet = -1;maxTaille =max;

}

template <class T>Pile<T> :: ~Pile (void) { if (tab!=0) delete [ ] tab;}

Constructeur

Destructeur


template <typename T>T Pile<T> :: depiler(void) throw (logic_error){

if (!estVide()) return tab[sommet--];else

throw logic_error("Depiler: la pile est vide!");}

template <typename T>bool Pile<T> :: estVide (void){

return (sommet == -1);}

dépiler

Sélecteur : vide

Piles : implantation dans un tableautemplate <typename T>void Pile<T> :: empiler(const T& e) throw (length_error){

if (sommet+1 < maxTaille) { sommet += 1;

tab[sommet] = e; }else{

throw length_error("Empiler:la pile est pleine\n");

}

empiler

Remarque : on suppose que l ’opérateur d ’affectation existe ou est surchargé dans la classe qui correspond au paramètre T.

=> intérêt de la surcharge des opérateurs


Remarque

Il faut cependant noter que la contrainte de pile pleine n’est pas une contrainte liée à la structure de donnée pile. Théoriquement, il n’y a pas de limite sur le nombre d’éléments d’une pile. En pratique, son implantation dans un tableau limite le nombre d’éléments à maxTaille.


template <typename T>Pile<T>& Pile<T> :: operator = (const Pile<T>& p) {

if (tab!=0) delete [ ] tab; //on nettoie thistab=new T [p.maxTaille];

maxTaille=p.maxTaille;for (int i=0; i<maxTaille;i+=1)

tab[i]=p.tab[i];sommet=p.pommet;

return (*this);//retourner : une référence sur l ’objet courant}

Surcharge de l’op. =


template <typename T>Pile<T> :: Pile (const Pile<T>& p) { tab=new X [p.maxtaille];

maxTaille=p.maxTaille;for (int i=0; i<maxTaille;i+=1)

tab[i]=p.tab[i];sommet=p.sommet;

}

Constructeur de copie

• liste chaînée

debut

pile


• liste chaînée : empiler

debut el

suivant

pile



debut el

suivant

el

suivant

pile



debut el

suivant

el

suivant

pile



debut el

suivant

el

suivant

el

suivant

pile



debut el

suivant

el

suivant

el

suivant

pile


• liste chaînée : dépiler

debut el

suivant

el

suivant

el

suivant

pile



debut el

suivant

el

suivant

el

suivant

pile

x



debut el

suivant

el

suivant

pile



debut el

suivant

el

suivant

pile

x



debut el

suivant

pile



debut el

suivant

pile

x



debut

pile


Piles : implantation dans une liste chaînée

template <typename T>class Noeud{public:

Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}//constructeur

~Noeud () {}; //destructeur qui ne fait rien

};

friend class Pile <T>;

private :T el;Noeud<T> * suivant;

Version 1Implantation dans une liste chaînée


template <typename T>class Pile {public: Pile (); // Constructeur Pile (const pile<X>&) throw (bad_alloc); // Constructeur par

copie ~Pile (); // Destructeur

Pile<T>& operator=(const Pile<T>& P); // P1 = Pvoid empiler (const T& a) throw (bad_alloc); T depiler () throw (logic_error);

T& sommet (void) throw (logic_error); // sélecteur : valeur //placée au sommet

bool vide(); //sélecteur : ( IC est vide?)

};

private :Noeud<T>* sommet; // pointeur sur la cellule sommetint cpt; // Nombre d'élements de la pile void detruire (); //Méthode privée utile pour le destructeur

// et l’op. =

Version 1


template <typename T>class Pile {public:

Pile (); Pile (const Pile<T>&) throw (bad_alloc); ~Pile (); Pile<T>& operator=(const Pile<T>& P); //..

private:class Noeud{public: T el;

Noeud * suivant;Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}

};typedef Noeud * elem;elem sommet;int cpt; void detruire ();

};

Version 2


template <typename T>Pile<T>::Pile (void){ sommet =0; cpt = 0;}

template <class X>Pile<X>:: ~Pile(void){ if (sommet != 0) detruire( );}

template <typename T>void Pile<T>::detruire () {

Noeud<T>* p;while (sommet != 0){

p=sommet->suivant;delete sommet;sommet=p;

}}

constructeur

destructeur


template <typename T>void Pile<T>::detruire () {

…delete (sommet);

}

template <typename T>Noeud<T>:: ~Noeud (void){ if (sommet!=0) delete sommet;}

Pour que l ’espace occupé par les composants pointés dans chaque nœud soit libéré lorsque la fonction détruire est appliquée, autre version, il faut un destructeur de noeud qui ait cet effet :

Chaque fois que l’instruction delete est appliquée sur un pointeur de cellule, alors le destructeur de la classe Noeud est activé.

Libère l ’espace occupé par le composant pointé par ptr

Autre version

Les piles

Comparaison des 2 implantations Toutes les implantations des opérations d’une pile utilisant un tableau

ou une liste chaînée prennent un temps constant i.e. en O(1). Par conséquent, d’un point de vue d’efficacité, aucune des deux implantations n’est mieux que l’autre. D’un point de vue de complexité spatiale, le tableau doit déclarer une taille fixe initialement. Une partie de cet espace est perdue quand la pile n’est pas bien remplie. La liste peut augmenter ou rapetisser au besoin mais demande un extra espace pour mémoriser les adresses des pointeurs.

Exemples d’utilisation des piles

Le problème des parenthèses : étant donnée une expression avec desparenthèses, est-elle bien ou mal parenthésée ?

((a + b) c − (d + 4) (5 + (a + c))) (c + (d + (e + 5 g) f) a)(correct)

(a + b)((incorrect)

Encore un peu plus complexe : différentes parenthèses. Exemple avec [ et (([])[()(()[])] : correct([)] : incorrect

Vérification de parenthèsage

Tant que lire caractère cSi c est ( ou [

empiler cSinon

Si c est ) ou ]Si pile vide

ÉCHECSinon

c′ = lire la pileSi c et c′ correspondent

dépilerSinon

ÉCHECSi pile vide

OKSinon

ÉCHEC

Code C++

bool check(string s) {Pile p;for (unsigned int i(0); i < s.size(); ++i) {

if ((s[i] == ’(’) || (s[i] == ’[’))p.empile(s[i]);else if (s[i] == ’)’) {

if ((!p.est_vide()) && (p.top() == ’(’))p.depile();

elsereturn false;

} else if (s[i] == ’]’) {if ((!p.est_vide()) && (p.top() == ’[’))

p.depile();else

return false;}

}return p.est_vide();}

Exemples d’application des piles

Reconnaissance syntaxique : Soit une chaîne de caractères définie par

la règle suivante : Une chaîne quelconque S suivie du caractère *, suivi de la chaîne S inversée.

Exemple abc*cba La chaîne peut contenir n’importe quel caractère alphanumérique. La

chaîne se termine par le marqueur fin de ligne.

Conception : Pour déterminer si la chaîne est légale, il faut :1) Lire jusqu’à ‘*’ les caractère un à un en les empilant dans une pile.2) Après ‘*’, jusqu’à la fin de la chaîne, lire un caractère, dépiler le

caractère au sommet de la pile et comparer les deux, s’il ne sont pas égaux, la chaîne est invalide.

3) Si tous les caractères sont égaux et que la pile s’est vidée, la chaîne est valide.


Calcul arithmétique : Une application courante des piles se fait dans le

calcul arithmétique: l'ordre dans la pile permet d'éviter l'usage des parenthèses. La notation postfixée (polonaise) consiste à placer les opérandes devant l'opérateur. La notation infixée (parenthèsée) consiste à entourer les opérateurs par leurs opérandes. Les parenthèses sont nécessaires uniquement en notation infixée. Certaines règles permettent d'en réduire le nombre (priorité de la multiplication par rapport à l'addition, en cas d'opérations unaires représentées par un caractère spécial (-, !,...). Les notations préfixée et postfixée sont d'un emploi plus facile puisqu'on sait immédiatement combien d'opérandes il faut rechercher.


Calcul arithmétique : Détaillons ici la saisie et l'évaluation d'une

expression

Postfixée. La notation usuelle, comme (3 + 5) * 2, est dite infixée. Son défaut est de nécessiter l'utilisation de parenthèses pour éviter toute ambiguïté (ici, avec 3 + (5 * 2)). Pour éviter le parenthésage, il est possible de transformer une expression infixée en une expression postfixée en faisant "glisser« les opérateurs arithmétiques à la suite des expressions auxquelles ils s'appliquent.

Exemple

(3 + 5) * 2 s'écrira en notation postfixée (notation polonaise): 3 5 + 2 *alors que 3 + (5 * 2) s'écrira: 3 5 2 * +

Calcul arithmétique: On voit que la multiplication vient immédiatement

après ses deux opérandes A et B. Imaginons maintenant que A * B est calculé et stocké dans T. Alors la division / vient juste après les deux arguments T et C.

Forme infixe: A/B ** C + D * E - A * CForme postfixe: ABC ** /DE * + AC * -


Evaluation en Postfixe

Considérons l’expression en postfixe suivante: 6 5 2 3 + 8 * + 3 + *

AlgorithmeInitialiser la pile à vide;while (ce n’st pas la fin del’expression postfixée) {

prendre l’item prochain de postfixe;if(item est une valeur)empiler;else if(item operateur binaire ) {

dépiler dans x;dépiler dans y;effectuer y operateur x;empiler le résultat obtenu;

} else if (item opérateur unaire) {dépiler dans x;effectuer opérateur(x);empiler le résultat obtenu;}

}

la seule valeur qui reste dans la pile est le résultat recherché.

Opérateur binaires: +, -, *, /, etc.,

Opérateur unaires: moins unaire, racine carrée, sin, cos, exp, … etc.



Infixe à Postfixe

Algorithmeinitialise la pile et l’output postfixe à vide;while(ce n’est pas la fin de l’expression infixe) {

prendre le prochain item infixeif (item est une valeur) concaténer item à postfixeelse if (item == ‘(‘) empiler itemelse if (item == ‘)’) {

dépiler sur xwhile(x != ‘(‘)concaténer x à postfixe & dépiler sur x

}else {while(precedence(stack top) >= precedence(item))dépiler sur x et concaténer x à postfixe;empiler item;}

}while (pile non vide)dépiler sur x et concaténer x à postfixe;

Bien entendu la notation postfixe ne sera pas d’une grande utilité s’il n’existait pas unalgorithme simple pour convertir une expressioninfixe en une expression postfixe.

Encore une fois, cet algorithme utilise une pile.


Infixe à Postfixe

Algorithmeinitialise la pile et l’output postfixe à vide;while(ce n’est pas la fin de l’expression infixe) {

prendre le prochain item infixeif (item est une valeur) concaténer item à postfixeelse if (item == ‘(‘) empiler itemelse if (item == ‘)’) {

dépiler sur xwhile(x != ‘(‘)concaténer x à postfixe & dépiler sur x

}else {while(precedence(stack top) >= precedence(item))dépiler sur x et concaténer x à postfixe;empiler item;}

}while (pile non vide)dépiler sur x et concaténer x à postfixe;

Précédence des opérateurs4 : ‘(‘ – déplée seulement si une ‘)’ est trouvée3 : tous les opérateurs unaires2 : / *1 : + -

L’algorithme passe les opérandes à la forme postfixe, mais sauvegarde les opérateurs dans la pile jusqu’à ce que tous les opérandes soient tous traduits.

Documents

Structures de données IFT-10541 Abder Alikacem Les piles Département dinformatique et de génie logiciel Édition Septembre 2009