les piles
Bien, voyons en détail les piles !
Voici tout d'abord les opérations possibles sur les piles :
déterminer la taille de la pile ;
déterminer si la pile est vide ou non ;
ajouter une nouvelle donnée ;
consulter la dernière donnée empilée ;
supprimer la dernière donnée ajoutée.
Bien, ça, c'est la version en français, passons à la version C++ !
Pour pouvoir utiliser les piles, il faut inclure l'en-tête stack.
Le début du code est donc :
1
2
#include <stack>
using namespace std;
Maintenant, pour pouvoir travailler avec une pile, il faut l'initialiser :
1
2
3
stack<int> i; //pile d'entiers
stack<string> s; //pile de chaînes de caractères
stack<T> p; //remplacer le T par le type voulu
Entre les chevrons (< >;), il faut mettre le type de pile voulu. Si l'on désire une pile d'entiers, on met int ; pour une pile de chaînes, on met string, ...
Voyons maintenant les différentes manipulations des piles.
La hauteur de la pile
Pour pouvoir boucler sur une pile, il faut connaître sa hauteur (ou sa taille). On utilise la fonction nomPile.size() qui renvoie le nombre d'éléments de la pile.
1
2
stack<int> i;
cout << "Le nombre d'éléments de la pile est : " << i.size() << endl;
Ce code affichera :
Le nombre d'éléments de la pile est : 0
La taille est zéro car lorsqu'une pile est initialisée, elle est initialisée en tant que pile vide, donc elle ne contient aucun élément.
L'état de la pile
Si on ne veut pas connaître le nombre d'éléments présents dans la pile, mais juste savoir si elle est vide ou non, on utilise la fonction nomPile.empty() qui renvoie un booléen qui vaut true si la pile est vide et false sinon.
1
2
3
4
5
6
stack<int> i;
cout << "Etat de la pile : ";
if(i.empty())
cout << "vide" << endl;
else
cout << "pas vide" << endl;
Ajouter (empiler) un élément dans la pile
Pour empiler un élément, on utilise la fonction nomPile.push(elt) qui prend en paramètre l'élément à empiler.
L'élément à empiler doit être du même type que la pile !
On ne donne pas le type de l'élément à empiler : par exemple, si nomPile est une pile d'entiers, on ne fait pas nomPile.push(int elt).
1
2
3
4
5
6
stack<int> i; //pile d'entiers
int elt = 12;
i.push(2); //je rajoute 2
i.push(elt); //je rajoute le contenu de la variable elt, soit 12
i.push("Chaîne"); //erreur à la compilation car i est une pile de type entier et non chaîne
Accéder au dernier élément de la pile
Maintenant, si on veut accéder aux éléments de la pile, il faut obligatoirement prendre le dernier empilé, donc celui qui se trouve au sommet. Pour récupérer cet élément, on utilise la fonction nomPile.top().
Pour utiliser cette fonction, la pile ne doit pas être vide !
1
2
3
4
5
stack<int> i;
i.push(2);
i.push(12);
cout << "Le premier élément est : " << i.top();
Comme vous le voyez, il est impossible d'afficher le second élément. Il faut donc supprimer le premier.
Supprimer (dépiler) le dernier élément de la pile
Pour le supprimer, on utilise la fonction nomPile.pop().
Pour utiliser pop, la pile ne doit pas être vide !
Une fois l'élément dépilé, si on ne l'a pas sauvegardé, il est définitivement perdu !
1
2
3
4
5
6
7
8
9
10
stack<int> i;
i.push(2);
i.push(3);
cout << "Le premier élément est : " << i.top() << endl; // accès au dernier élément
i.pop(); // suppression du dernier élément
cout << "Le deuxième élément est : " << i.top() << endl; // accès au deuxième élément
i.pop(); // suppression du dernier élément ; maintenant la pile est vide !
cout << "Nombre d'éléments dans la pile : " << i.size() << endl;
Passage de paramètres
Implicitement, le passage de paramètres se fait par valeurs. Une pile passée en paramètre d'un sous-programme est donc recopiée. Pour des raisons de performances, une pile en entrée d'une procédure ou d'une fonction est passée par référence en ajoutant un "et commercial" (&) avant le nom du paramètre (exemple : stack<int>& p).
Maintenant, vous savez tout sur les piles :D !
Je vais maintenant vous donner deux exemples sur le fonctionnement de la pile en utilisant toutes les fonctions que l'on a vues.
Le premier est une procédure de remplissage et d'affichage d'une pile.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <stack>
using namespace std;
/* Procédure qui remplit la pile passée en paramètre. La pile est passée par référence, ce qui veut dire que quand on ajoute un élément, on agit directement sur la "vraie" pile déclarée dans le main */
void remplir(stack<int>& p)
{
int n;
cout << "Entrez le nombre d'éléments de la pile : ";
cin >> n;
int elt;
for(int i = 0; i < n; i++)
{
cout << "Entrez un élément : ";
cin >> elt;
p.push(elt);
}
}
/* Procédure qui affiche la pile donnée en paramètre. La pile est passée par référence et déclarée const pour être sûr de ne pas la modifier, car on travaille sur la "vraie" pile (elle n'est pas recopiée en mémoire) */
void afficher(const stack<int>& p)
{
stack<int> t = p;
while(!t.empty())
{
cout << t.top();
t.pop();
if(!t.empty())
cout << " , ";
}
}
int main()
{
stack<int> p;
remplir(p);
cout << "Votre pile est : ";
afficher(p);
return 0;
}
Le deuxième exemple est un programme qui montre l'évolution de la pile.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <stack>
using namespace std;
void afficher(const stack<int>& p)
{
stack<int> t = p;
while(!t.empty())
{
cout << t.top();
t.pop();
if(!t.empty())
cout << " , ";
}
}
int main()
{
stack<int> p;
cout << "Apres declaration p = ";
afficher(p);
cout << "p.size() = " << p.size() << endl;
cout << "p.empty() = " << boolalpha << p.empty() << endl; /* boolalpha permet d'afficher true ou false pour la valeur d'un booléen (à la place de 1 ou 0) */
p.push(10);
p.push(20);
p.push(30);
cout << endl << "Apres empilement de 10, 20 et 30 p = ";
afficher(p);
cout << "p.size() = " << p.size() << endl;
cout << "p.empty() = " << boolalpha << p.empty() << endl;
cout << "p.top() = " << p.top() << endl;
p.pop();
cout << endl << "Apres p.pop(), p = ";
afficher(p);
cout << "p.size() = " << p.size() << endl;
cout << "p.empty() = " << boolalpha << p.empty() << endl;
cout << "p.top() = " << p.top() << endl;
p.pop();
cout << endl << "Apres p.pop(), p = ";
afficher(p);
cout << "p.size() = " << p.size() << endl;
cout << "p.empty() = " << boolalpha << p.empty() << endl;
cout << "p.top() = " << p.top() << endl;
p.pop();
cout << endl << "Apres p.pop(), p = ";
afficher(p);
cout << "p.size() = " << p.size() << endl;
cout << "p.empty() = " << boolalpha << p.empty() << endl;
return 0;
}
Voilà, la partie sur les piles est terminée. Passons maintenant aux files
fin.
ليست هناك تعليقات:
إرسال تعليق