Pile en C++ STL avec exemple

Qu'est-ce que std::stack ?

Une pile est une structure de données qui fonctionne selon la technique LIFO (Last In First Out). Le std ::stack permet d'ajouter et de supprimer des éléments à partir d'une seule extrémité.

La classe std::stack est un adaptateur de conteneur. Les objets conteneurs contiennent des données d'un type de données similaire. Vous pouvez créer une pile à partir de divers conteneurs de séquence. Si aucun conteneur n'est fourni, le conteneur deque sera utilisé par défaut. Les adaptateurs de conteneur ne prennent pas en charge les itérateurs, ils ne peuvent donc pas être utilisés pour manipuler des données.

Dans ce tutoriel C++, vous apprendrez

• Qu'est-ce que std::stack ?
• Syntaxe de la pile
• Types de membres
• Opérations dans la pile
• Mise en œuvre de la pile
• pousser() et pop()
• vide(), taille(), haut()
• place() et swap()
• Empiler en STL

Syntaxe de la pile

Pour créer une pile, nous devons inclure le fichier d'en-tête dans notre code. Nous utilisons ensuite cette syntaxe pour définir le std::stack :

template <class Type, class Container = deque<Type> > class stack;

• Tapez – est le Type d'élément contenu dans std::stack. Il peut s'agir de n'importe quel type C++ valide ou même d'un type défini par l'utilisateur.
• Conteneur – est le Type d'objet conteneur sous-jacent.

Types de membres

Voici les types de membres de la pile :

• value_type - Le premier paramètre de modèle, T. Il désigne les types d'éléments.
• container_type - Le deuxième paramètre de modèle, Container. Il indique le type de conteneur sous-jacent.
• size_type- Type intégral non signé.

Opérations dans la pile

Une pile C++ prend en charge les opérations de base suivantes :

• push – Il ajoute/pousse un élément dans la pile.
• pop - Il supprime/éjecte un élément de la pile.
• peek – Renvoie l'élément du haut de la pile sans le supprimer.
• isFull – Vérifie si une pile est pleine.
• isEmpty – Vérifie si une pile est vide.

Mise en œuvre de la pile

Étape 1) Nous avons initialement une pile vide. Le sommet d'une pile vide est défini sur -1.

Étape 2) Ensuite, nous avons poussé l'élément 5 dans la pile. Le haut de la pile pointe vers l'élément 5.

Étape 3) Ensuite, nous avons poussé l'élément 50 dans la pile. Le haut de la pile se décale et pointe vers l'élément 50.

Étape 4) Nous avons ensuite effectué une opération pop, supprimant l'élément supérieur de la pile. L'élément 50 est extrait de la pile. Le haut de la pile pointe maintenant vers l'élément 5.

pousser() et pop()

Les fonctions stack::push() ajoutent un nouvel élément au sommet de la pile. La taille de la pile est augmentée de 1 après l'insertion. La fonction prend cette syntaxe :

stack.push(value)

La valeur est l'élément à insérer dans la pile.

La fonction stack::pop() supprime l'élément supérieur de la pile. C'est l'élément le plus récent de la pile. La taille de la pile est réduite de 1 après la suppression. Voici la syntaxe de la fonction :

stack.pop()

La fonction ne prend aucun paramètre.

Exemple 1 :

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> st;
	st.push(10);
	st.push(20);
	st.push(30);
	st.push(40);
	
         st.pop();
	st.pop();

	while (!st.empty()) {
		cout << ' ' << st.top();
		st.pop();
	}
}

Sortie :

Voici une capture d'écran du code :

Explication du code :

1. Inclure le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Inclure le fichier d'en-tête de pile dans notre code pour utiliser ses fonctions.
3. Incluez l'espace de noms std dans notre code pour utiliser ses classes sans l'appeler.
4. Appelez la fonction main(). La logique du programme doit être ajoutée dans cette fonction.
5. Créez une pile st pour stocker les valeurs entières.
6. Utilisez la fonction push() pour insérer la valeur 10 dans la pile.
7. Utilisez la fonction push() pour insérer la valeur 20 dans la pile.
8. Utilisez la fonction push() pour insérer la valeur 30 dans la pile.
9. Utilisez la fonction push() pour insérer la valeur 40 dans la pile.
10. Utilisez la fonction pop() pour supprimer l'élément supérieur de la pile, c'est-à-dire 40. L'élément supérieur devient maintenant 30.
11. Utilisez la fonction pop() pour supprimer l'élément supérieur de la pile, c'est-à-dire 30. L'élément supérieur devient maintenant 20.
12. Utilisez une boucle while et la fonction empty() pour vérifier si la pile n'est PAS vide. La ! est l'opérateur NOT.
13. Imprimer le contenu actuel de la pile sur la console.
14. Appelez la fonction pop() sur la pile.
15. Fin du corps de la boucle while.
16. Fin du corps de la fonction main().

