Les piles et les files en C++
Formation
En Semi-présenciel Paris
Avez-vous besoin d'un coach de formation?
Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.
Description
-
Typologie
Formation
-
Méthodologie
En semi-présentiel
-
Lieu
Paris
Grâce à cette formation vous pourrez acquérir les connaissances nécessaires qui vous permettrons d’ajouter des compétences à votre profil et obtenir de solides aptitude qui vous offriront de nombreuses opportunités professionnelles.
Les sites et dates disponibles
Lieu
Date de début
Date de début
Les Avis
Les matières
- C++
Le programme
Bonjour à tous !
Dans ce tutoriel, vous allez apprendre à vous servir des piles ainsi que des files en C++.
Avant de vous lancer dans la lecture, vous pouvez lire le tutoriel d'Octal sur les piles et les files en C, pour voir le principe. L'avantage en C++, c'est que l'implémentation et l'utilisation ont été considérablement simplifiées ! :-°
Il faut avoir lu au préalable le tutoriel de M@teo21 sur le C et C++ !
PrincipeAvant de commencer à coder, voyons le principe de ces structures de données.
Les pilesTous les jours, on manipule des piles (et pas seulement dans la télécommande :D !).
Prenons un exemple : une pile d'assiettes à laver. On les met les unes sur les autres et pour les laver, on prend celle du dessus. Un deuxième exemple : une pile de dossiers sur un bureau. On les met les uns au-dessus des autres et on retire le premier, donc le dernier arrivé. Les piles répondent à ce principe : dernier arrivé, premier servi, aussi connues sous le nom de LIFO pour Last In, First Out.
Pour les files, c'est exactement le contraire ! Un exemple tout simple : une file d'attente. Le premier arrivé est le premier à sortir (à être servi), aussi connues sous le nom de FIFO pour First In, First Out.
La STLSTL pour Standard Template Library. Les deux structures de données de ce tuto en font partie. Pour résumer, la STL est un ensemble de structures pouvant contenir n'importe quel type de données. Cela veut donc dire que, dans les piles et les files, on peut stocker tout type de données (entiers, réels, chaînes de caractères, ...) mais un seul type par structure : si je déclare une pile d'entiers, je ne pourrais pas empiler des chaînes de caractères !
Les pilesBien, 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 :
Maintenant, pour pouvoir travailler avec une pile, il faut l'initialiser :
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 vouluEntre 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.
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.
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 : 0La 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 pileSi 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.
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 pilePour 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).
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 !
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 pilePour 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 !
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.
Le deuxième exemple est un programme qui montre l'évolution de la pile.
#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 :D .
Les filesBien, les files maintenant !
Les opérations possibles sur les files sont :
déterminer la taille de la file ;
déterminer si la file est vide ou non ;
ajouter une nouvelle donnée ;
consulter la première donnée ;
consulter la dernière donnée ;
supprimer la première donnée.
Voyons comment implémenter cela en C++.
Plusieurs de ces fonctions ont un fonctionnement identique à celles des piles, je les passerai donc plus rapidement.
Pour pouvoir utiliser les files, il faut inclure l'en-tête queue.
Le début du code est donc :
Pour initialiser une file, il faut la déclarer comme ceci :
queue<int> f; // file d'entiers queue<T> g; //remplacer T par le type vouluVoyons maintenant les différentes fonctions.
Pour les quatre fonctions qui vont suivre, je vais juste les citer pour la bonne et simple raison que j'ai déjà expliqué leur fonctionnement dans la partie sur les piles.
La taille de la fileOn utilise la fonction nomFile.size().
L'état de la fileOn utilise la fonction nomFile.empty().
Rappel : cette fonction renvoie un booléen.
On utilise la fonction nomFile.push(elt).
Supprimer la première donnéeOn utilise la fonction nomFile.pop().
Pour utiliser cette fonction, la file ne doit pas être vide !
Accéder au premier et au dernier élémentPour utiliser ces fonctions, la file ne doit pas être vide !
Pour accéder au premier élément ajouté dans la pile (donc le premier à sortir), on utilise la fonction nomFile.front().
Pour accéder au dernier élément ajouté dans la liste, on utilise la fonction nomFile.back().
Voici un exemple d'utilisation :
queue<int> i; i.push(10); i.push(20); i.push(30); i.push(40); cout << "Le premier élément est : " << i.front() << endl; cout << "Le dernier élément est : " << i.back() << endl; i.pop(); cout << "Le premier élément est : " << i.front() << endl; cout << "Le dernier élément est : " << i.back() << endl;Le résultat est :
Le premier élément est : 10 Le dernier élément est : 40 Le premier élément est : 20 Le dernier élément est : 40Pour mieux comprendre, on peut dessiner la file :
Comme pour les piles, le passage de paramètres se fait de préférence par référence.
Je termine cette partie sur les files avec deux exemples.
Le premier est une procédure d'affichage d'une file.
/* Procédure qui affiche la file donnée en paramètre. La file 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" file (elle n'est pas recopiée en mémoire) */ #include <iostream> #include <queue> using namespace std; void afficher(const queue<int>& f) { queue<int> q = f; while(!q.empty()) { cout << q.front(); q.pop(); if(!q.empty()) cout << " , "; } }Le deuxième exemple utilise toutes les fonctions sur les files.
#include <queue> #include <iostream> using namespace std; void afficher(const queue<int>& f) { ...Avez-vous besoin d'un coach de formation?
Il vous aidera à comparer différents cours et à trouver la solution la plus abordable.
Les piles et les files en C++