Empilez dans C++ STL avec exemple

Qu'est-ce que std::stack ?

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

La classe `std::stack` est un adaptateur de conteneur. Les objets conteneurs contiennent des données de même type. Vous pouvez créer une pile à partir de différents 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.

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;

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

Types de membres

Voici les types de membres de la pile :

• type_valeur– Le premier paramètre de modèle, T. Il désigne les types d'éléments.
• type_de_conteneur– Le deuxième paramètre du modèle, Container, désigne le type de conteneur sous-jacent.
• type_taille– Type entier non signé.

Operation dans la pile

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

• pousser – Il ajoute/pousse un élément dans la pile.
• pop – Elle retire/dépile un élément de la pile.
• coup d'oeil – Renvoie l'élément du dessus de la pile sans le supprimer.
• estple – Vérifie si une pile est pleine.
• est vide – Vérifie si une pile est vide.

Implémentation de la pile

Les étapes suivantes montrent comment le haut de la pile se déplace lorsque des éléments sont ajoutés puis retirés :

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

Étape 2) Ensuite, nous avons empilé l'élément 5. Le sommet de la pile pointe désormais vers l'élément 5.

Étape 3) Ensuite, nous avons empilé l'élément 50. Le sommet de la pile se déplace et pointe vers l'élément 50.

Étape 4) Nous avons ensuite effectué une opération de dépilement, retirant ainsi l'élément du sommet de la pile. L'élément 50 a été dépilé. Le sommet de la pile pointe désormais vers l'élément 5.

push() et pop()

La fonction stack::push() ajoute un nouvel élément au sommet de la pile. La taille de la pile est incrémentée de 1 après l'insertion. La fonction accepte la syntaxe suivante :

stack.push(value)

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

La fonction `stack::pop()` supprime l'élément du sommet de la pile, c'est-à-dire l'élément le plus récent. La taille de la pile est réduite de 1 après cette 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 :

Code Explication:

1. Incluez le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Incluez 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 des 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 désormais 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 désormais 20.
12. Utilisez une boucle while et une fonction vide() pour vérifier si la pile n'est PAS vide. Le ! est l'opérateur NOT.
13. Impression du 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 inclus:

• vide()– vérifie si une pile est vide ou non.
• Taille()– renvoie la taille de la pile, c'est-à-dire le nombre d'éléments dans la pile.
• Haut()– accède à l'élément de pile situé 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 :

Code Explication:

1. Incluez le fichier d'en-tête iostream dans notre code afin d'utiliser ses fonctions.
2. Incluez le fichier d'en-tête de pile dans notre code afin d'utiliser ses fonctions.
3. Incluez 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éez 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'un autre texte.
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 ensuite 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 de la valeur une fois terminé.
30. Fin du corps de la fonction main().

emplace() 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.
• échanger()– échange le contenu d'une 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 :

Code Explication:

1. Incluez le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Incluez 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. La fin est un C++ mot-clé pour la ligne de fin. Il déplace le curseur de la souris vers 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().

Pile en STL

La STL (Standard Template Library) est livrée avec des classes de modèles qui fournissent des C++ structures de données. 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 4:

#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 :

Code Explication:

1. Incluez le fichier d'en-tête iostream dans notre code pour utiliser ses fonctions.
2. Incluez 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().

FAQ