vide(), taille(), haut()

Les piles ont des fonctions intégrées que vous pouvez utiliser pour jouer avec la pile et ses valeurs. Ceux-ci incluent :

• empty()- vérifie si une pile est vide ou non.
• size()- renvoie la taille de la pile, c'est-à-dire le nombre d'éléments dans une pile.
• top() - accède à l'élément de pile en haut.

Exemple 2 :

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> st;
	st.push(32);
	st.push(21);
	st.push(39);
	st.push(89);
	st.push(25);

	cout << "The stack st is: ";
	createStack(st);
	cout << "\n st.size() : " << st.size();
	cout << "\n st.top() : " << st.top();
	cout << "\n st.pop() : ";
	st.pop();
	createStack(st);
	return 0;
}

Sortie :

Voici une capture d'écran du code :

Explication du code :

1. Inclure le fichier d'en-tête iostream dans notre code afin d'utiliser ses fonctions.
2. Inclure le fichier d'en-tête de pile dans notre code afin d'utiliser ses fonctions.
3. Inclure l'espace de noms std dans notre programme afin d'utiliser ses classes sans l'appeler.
4. Créez la fonction createStack que nous pouvons utiliser pour créer la pile mystack. La pile contiendra un ensemble d'entiers.
5. Le début du corps de la fonction createStack.
6. Créez une instance du type de données mystack et donnez-lui le nom ms.
7. Utilisez la boucle while et la fonction empty() pour vérifier si la pile est vide.
8. Le début du corps de la boucle while.
9. Utilisez la fonction top() stockée en haut de la pile. Le caractère \t créera un nouvel onglet.
10. Utilisez la fonction pop() pour supprimer l'élément en haut de la pile.
11. Fin du corps de la boucle while.
12. Imprimez une ligne vierge sur la console.
13. Fin du corps de la fonction createStack.
14. Appelez la fonction main(). La logique du programme doit être ajoutée dans le corps de la fonction main().
15. Le début du corps de la fonction main().
16. Créer un objet de pile st.
17. Utilisez la fonction push() pour insérer l'élément 32 dans la pile.
18. Utilisez la fonction push() pour insérer l'élément 21 dans la pile.
19. Utilisez la fonction push() pour insérer l'élément 39 dans la pile.
20. Utilisez la fonction push() pour insérer l'élément 89 dans la pile.
21. Utilisez la fonction push() pour insérer l'élément 25 dans la pile.
22. Imprimez du texte sur la console.
23. Appelez la fonction createStack pour exécuter les opérations d'insertion ci-dessus dans la pile.
24. Imprimez la taille de la pile sur la console à côté d'autres textes.
25. Imprimez l'élément en haut de la pile sur la console.
26. Imprimez du texte sur la console.
27. Supprimez l'élément en haut de la pile. Il renverra alors les éléments restant dans la pile.
28. Appelez la fonction createStack pour exécuter les opérations ci-dessus.
29. Le programme doit renvoyer une valeur en cas de réussite.
30. Fin du corps de la fonction main().

place() et swap()

Voici d'autres fonctions de pile intégrées :

• emplace() - construit puis insère un nouvel élément en haut de la pile.
• swap()- échange le contenu de la pile avec le contenu d'une autre pile.

Exemple 3 :

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> st2;

	st1.emplace(12);
	st1.emplace(19);

	st2.emplace(20);
	st2.emplace(23);

	st1.swap(st2);

	cout << "st1 = ";
	while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}

	cout << endl << "st2 = ";
	while (!st2.empty()) {
		cout << st2.top() << " ";
		st2.pop();
	}
}

Sortie :

Voici une capture d'écran du code :

Explication du code :

