adplus-dvertising

Les piles en C++

Les piles en C++

Souvent, nous avons besoin d'une liste linéaire, mais nous n'avons pas besoin de toute l'interface de la classe de liste chaînée que nous avons définie dans ce cours (Visitez le cours). Nous pouvons adapter l'interface à notre utilisation. Par exemple, nous pouvons adapter la liste chaînée pour créer deux collections plus restreintes appelées une pile et une file d'attente.

Dans ce cours, nous discutons structure pile, plus tard, nous discuterons la structure file d'attente.

Une pile est un conteneur implémenté sous la forme d'une liste linéaire dans laquelle tous les ajouts et suppressions sont limités à une extrémité, appelée tête de la pile (entête). Si nous insérons des éléments de données dans une pile puis les supprimons, l'ordre des éléments de données serait inversé. Les données saisies sous la forme {5, 10, 8, 20} seraient supprimées sous la forme {20, 8, 10, 5}. Cet attribut d'inversion est la raison pour laquelle les piles sont appelées structure de données dernier entré, premier sorti (LIFO – Last In First Out).

Nous utilisons de nombreux types de piles différents dans notre vie quotidienne. On parle souvent d'une pile de disques ou d'une pile de livres. Toute situation dans laquelle vous ne pouvez ajouter ou supprimer qu'un objet en tête est une pile. Si vous souhaitez supprimer un objet autre que celui de tête de la pile, vous devez d'abord supprimer tous les objets au-dessus. Une représentation graphique des piles est présentée dans la figure ci-dessous.

Opérations de base

Nous rencontrons normalement trois opérations de base pour une structure de données de pile : empiler, dépiler et premier.

L'opération d'insertion d'un élément au début de la pile est appelée empiler. L'opération pour supprimer un élément de début est appelée dépiler. L'opération qui accède uniquement à l'élément supérieur sans le supprimer est appelée premier.

Une pile peut être implémentée sous forme de tableau ou de liste chaînée. Bien que l'implémentation du tableau soit plus simple, la taille du tableau doit être fixée au moment de la compilation. Une implémentation de liste chaînée permet à la taille de la pile d'augmenter et de réduire dynamiquement. La figure ci-dessous montre comment nous implémentons normalement une pile en tant que liste chaînée.

Dans la figure ci-dessus, nous avons un objet de pile et un certain nombre d'objets de nœud. L'objet de pile est créé dans la mémoire de pile. Il a une variable entière pour contenir la taille de la pile et un pointeur qui pointe vers le nœud supérieur (tête). Nous avons également un certain nombre d'objets nœuds. Chaque objet nœud a une section de données et une section de pointeur. La section de données peut être de n'importe quel type. Les nœuds sont créés dans le tas car le nombre de nœuds augmente avec chaque opération empiler et diminue avec chaque opération dépiler. Notez que nous avons utilisé la même terminologie que pour une liste chaînée. Nous appelons le pointeur qui pointe vers l'élément supérieur entête. Notez également que la tête de la pile est le premier élément de la liste chaînée sous-jacente.

#ifndef PILE_H
#define PILE_H

#include <iostream>
#include <cassert>

using namespace std;

// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
    T donnees;
    Noeud <T>* suivant;
};

// Définition de la classe Liste
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
        

Implémentation

L'implémentation de la pile est assez similaire à l'implémentation de la liste chaînée, avec quelques petites modifications, l'insertion et la suppression se fait uniquement en tête de liste.

Empiler un élément

L'insertion au début peut être effectuée à l'aide de deux opérations (après avoir créé un nœud), comme le montre la figure ci-dessous.

template <typename T>
void Pile <T> :: empiler (const T& valeur)
{
    Noeud <T>* nouveau = CreerNoeud (valeur);
    //Insertion au début
    nouveau -> suivant = entete;
    entete = nouveau;

    compteur++;
}
        

Dépiler l’élément en tête

La suppression du premier nœud est très simple et peut être effectuée comme le montre la figure ci-dessous.

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;
}
        

La classe Pile.h & Pile.cpp

#ifndef PILE_H
#define PILE_H

#include <iostream>
#include 

using namespace std;

// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
    T donnees;
    Noeud <T>* suivant;
};

// Définition de la classe Liste
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"

// Constructeur
template <typename T>
Pile <T> :: Pile ():entete (NULL), compteur (0) {}

// Destructeur
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);
    //Insertion au début
    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;
}
#endif
                    

Implémentation en utilisant la classe Liste (liste chaînée)

Nous pourrions créer une nouvelle interface et un nouveau fichier d'implémentation pour notre classe Pile, mais il est plus efficace de réutiliser le code créé pour la classe Liste. Une classe Pile est une classe Liste spéciale avec des opérations limitées. Cependant, nous devons nous rappeler qu'un objet Pile n'est pas un objet Liste. Un objet Pile a moins de fonctionnalités qu'un objet Liste.

Un objet Pile compose un objet de Liste et n'utilise que des opérations limitées définies dans la classe Liste. Nous implémentons la classe Pile en utilisant la composition.

Veuillez visiter ce cours pour plus de détails sur la classe Liste

#ifndef PILE_H
#define PILE_H
#include "liste.cpp"

// Définition de la classe Pile

template <typename T>
class Pile
{
    private:
        Liste <T> 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);
}

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();
}
#endif
                    

Programme principal

#include "pile.cpp"
#include 

int main ( ){

    // Instanciation d'une pile
    Pile  pile;
    
    // Insertion de six noeuds dans la pile
    pile.empiler ("Mostafa");
    pile.empiler ("Omar");
    pile.empiler ("Sara");
    pile.empiler ("Mohamed");
    pile.empiler ("Moneim");
    pile.empiler ("Dounia");
    pile.empiler ("Abdelmalek");
    
    // Afficher les valeurs de noeuds
    cout << "Afficher la pile" << endl;
    pile.afficher ();

    cout<<'\n';

    // afficher les valeurs de trois noeuds
    cout << "Afficher la tete de la pile" << endl;
    cout << pile.premier () << endl;
    
    cout<<'\n';

    // Supprimer trois noeuds
    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';
    
    // Afficher la taille apres la suppression
    cout << "Nombre de noeuds dans la pile: " << pile.taille() ;

    return 0;
}
        
Résultat
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

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.