Empiler en 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 d’un type de données similaire. Vous pouvez créer une pile à partir de différents conteneurs de séquences. Si aucun conteneur n'est fourni, le deque containe sera utilisé par défaut. Les adaptateurs de conteneur ne prennent pas en charge les itérateurs et 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. Il peut s'agir de n'importe quel type C++ valide ou même d'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 :

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

Opérations dans la pile

A C + + la pile prend en charge le suiviwing opérations de base:

  • push – Il ajoute/pousse un élément dans la pile.
  • pop – Il supprime/fait apparaître un élément de la pile.
  • peek – Renvoie l’élément supérieur de la pile sans le supprimer.
  • isFull – Vérifie si une pile est pleine.
  • isEmpty – Vérifie si une pile est vide.

Implémentation de la pile

Implémentation de la pile

Étape 1) Nous avons initialement une pile vide. Le haut 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éplace 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 désormais vers l'élément 5.

push() et pop()

Les fonctions stack::push() ajoutent un nouvel élément en haut 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. Il s'agit de 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.

1 Exemple:

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

push() et pop()

Voici une capture d'écran du code :

push() et pop()

Explication du code :

  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.
  • 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.

2 Exemple:

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

vide(),taille(),haut()

Voici une capture d'écran du code :

vide(),taille(),haut()

Explication du code :

  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.
  • swap()- échange le contenu de la pile avec le contenu d'une autre pile.

3 Exemple:

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

remplacer()& swap()

Voici une capture d'écran du code :

remplacer()& swap()

Explication du code :

  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. Le endl est un mot-clé C++ 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 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 declares une pile st aux éléments de type de données T.

4 Exemple:

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

Pile en STL

Voici une capture d'écran du code :

Pile en STL

Explication du code :

  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().

Résumé

  • 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 uniquement d'ajouter et de supprimer des éléments à 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 différents conteneurs de séquences.
  • 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() permet de supprimer l'élément supérieur de l'étape.
  • La fonction empty() permet de vérifier si une pile est vide ou non.