1. Inclure le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Inclure le fichier d'en-tête de pile dans notre code pour utiliser ses fonctions.
3. Incluez le fichier d'en-tête cstdlib dans notre code pour utiliser ses fonctions.
4. Incluez l'espace de noms std dans notre code pour utiliser ses classes sans l'appeler.
5. Appelez la fonction main(). La logique du programme sera ajoutée dans le corps de cette fonction.
6. Déclarez une pile nommée st1 pour stocker des valeurs entières.
7. Déclarez une pile nommée st2 pour stocker des valeurs entières.
8. Utilisez la fonction emplace() pour insérer l'entier 12 dans la pile nommée st1.
9. Utilisez la fonction emplace() pour insérer l'entier 19 dans la pile nommée st1.
10. Utilisez la fonction emplace() pour insérer l'entier 20 dans la pile nommée st2.
11. Utilisez la fonction emplace() pour insérer l'entier 23 dans la pile nommée st2.
12. Utilisez la fonction swap() pour échanger le contenu des deux piles, st1 et st2. Le contenu de la pile st1 doit être déplacé vers la pile st2. Le contenu de la pile st2 doit être déplacé vers la pile st1.
13. Imprimez du texte sur la console.
14. Utilisez l'instruction while et la fonction empty() pour vérifier si la pile st1 n'est pas vide.
15. Imprimez le contenu de la pile st1 sur la console. Le " " ajoute de l'espace entre les éléments de la pile lors de leur impression sur la console.
16. Exécutez la fonction pop() sur la pile st1 pour supprimer l'élément supérieur.
17. Fin du corps de l'instruction while.
18. Imprimez du texte sur la console. Le endl est un mot-clé C++ pour la ligne de fin. Il déplace le curseur de la souris sur la ligne suivante pour commencer l'impression à partir de là.
19. Utilisez l'instruction while et la fonction empty() pour vérifier si la pile st2 n'est pas vide.
20. Imprimez le contenu de la pile st2 sur la console. Le " " ajoute de l'espace entre les éléments de la pile lors de leur impression sur la console.
21. Exécutez la fonction pop() sur la pile st2 pour supprimer l'élément supérieur.
22. Fin du corps de l'instruction while.
23. Fin du corps de la fonction main().

Empiler en STL

La STL (Standard Template Library) est fournie avec des classes de modèles qui fournissent des structures de données C++ communes. Par conséquent, une pile peut également être implémentée en STL. Nous incluons simplement cette bibliothèque dans notre code et l'utilisons pour définir une pile.

stack<T> st; 

La syntaxe ci-dessus déclare une pile st aux éléments de type de données T.

Exemple 3 :

#include <iostream>      
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st;
	st.push(12);
	st.push(19);
	st.push(20);
	cout << st.top();   
	cout << st.size();  
}

Sortie :

Voici une capture d'écran du code :

Explication du code :

1. Inclure le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Inclure le fichier d'en-tête de pile dans notre code pour utiliser ses fonctions.
3. Incluez le fichier d'en-tête cstdlib dans notre code pour utiliser ses fonctions.
4. Incluez l'espace de noms std dans notre code pour utiliser ses classes sans l'appeler.
5. Appelez la fonction main(). La logique du programme doit être ajoutée dans le corps de cette fonction.
6. Déclarez une pile st pour stocker des données entières.
7. Ajoutez l'élément 12 à la pile.
8. Ajoutez l'élément 19 à la pile.
9. Ajoutez l'élément 20 à la pile.
10. Imprimez l'élément en haut de la pile sur la console.
11. Imprimez la taille de la pile sur la console.
12. Fin du corps de la fonction main().

Résumé :

• Une pile est une structure de données qui fonctionne selon la technique LIFO (Last In first Out).
• Le std::stack ne permet d'ajouter et de supprimer des éléments qu'à une extrémité.
• La classe std::stack est un adaptateur de conteneur, contenant des éléments d'un type de données similaire.
• Une pile peut être créée à partir de divers conteneurs de séquence.
• Si vous ne fournissez pas de conteneur, le conteneur deque sera utilisé par défaut.
• La fonction push() sert à insérer des éléments dans la pile.
• La fonction pop() sert à supprimer l'élément supérieur de l'étape.
• La fonction empty() sert à vérifier si une pile est vide ou non.