La structure Pile (Stack)
Une pile est un conteneur linéaire dans lequel tous les ajouts et suppressions sont limités à une seule extrémité appelée tête de pile. Si on insère les éléments {5, 10, 8, 20}, ils seront supprimés dans l'ordre inverse {20, 8, 10, 5}.
Principe LIFO Une pile est une structure LIFO (Last In, First Out — dernier entré, premier sorti). Le dernier élément inséré est le premier à être retiré, comme une pile de livres ou de disques dans la vie courante.
Opérations de base
| Opération | Description |
|---|---|
empiler(valeur) | Insère un élément en tête de pile |
depiler() | Supprime l'élément en tête de pile |
premier() | Accède à l'élément en tête sans le supprimer |
Implémentation : tableau vs liste chaînée L'implémentation par tableau est plus simple, mais impose une taille fixe à la compilation. L'implémentation par liste chaînée permet à la pile de grandir et rétrécir dynamiquement : les nœuds sont alloués dans le tas, l'objet pile dans la pile mémoire.
Implémentation directe (sans réutilisation de Liste)
Déclaration — pile.h
#ifndef PILE_H
#define PILE_H
#include <iostream>
#include <cassert>
using namespace std;
template <typename T>
struct Noeud {
T donnees;
Noeud<T>* suivant;
};
template <typename T>
class Pile {
private:
Noeud<T>* entete;
int compteur;
Noeud<T>* CreerNoeud(const T& valeur);
public:
Pile();
~Pile();
void empiler(const T& valeur);
void depiler();
T& premier() const;
void afficher() const;
int taille() const;
};
#endifEmpiler un élément
L'insertion se fait toujours en tête — deux opérations suffisent après la création du nœud.
template <typename T>
void Pile<T>::empiler(const T& valeur) {
Noeud<T>* nouveau = CreerNoeud(valeur);
nouveau->suivant = entete;
entete = nouveau;
compteur++;
}Dépiler l'élément en tête
La suppression du premier nœud libère sa mémoire et avance l'entête.
template <typename T>
void Pile<T>::depiler() {
if (compteur == 0) {
cout << "Erreur! La pile est vide." << endl;
return;
}
Noeud<T>* del = entete;
entete = entete->suivant;
delete del;
compteur--;
}Retourner le premier élément
template <typename T>
T& Pile<T>::premier() const {
if (compteur == 0) {
cout << "Erreur! La pile est vide";
assert(false);
}
return entete->donnees;
}Fichiers complets — implémentation directe
#ifndef PILE_H
#define PILE_H
#include <iostream>
#include <cassert>
using namespace std;
template <typename T>
struct Noeud {
T donnees;
Noeud<T>* suivant;
};
template <typename T>
class Pile {
private:
Noeud<T>* entete;
int compteur;
Noeud<T>* CreerNoeud(const T& valeur);
public:
Pile();
~Pile();
void empiler(const T& valeur);
void depiler();
T& premier() const;
void afficher() const;
int taille() const;
};
#endif#ifndef PILE_CPP
#define PILE_CPP
#include "pile.h"
template <typename T>
Pile<T>::Pile() : entete(NULL), compteur(0) {}
template <typename T>
Pile<T>::~Pile() {
Noeud<T>* del = entete;
while (entete) {
entete = entete->suivant;
delete del;
del = entete;
}
}
template <typename T>
Noeud<T>* Pile<T>::CreerNoeud(const T& valeur) {
Noeud<T>* temp = new Noeud<T>;
temp->donnees = valeur;
temp->suivant = NULL;
return temp;
}
template <typename T>
void Pile<T>::empiler(const T& valeur) {
Noeud<T>* nouveau = CreerNoeud(valeur);
nouveau->suivant = entete;
entete = nouveau;
compteur++;
}
template <typename T>
void Pile<T>::depiler() {
if (compteur == 0) { cout << "Erreur! La pile est vide." << endl; return; }
Noeud<T>* del = entete;
entete = entete->suivant;
delete del;
compteur--;
}
template <typename T>
T& Pile<T>::premier() const {
if (compteur == 0) { cout << "Erreur! La pile est vide"; assert(false); }
return entete->donnees;
}
template <typename T>
void Pile<T>::afficher() const {
if (compteur == 0) { cout << "La pile est vide!" << endl; return; }
Noeud<T>* courant = entete;
while (courant != 0) {
cout << courant->donnees << endl;
courant = courant->suivant;
}
}
template <typename T>
int Pile<T>::taille() const { return compteur; }
#endifImplémentation par composition (réutilisation de la classe Liste)
Plutôt que de tout réécrire, on peut réutiliser la classe Liste par composition : la pile contient un objet liste et restreint son interface aux trois opérations utiles.
Composition vs Héritage Un objet
Pile n'est pas un objet Liste — il en a moins de fonctionnalités. On préfère donc la composition (la pile possède une liste) plutôt que l'héritage.#ifndef PILE_H
#define PILE_H
#include "liste.cpp"
template <typename T>
class Pile {
private:
Liste<T> liste; // composition : la pile contient une liste
public:
void empiler(const T& valeur);
void depiler();
T& premier() const;
void afficher() const;
int taille() const;
};
#endif#ifndef PILE_CPP
#define PILE_CPP
#include "pile.h"
template <typename T>
void Pile<T>::empiler(const T& valeur) {
liste.inserer(0, valeur); // toujours en position 0 (tête)
}
template <typename T>
void Pile<T>::depiler() {
liste.supprimer(0);
}
template <typename T>
T& Pile<T>::premier() const {
return liste.getNoeud(0);
}
template <typename T>
void Pile<T>::afficher() const {
liste.afficher();
}
template <typename T>
int Pile<T>::taille() const {
return liste.taille();
}
#endifProgramme principal
#include "pile.cpp"
#include <string>
int main() {
Pile<string> pile;
pile.empiler("Mostafa");
pile.empiler("Omar");
pile.empiler("Sara");
pile.empiler("Mohamed");
pile.empiler("Moneim");
pile.empiler("Dounia");
pile.empiler("Abdelmalek");
cout << "Afficher la pile" << endl;
pile.afficher();
cout << '\n';
cout << "Afficher la tete de la pile" << endl;
cout << pile.premier() << endl;
cout << '\n';
cout << "Supprimer quelques noeuds et afficher la pile" << endl;
pile.depiler();
pile.depiler();
pile.afficher();
cout << '\n';
cout << "Afficher la tete de la pile" << endl;
cout << pile.premier() << endl;
cout << '\n';
cout << "Nombre de noeuds dans la pile : " << pile.taille();
return 0;
}Sortie
Afficher la pile Abdelmalek Dounia Moneim Mohamed Sara Omar Mostafa Afficher la tete de la pile Abdelmalek Supprimer quelques noeuds et afficher la pile Moneim Mohamed Sara Omar Mostafa Afficher la tete de la pile Moneim Nombre de noeuds dans la pile : 5
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.