Chapitre 5 : La Structure de Données Pile (Stack)

1. Définition de la Structure de Données Pile

1.1 Le Problème qui a Motivé la Pile

Imaginez que vous êtes en train d'empiler des assiettes dans votre cuisine. Quelle assiette pouvez-vous retirer facilement ? La
dernière que vous avez posée sur le dessus. C'est exactement le principe de la pile (stack en anglais).

Scénarios réels nécessitant une pile :

• Fonction "Annuler" (Undo) : Dans un éditeur de texte, chaque action est empilée. Quand vous appuyez sur Ctrl+Z, la
dernière action est dépilée et annulée.
• Navigation web : Le bouton "Retour" de votre navigateur utilise une pile. Chaque page visitée est empilée, et "Retour" dépile
la dernière page.
• Évaluation d'expressions mathématiques : 3 + 5 * 2 nécessite de mémoriser temporairement des valeurs.
• Appels de fonctions : Quand une fonction appelle une autre fonction, le système doit "se souvenir" où retourner.

1.2 Définition Formelle

Une pile est une structure de données linéaire qui suit le principe LIFO (Last In, First Out) ou DEPS (Dernier Entré, Premier Sorti).

Définition mathématique :
Soit S une pile. On peut la représenter comme une séquence ordonnée :

S = ⟨e1 , e2 , e3 , ..., en ⟩

où :

• en est le sommet de la pile (élément le plus récent)

• e1 est le fond de la pile (élément le plus ancien)
• n est la taille de la pile

Principe LIFO :

Si x est ajoutˊe avant y, alors y sera retirˊe avant x

1.3 Visualisation Conceptuelle

 Sommet (Top)
↓
┌─────────┐
│ 5 │ ← Dernier élément ajouté
├─────────┤
│ 3 │
├─────────┤
│ 7 │
├─────────┤
│ 2 │ ← Premier élément ajouté
└─────────┘
↑
Fond (Bottom)

Opérations possibles :
→ PUSH(8) : Ajouter 8 au sommet
→ POP() : Retirer 5 du sommet

1.4 Propriétés Fondamentales

1. Accès restreint : On ne peut accéder qu'au sommet de la pile
2. Ordre d'insertion préservé : L'ordre relatif des éléments est maintenu
3. Dynamique : La taille peut varier pendant l'exécution
4. Opérations en temps constant : Les opérations principales sont en O(1)

2. Importance de la Structure Pile

2.1 Pourquoi les Piles sont Essentielles ?

Les piles résolvent des problèmes où l'on doit :

• Mémoriser temporairement des informations dans un ordre précis

• Inverser l'ordre de traitement des données
• Gérer des dépendances hiérarchiques ou récursives

2.2 Exemple Fondamental : Appel et Retour de Fonction

Le Problème
Quand un programme exécute des fonctions qui s'appellent entre elles, le système doit :

1. Se souvenir où retourner après chaque fonction

2. Préserver les variables locales de chaque fonction
3. Retourner dans l'ordre inverse des appels

La Solution : La Pile d'Appels (Call Stack)

Considérons ce code :
 int calculer(int x) {
int resultat = multiplier(x, 2);
return resultat + 1;
}

int multiplier(int a, int b) {

return a * b;
}

int main() {
int valeur = calculer(5);
printf("%d", valeur);
return 0;
}

Exécution étape par étape avec la pile d'appels :

 Étape 1: main() démarre
┌──────────────────┐
│ main() │
│ valeur = ? │
└──────────────────┘

Étape 2: main() appelle calculer(5)

┌──────────────────┐
│ calculer(5) │
│ x = 5 │
│ resultat = ? │
├──────────────────┤
│ main() │
│ valeur = ? │
└──────────────────┘

Étape 3: calculer() appelle multiplier(5, 2)

┌──────────────────┐
│ multiplier(5,2) │ ← SOMMET (exécution actuelle)
│ a = 5, b = 2 │
├──────────────────┤
│ calculer(5) │
│ x = 5 │
│ resultat = ? │
├──────────────────┤
│ main() │
│ valeur = ? │
└──────────────────┘

Étape 4: multiplier() retourne 10 (POP)

┌──────────────────┐
│ calculer(5) │ ← SOMMET
│ x = 5 │
│ resultat = 10 │
├──────────────────┤
│ main() │
│ valeur = ? │
└──────────────────┘

Étape 5: calculer() retourne 11 (POP)

┌──────────────────┐
│ main() │ ← SOMMET
│ valeur = 11 │
└──────────────────┘

Étape 6: main() termine (POP)

┌──────────────────┐
│ [vide] │
└──────────────────┘

Analyse Mathématique
Soit n la profondeur d'appels de fonctions. La pile d'appels nécessite :

• Espace : O(n) pour stocker les cadres d'activation

• Temps par appel/retour : O(1) pour chaque PUSH/POP

Invariant de la pile d'appels :

∀t, la fonction au sommet est celle en cours d’exˊecution

2.3 Autres Applications Cruciales
A. Vérification de Parenthèses Équilibrées
Problème : Vérifier si ((a + b) * (c + d)) est bien parenthésé.

Algorithme avec pile :

Pour chaque caractère c :

Si c est '(' → PUSH(c)
Si c est ')' →
Si pile vide → ERREUR
Sinon → POP()
Fin : pile doit être vide

Exemple d'exécution :

Expression: ( ( a + b ) * ( c + d ) )

Caractère | Action | État de la pile

----------|-----------|------------------
( | PUSH | (
( | PUSH | ( (
a | ignorer | ( (
+ | ignorer | ( (
b | ignorer | ( (
) | POP | (
* | ignorer | (
( | PUSH | ( (
c | ignorer | ( (
+ | ignorer | ( (
d | ignorer | ( (
) | POP | (
) | POP | [vide] ✓

B. Conversion Notation Infixe → Postfixe (Notation Polonaise Inverse)

Infixe : 3 + 5 * 2 (notation humaine)
Postfixe : 3 5 2 * + (notation machine)

Les piles permettent cette conversion efficacement.

C. Parcours en Profondeur (DFS) de Graphes

La pile remplace la récursion pour explorer des structures :

PUSH(sommet_initial)
Tant que pile non vide :
sommet = POP()
visiter(sommet)
Pour chaque voisin de sommet :
PUSH(voisin)

3. Primitives de Manipulation d'une Pile

3.1 Création/Initialisation d'une Pile
Concept : Le Pointeur de Pile
Une pile nécessite un pointeur (ou index) qui indique la position du sommet.

Représentation mathématique :

Pile vide : sommet = −1 ou sommet = NULL

États possibles :

Pile vide (initialisée) :

sommet = -1
┌─────────┐
│ [vide] │
└─────────┘

Après PUSH(5) :
sommet = 0
┌─────────┐
│ 5 │ ← sommet
└─────────┘

Après PUSH(3) :
sommet = 1
┌─────────┐
│ 3 │ ← sommet
├─────────┤
│ 5 │
└─────────┘

Pseudocode d'Initialisation

ALGORITHME InitialiserPile()
ENTRÉE : Rien
SORTIE : Une pile vide P

DÉBUT
Créer une structure Pile P
[Link] ← -1 // ou NULL pour chaînée
[Link] ← 0
Retourner P
FIN

Complexité :

• Temps : O(1) - opérations constantes

• Espace : O(1) - allocation de la structure de contrôle

3.2 Tester si la Pile est Pleine (PilePleine/StackFull)

Concept : Capacité Limitée
Pour une pile à représentation contiguë (tableau), il existe une capacité maximale.

Condition mathématique :
 PilePleine(P ) ⟺ P .sommet = P .capacite − 1

où P .capacite est la taille maximale du tableau.

Visualisation

Pile avec capacité = 5, sommet = 4 (5 éléments)

sommet = 4 → ┌─────────┐
│ 8 │ ← Position 4 (PLEINE!)
├─────────┤
│ 2 │ ← Position 3
├─────────┤
│ 7 │ ← Position 2
├─────────┤
│ 1 │ ← Position 1
├─────────┤
│ 3 │ ← Position 0
└─────────┘

PUSH(9) → IMPOSSIBLE ! (débordement)

Pseudocode

ALGORITHME PilePleine(P)
ENTRÉE : Pile P
SORTIE : VRAI si pleine, FAUX sinon

DÉBUT
SI [Link] = [Link] - 1 ALORS
Retourner VRAI
SINON
Retourner FAUX
FIN SI
FIN

Complexité :

• Temps : O(1) - comparaison simple

• Espace : O(1) - aucune mémoire supplémentaire

Important : Pour une pile chaînée, cette opération n'a pas de sens (capacité limitée seulement par la mémoire disponible).

3.3 Tester si la Pile est Vide (PileVide/StackEmpty)

Concept : Détection de Pile Vide
Condition mathématique :

PileVide(P ) ⟺ P .sommet = −1 (contiguë) ou P .sommet = NULL (chaı̂nˊee)

Pourquoi c'est crucial ?

Tenter de dépiler (POP) une pile vide provoque une erreur de sous-dépassement (underflow).
 Pile vide :
sommet = -1
┌─────────┐
│ [vide] │
└─────────┘

POP() → ERREUR ! Rien à retirer

Pseudocode

ALGORITHME PileVide(P)
ENTRÉE : Pile P
SORTIE : VRAI si vide, FAUX sinon

DÉBUT
SI [Link] = -1 ALORS // ou [Link] = NULL
Retourner VRAI
SINON
Retourner FAUX
FIN SI
FIN

Complexité :

• Temps : O(1)
• Espace : O(1)

Invariant de sécurité :

∀ opˊeration POP ou Sommet, on doit vˊerifier : ¬PileVide(P )

3.4 Ajouter un Élément au Sommet (Empiler/Push)

Concept : Insertion au Sommet
L'opération PUSH ajoute un nouvel élément au sommet de la pile.

Transformation mathématique :

PUSH(P , x) : P = ⟨e1 , ..., en ⟩ → P ′ = ⟨e1 , ..., en , x⟩

où x devient le nouveau sommet.

Étapes Logiques
1. Vérifier que la pile n'est pas pleine (débordement)
2. Incrémenter le pointeur de sommet
3. Insérer l'élément à la nouvelle position
4. Mettre à jour la taille (optionnel)

Visualisation Étape par Étape

 État initial :
sommet = 1
┌─────────┐
│ 7 │ ← sommet
├─────────┤
│ 3 │
└─────────┘

Étape 1 : PUSH(9)
Vérification : pile non pleine ✓

Étape 2 : Incrémenter sommet

sommet = 1 → sommet = 2

Étape 3 : Insérer 9
┌─────────┐
│ 9 │ ← nouveau sommet
├─────────┤
│ 7 │
├─────────┤
│ 3 │
└─────────┘

État final :
sommet = 2, taille = 3

Pseudocode Détaillé

ALGORITHME Push(P, element)

ENTRÉE : Pile P, élément à empiler
SORTIE : Pile modifiée ou erreur

DÉBUT
// Étape 1 : Vérification
SI PilePleine(P) ALORS
Afficher "ERREUR : Débordement de pile"
Retourner FAUX
FIN SI

// Étape 2 : Incrémenter le pointeur

[Link] ← [Link] + 1

// Étape 3 : Insertion
[Link][[Link]] ← element

// Étape 4 : Mise à jour (optionnel)

[Link] ← [Link] + 1

Retourner VRAI
FIN

Analyse de Complexité
Complexité temporelle :

T (n) = O(1)

Justification :
 • Vérification pleine : O(1)
• Incrémentation : O(1)
• Affectation : O(1)
• Total : O(1)

Complexité spatiale :

S(n) = O(1)

Aucune mémoire auxiliaire nécessaire.

Invariant de PUSH :

Aprˋes PUSH(x), Sommet(P ) = x

3.5 Supprimer l'Élément du Sommet (Dépiler/Pop)

Concept : Retrait du Sommet
L'opération POP retire et retourne l'élément au sommet de la pile.

Transformation mathématique :

POP(P ) : P = ⟨e1 , ..., en−1 , en ⟩ → P ′ = ⟨e1 , ..., en−1 ⟩, retourne en

Étapes Logiques
1. Vérifier que la pile n'est pas vide (sous-dépassement)
2. Récupérer l'élément au sommet
3. Décrémenter le pointeur de sommet
4. Retourner l'élément récupéré

Visualisation Étape par Étape

 État initial :
sommet = 2
┌─────────┐
│ 9 │ ← sommet (à retirer)
├─────────┤
│ 7 │
├─────────┤
│ 3 │
└─────────┘

Étape 1 : POP()
Vérification : pile non vide ✓

Étape 2 : Récupérer la valeur

element_retire = 9

Étape 3 : Décrémenter sommet

sommet = 2 → sommet = 1

État final :
┌─────────┐
│ 7 │ ← nouveau sommet
├─────────┤
│ 3 │
└─────────┘

Retourne : 9

Note Importante : Suppression Logique vs Physique

En réalité, l'élément 9 reste physiquement dans le tableau :

Mémoire physique :
┌─────────┐
│ 9 │ ← Toujours là, mais "oublié"
├─────────┤
│ 7 │ ← sommet logique
├─────────┤
│ 3 │
└─────────┘

Le prochain PUSH écrasera cette valeur. C'est une suppression logique, pas physique.

Pseudocode Détaillé
 ALGORITHME Pop(P)
ENTRÉE : Pile P
SORTIE : Élément retiré ou erreur

DÉBUT
// Étape 1 : Vérification
SI PileVide(P) ALORS
Afficher "ERREUR : Sous-dépassement de pile"
Retourner NULL // ou valeur sentinelle
FIN SI

// Étape 2 : Récupération
element ← [Link][[Link]]

// Étape 3 : Décrémenter
[Link] ← [Link] - 1

// Étape 4 : Mise à jour (optionnel)

[Link] ← [Link] - 1

Retourner element
FIN

Analyse de Complexité
Complexité temporelle :

T (n) = O(1)

Complexité spatiale :

S(n) = O(1)

Invariant de POP :

Aprˋes POP(), P .sommet = P .sommetancien − 1

3.6 Consulter l'Élément du Sommet (Sommet/Top/Peek)

Concept : Lecture Non-Destructive
Contrairement à POP, Sommet (ou Top/Peek) retourne l'élément au sommet sans le retirer.

Opération mathématique :

Sommet(P ) : P = ⟨e1 , ..., en ⟩ → en , P reste inchangˊe

Pourquoi cette Opération ?

Parfois, on veut inspecter le sommet sans le modifier :

• Vérifier une condition avant de dépiler

• Comparer avec une autre valeur
• Implémenter des algorithmes qui consultent plusieurs fois

Visualisation
 État avant Sommet() :
sommet = 2
┌─────────┐
│ 9 │ ← sommet
├─────────┤
│ 7 │
├─────────┤
│ 3 │
└─────────┘

Après valeur = Sommet() :

valeur = 9
┌─────────┐
│ 9 │ ← sommet (inchangé !)
├─────────┤
│ 7 │
├─────────┤
│ 3 │
└─────────┘

Pseudocode

ALGORITHME Sommet(P)
ENTRÉE : Pile P
SORTIE : Élément au sommet ou erreur

DÉBUT
// Vérification
SI PileVide(P) ALORS
Afficher "ERREUR : Pile vide"
Retourner NULL
FIN SI

// Retour direct (pas de modification)

Retourner [Link][[Link]]
FIN

Comparaison Pop vs Sommet

Opération | État Initial | Action | État Final | Retour

-------------|--------------|-------------|---------------|-------
Pop() | [3,7,9] | Retire 9 | [3,7] | 9
Sommet() | [3,7,9] | Consulte 9 | [3,7,9] | 9

Complexité :

• Temps : O(1)
• Espace : O(1)

Invariant :

Sommet(P ) = Sommet(P ) (idempotent)

4. Implémentation d'une Pile

4.1 Représentation Contiguë (Tableau)
Principe
La pile est implémentée avec un tableau statique ou dynamique où :

• Les éléments sont stockés consécutivement en mémoire

• Un index/pointeur sommet indique la position du dernier élément

Structure en Mémoire

Mémoire physique :

Adresse Contenu Index Rôle

--------- ------- ----- ----
0x1000 3 [0] Fond
0x1004 7 [1]
0x1008 9 [2] Sommet (sommet = 2)
0x100C ? [3] Non utilisé
0x1010 ? [4] Non utilisé
...
capacite - 1 Limite

Diagramme Mermaid de la Structure

Structure Pile

Tableau elements Entier sommet Entier capacite Entier taille

elements 0 elements 1 elements 2 ... elements capacite-1

Avantages de la Représentation Contiguë

1. Accès direct : O(1) pour accéder au sommet
2. Simplicité : Implémentation facile
3. Cache-friendly : Données contiguës en mémoire (meilleure performance CPU)
4. Pas de pointeurs : Moins de gestion de mémoire

Inconvénients
1. Taille fixe : Capacité définie à l'avance
2. Gaspillage mémoire : Si la pile n'est jamais pleine
3. Débordement : Impossible d'ajouter au-delà de la capacité

Formules Mathématiques
Espace mémoire requis :

M = capacite × sizeof(element) + sizeof(mˊetadonnˊees)

Taux d'utilisation :

taille
Utilisation = × 100%
capacite
4.2 Représentation Chaînée (Liste Chaînée)
Principe
La pile est implémentée avec une liste chaînée où :

• Chaque élément est un nœud contenant une valeur et un pointeur vers le nœud suivant
• Le sommet pointe vers le premier nœud
• Pas de limite de capacité (sauf la mémoire totale)

Structure en Mémoire

Mémoire dispersée :

sommet → ┌──────────────┐
│ valeur: 9 │ Adresse: 0x2050
│ suivant: ────┼─→ ┌──────────────┐
└──────────────┘ │ valeur: 7 │ Adresse: 0x3020
│ suivant: ────┼─→ ┌──────────────┐
└──────────────┘ │ valeur: 3 │ Adresse: 0x1080
│ suivant: NULL│
└──────────────┘

Diagramme Mermaid de la Structure

suivant NULL

suivant Nœud 3

suivant Nœud 2 donnee 3

Pile sommet Nœud 1 donnee 7

donnee 9

Avantages de la Représentation Chaînée

1. Taille dynamique : Croît selon les besoins
2. Pas de débordement : (sauf mémoire système épuisée)
3. Flexibilité : Peut partager des nœuds entre structures

Inconvénients
1. Overhead mémoire : Chaque nœud stocke un pointeur supplémentaire
2. Allocation dynamique : Coût de malloc/free à chaque opération
3. Fragmentation : Données dispersées en mémoire
4. Cache-unfriendly : Moins efficace pour le CPU

Formules Mathématiques
Espace mémoire par élément :

Mnoeud = sizeof(donnee) + sizeof(pointeur)

Espace total pour n éléments :

 Mtotal = n × Mnoeud + sizeof(pointeur sommet)

Overhead mémoire :

sizeof(pointeur)
Overhead = × 100%
sizeof(donnee) + sizeof(pointeur)

Pour un entier (4 octets) et un pointeur (8 octets sur 64-bit) :

8
Overhead = × 100% = 66.67%
4+8

4.3 Comparaison : Contiguë vs Chaînée

Critère Contiguë (Tableau) Chaînée (Liste)

Accès sommet O(1) O(1)

Push O(1) O(1)
Pop O(1) O(1)
Espace/élément k octets k + p octets (p=pointeur)
Capacité Fixe Dynamique

Débordement Possible Rare

Localité mémoire Excellente Mauvaise

Complexité implémentation Simple Moyenne

5. Implémentation en Langage C

5.1 Implémentation Contiguë en C (Procédural)

Structure de Données

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define CAPACITE_MAX 100

// Structure représentant une pile contiguë

typedef struct {
int elements[CAPACITE_MAX]; // Tableau stockant les éléments
int sommet; // Index du sommet (-1 si vide)
int capacite; // Capacité maximale
} Pile;

Explication :

• elements[] : Tableau statique de taille fixe

• sommet : Initialisé à -1 pour indiquer une pile vide
• capacite : Permet de gérer différentes tailles si nécessaire
Initialisation

/**
* Crée et initialise une pile vide
* Complexité : O(1)
*/
void initialiser_pile(Pile* p) {
p->sommet = -1; // Pile vide
p->capacite = CAPACITE_MAX; // Taille maximale

// Note : Pas besoin d'initialiser elements[]

// car ils seront écrasés lors des PUSH
}

Logique :

1. Positionner sommet à -1 signifie "aucun élément"

2. Définir la capacité pour les vérifications futures

Test de Pile Vide

/**
* Vérifie si la pile est vide
* Complexité : O(1)
*/
bool est_vide(Pile* p) {
return p->sommet == -1;
}

Logique : Condition simple : si sommet == -1 , aucun élément n'a été ajouté.

Test de Pile Pleine

/**
* Vérifie si la pile est pleine
* Complexité : O(1)
*/
bool est_pleine(Pile* p) {
return p->sommet == p->capacite - 1;
}

Logique :

• Les indices vont de 0 à capacite - 1

• Si sommet == capacite - 1 , toutes les positions sont occupées

Opération Push (Empiler)

 /**
* Ajoute un élément au sommet de la pile
* Complexité : O(1)
*
* @param p Pointeur vers la pile
* @param valeur Valeur à empiler
* @return true si succès, false si débordement
*/
bool push(Pile* p, int valeur) {
// Étape 1 : Vérification débordement
if (est_pleine(p)) {
printf("ERREUR : Débordement de pile (overflow)\n");
return false;
}

// Étape 2 : Incrémenter le sommet

p->sommet++;

// Étape 3 : Insérer la valeur

p->elements[p->sommet] = valeur;

return true;
}

Logique détaillée :

Avant : sommet = 1, elements = [3, 7, ?, ?, ...]

Push(9)
Après incrémentation : sommet = 2
Après insertion : elements = [3, 7, 9, ?, ...]

Trace d'exécution :

Pile p;
initialiser_pile(&p);
push(&p, 3); // sommet=0, elements[0]=3
push(&p, 7); // sommet=1, elements[1]=7
push(&p, 9); // sommet=2, elements[2]=9

Opération Pop (Dépiler)

 /**
* Retire et retourne l'élément au sommet
* Complexité : O(1)
*
* @param p Pointeur vers la pile
* @param valeur Pointeur pour stocker la valeur retirée
* @return true si succès, false si pile vide
*/
bool pop(Pile* p, int* valeur) {
// Étape 1 : Vérification sous-dépassement
if (est_vide(p)) {
printf("ERREUR : Sous-dépassement de pile (underflow)\n");
return false;
}

// Étape 2 : Récupérer la valeur

*valeur = p->elements[p->sommet];

// Étape 3 : Décrémenter le sommet

p->sommet--;

return true;
}

Logique détaillée :

Avant : sommet = 2, elements = [3, 7, 9, ?, ...]

Pop()
valeur récupérée : 9
Après décrémentation : sommet = 1
État logique : [3, 7] (9 toujours physiquement là)

Note importante : On ne supprime pas physiquement la valeur ! Elle sera écrasée au prochain push.

Opération Sommet (Consulter)

/**
* Consulte l'élément au sommet sans le retirer
* Complexité : O(1)
*
* @param p Pointeur vers la pile
* @param valeur Pointeur pour stocker la valeur consultée
* @return true si succès, false si pile vide
*/
bool sommet(Pile* p, int* valeur) {
if (est_vide(p)) {
printf("ERREUR : Pile vide\n");
return false;
}

// Simple lecture, pas de modification

*valeur = p->elements[p->sommet];

return true;
}

Affichage (Utilitaire)
 /**
* Affiche le contenu de la pile (pour débogage)
* Complexité : O(n) où n est le nombre d'éléments
*/
void afficher_pile(Pile* p) {
if (est_vide(p)) {
printf("Pile vide\n");
return;
}

printf("Pile (sommet -> fond) : ");

for (int i = p->sommet; i >= 0; i--) {
printf("%d ", p->elements[i]);
}
printf("\n");
}

Programme Complet de Test

 int main() {
Pile ma_pile;
initialiser_pile(&ma_pile);

printf("=== Test de la Pile Contiguë ===\n\n");

// Test 1 : Empilage
printf("Test 1 : Empilage\n");
push(&ma_pile, 10);
push(&ma_pile, 20);
push(&ma_pile, 30);
afficher_pile(&ma_pile); // 30 20 10

// Test 2 : Consultation du sommet

printf("\nTest 2 : Consultation du sommet\n");
int valeur;
if (sommet(&ma_pile, &valeur)) {
printf("Sommet : %d\n", valeur);
}
afficher_pile(&ma_pile); // Inchangé : 30 20 10

// Test 3 : Dépilage
printf("\nTest 3 : Dépilage\n");
if (pop(&ma_pile, &valeur)) {
printf("Valeur dépilée : %d\n", valeur);
}
afficher_pile(&ma_pile); // 20 10

// Test 4 : Dépilage complet

printf("\nTest 4 : Dépilage complet\n");
while (pop(&ma_pile, &valeur)) {
printf("Dépilé : %d\n", valeur);
}
afficher_pile(&ma_pile); // Pile vide

// Test 5 : Sous-dépassement
printf("\nTest 5 : Tentative de dépilage sur pile vide\n");
pop(&ma_pile, &valeur); // Affiche erreur

// Test 6 : Débordement
printf("\nTest 6 : Test de débordement\n");
for (int i = 0; i < CAPACITE_MAX + 1; i++) {
if (!push(&ma_pile, i)) {
printf("Débordement détecté après %d éléments\n", i);
break;
}
}

return 0;
}

Sortie attendue :
 === Test de la Pile Contiguë ===

Test 1 : Empilage
Pile (sommet -> fond) : 30 20 10

Test 2 : Consultation du sommet

Sommet : 30
Pile (sommet -> fond) : 30 20 10

Test 3 : Dépilage
Valeur dépilée : 30
Pile (sommet -> fond) : 20 10

Test 4 : Dépilage complet

Dépilé : 20
Dépilé : 10
Pile vide

Test 5 : Tentative de dépilage sur pile vide

ERREUR : Sous-dépassement de pile (underflow)

Test 6 : Test de débordement

ERREUR : Débordement de pile (overflow)
Débordement détecté après 100 éléments

5.2 Implémentation Chaînée en C (Procédural)

Structure de Données

// Nœud de la liste chaînée

typedef struct Noeud {
int donnee; // Valeur stockée
struct Noeud* suivant; // Pointeur vers le nœud suivant
} Noeud;

// Structure de la pile chaînée

typedef struct {
Noeud* sommet; // Pointeur vers le nœud au sommet
int taille; // Nombre d'éléments (optionnel)
} PileChaînee;

Explication :

• Chaque Noeud contient une valeur et un lien vers le suivant

• PileChaînee maintient uniquement le pointeur vers le sommet
• taille est optionnel mais utile pour certains algorithmes

Initialisation
 /**
* Initialise une pile chaînée vide
* Complexité : O(1)
*/
void initialiser_pile_chainee(PileChaînee* p) {
p->sommet = NULL; // Pile vide
p->taille = 0;
}

Test de Pile Vide

/**
* Vérifie si la pile chaînée est vide
* Complexité : O(1)
*/
bool est_vide_chainee(PileChaînee* p) {
return p->sommet == NULL;
}

Note : Pour une pile chaînée, il n'y a pas de test "est pleine" (capacité illimitée).

Opération Push (Empiler)

/**
* Ajoute un élément au sommet de la pile chaînée
* Complexité : O(1)
*
* @param p Pointeur vers la pile
* @param valeur Valeur à empiler
* @return true si succès, false si allocation échoue
*/
bool push_chainee(PileChaînee* p, int valeur) {
// Étape 1 : Allouer un nouveau nœud
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
if (nouveau == NULL) {
printf("ERREUR : Allocation mémoire échouée\n");
return false;
}

// Étape 2 : Initialiser le nouveau nœud

nouveau->donnee = valeur;
nouveau->suivant = p->sommet; // Pointe vers l'ancien sommet

// Étape 3 : Mettre à jour le sommet

p->sommet = nouveau;

// Étape 4 : Incrémenter la taille

p->taille++;

return true;
}

Logique détaillée :
 Avant Push(9) :
sommet → [7] → [3] → NULL

Étape 1 : Créer nouveau nœud

nouveau → [9] → ?

Étape 2 : Lier nouveau à l'ancien sommet

nouveau → [9] → [7] → [3] → NULL

Étape 3 : Mettre à jour sommet

sommet → [9] → [7] → [3] → NULL

Visualisation ASCII :

Avant :
sommet
↓
┌───┬──┐ ┌───┬──┐ ┌───┬────┐
│ 7 │ ●┼──→│ 3 │ ●┼──→│ ? │NULL│
└───┴──┘ └───┴──┘ └───┴────┘

Après Push(9) :
sommet
↓
┌───┬──┐ ┌───┬──┐ ┌───┬──┐ ┌───┬────┐
│ 9 │ ●┼──→│ 7 │ ●┼──→│ 3 │ ●┼──→│ ? │NULL│
└───┴──┘ └───┴──┘ └───┴──┘ └───┴────┘

Opération Pop (Dépiler)

 /**
* Retire et retourne l'élément au sommet
* Complexité : O(1)
*
* @param p Pointeur vers la pile
* @param valeur Pointeur pour stocker la valeur retirée
* @return true si succès, false si pile vide
*/
bool pop_chainee(PileChaînee* p, int* valeur) {
// Étape 1 : Vérification pile vide
if (est_vide_chainee(p)) {
printf("ERREUR : Pile vide\n");
return false;
}

// Étape 2 : Sauvegarder le pointeur à libérer

Noeud* ancien_sommet = p->sommet;

// Étape 3 : Récupérer la valeur

*valeur = ancien_sommet->donnee;

// Étape 4 : Mettre à jour le sommet

p->sommet = ancien_sommet->suivant;

// Étape 5 : Libérer la mémoire

free(ancien_sommet);

// Étape 6 : Décrémenter la taille

p->taille--;

return true;
}

Logique détaillée :

Avant Pop() :
sommet → [9] → [7] → [3] → NULL
↑
ancien_sommet

Après mise à jour :

ancien_sommet → [9] → X
sommet → [7] → [3] → NULL

Après free :
sommet → [7] → [3] → NULL

Important : Il faut toujours libérer le nœud retiré pour éviter les fuites mémoire.

Opération Sommet (Consulter)

 /**
* Consulte l'élément au sommet sans le retirer
* Complexité : O(1)
*/
bool sommet_chainee(PileChaînee* p, int* valeur) {
if (est_vide_chainee(p)) {
printf("ERREUR : Pile vide\n");
return false;
}

*valeur = p->sommet->donnee;
return true;
}

Affichage (Utilitaire)

/**
* Affiche le contenu de la pile chaînée
* Complexité : O(n)
*/
void afficher_pile_chainee(PileChaînee* p) {
if (est_vide_chainee(p)) {
printf("Pile vide\n");
return;
}

printf("Pile (sommet -> fond) : ");

Noeud* courant = p->sommet;
while (courant != NULL) {
printf("%d ", courant->donnee);
courant = courant->suivant;
}
printf("\n");
}

Libération de la Mémoire

/**
* Libère toute la mémoire de la pile
* Complexité : O(n)
* CRUCIAL pour éviter les fuites mémoire !
*/
void detruire_pile_chainee(PileChaînee* p) {
int valeur;
while (!est_vide_chainee(p)) {
pop_chainee(p, &valeur); // Libère chaque nœud
}
printf("Pile détruite, mémoire libérée\n");
}

Programme Complet de Test

 int main() {
PileChaînee ma_pile;
initialiser_pile_chainee(&ma_pile);

printf("=== Test de la Pile Chaînée ===\n\n");

// Test 1 : Empilage
printf("Test 1 : Empilage\n");
push_chainee(&ma_pile, 100);
push_chainee(&ma_pile, 200);
push_chainee(&ma_pile, 300);
afficher_pile_chainee(&ma_pile);

// Test 2 : Consultation
printf("\nTest 2 : Consultation\n");
int valeur;
if (sommet_chainee(&ma_pile, &valeur)) {
printf("Sommet : %d\n", valeur);
}

// Test 3 : Dépilage
printf("\nTest 3 : Dépilage\n");
while (pop_chainee(&ma_pile, &valeur)) {
printf("Dépilé : %d\n", valeur);
}

// Test 4 : Pile vide

printf("\nTest 4 : Opération sur pile vide\n");
pop_chainee(&ma_pile, &valeur);

// Test 5 : Pas de limite de capacité

printf("\nTest 5 : Empilage massif (10000 éléments)\n");
for (int i = 0; i < 10000; i++) {
push_chainee(&ma_pile, i);
}
printf("Taille de la pile : %d\n", ma_pile.taille);

// Nettoyage
detruire_pile_chainee(&ma_pile);

return 0;
}

Sortie attendue :
 === Test de la Pile Chaînée ===

Test 1 : Empilage
Pile (sommet -> fond) : 300 200 100

Test 2 : Consultation
Sommet : 300

Test 3 : Dépilage
Dépilé : 300
Dépilé : 200
Dépilé : 100

Test 4 : Opération sur pile vide

ERREUR : Pile vide

Test 5 : Empilage massif (10000 éléments)

Taille de la pile : 10000
Pile détruite, mémoire libérée

5.3 Analyse Comparative des Implémentations C

Comparaison Mémoire : Contiguë vs Chaînée
Pour une pile de n éléments (int = 4 octets, pointeur = 8 octets sur 64-bit) :

Pile Contiguë :
Mcontiguë = capacitˊe × 4 + 12 octets (mˊetadonnˊees)

Pour capacité = 100 :

Mcontiguë = 100 × 4 + 12 = 412 octets

Pile Chaînée (n éléments) :

Mchaı̂nˊee = n × (4 + 8) + 16 = 12n + 16 octets

Pour n = 100 :
Mchaı̂nˊee = 12 × 100 + 16 = 1216 octets

Graphique de comparaison :

Mémoire utilisée (octets) pour différentes tailles

n | Contiguë | Chaînée | Ratio

------|----------|---------|-------
10 | 412 | 136 | 0.33
50 | 412 | 616 | 1.50
100 | 412 | 1216 | 2.95
200 | 412 | 2416 | 5.86

Observation : Chaînée devient plus coûteuse avec n

Choix de l'Implémentation
Utilisez Contiguë si :

• Taille maximale connue à l'avance

• Performance critique (cache CPU)
 • Mémoire limitée
• Pas de réallocation nécessaire

Utilisez Chaînée si :

• Taille imprévisible
• Insertions/suppressions fréquentes
• Pas de limite de capacité souhaitée
• Partage de nœuds entre structures

6. Implémentation en C++ (Orienté Objet)

6.1 Implémentation Contiguë en C++

Principe de l'Encapsulation
En C++, nous utilisons une classe qui :

• Encapsule les données (privées)

• Expose des méthodes publiques
• Gère automatiquement la mémoire (destructeur)
• Fournit des constructeurs

Structure de la Classe
 #include <iostream>
#include <stdexcept>

/**
* Classe représentant une pile contiguë
* Template permet de gérer différents types de données
*/
template <typename T>
class PileContigue {
private:
T* elements; // Tableau dynamique
int sommet; // Index du sommet
int capacite; // Capacité maximale

public:
// Constructeur
PileContigue(int cap = 100);

// Destructeur
~PileContigue();

// Méthodes principales
void push(const T& valeur);
T pop();
T top() const;

// Méthodes de vérification
bool estVide() const;
bool estPleine() const;
int taille() const;

// Affichage
void afficher() const;
};

Correspondance avec C :

C (Procédural) C++ (Orienté Objet)

----------------- --------------------
struct Pile class PileContigue
Pile p; PileContigue<int> p;
initialiser_pile(&p) [Link]() (constructeur)
push(&p, val) [Link](val)
pop(&p, &val) val = [Link]()
[pas de nettoyage auto] ~PileContigue() (destructeur)

Implémentation du Constructeur
 /**
* Constructeur : initialise une pile avec capacité donnée
* Complexité : O(capacite) pour allocation
*/
template <typename T>
PileContigue<T>::PileContigue(int cap) : capacite(cap), sommet(-1) {
// Allocation dynamique
elements = new T[capacite];

std::cout << "Pile créée avec capacité " << capacite << std::endl;
}

Logique :

1. Liste d'initialisation : capacite(cap), sommet(-1) initialise les membres

2. Allocation dynamique : new T[capacite] alloue le tableau
3. Différence avec C : En C++, new remplace malloc

Implémentation du Destructeur

/**
* Destructeur : libère automatiquement la mémoire
* Complexité : O(1)
*/
template <typename T>
PileContigue<T>::~PileContigue() {
delete[] elements; // Libération du tableau

std::cout << "Pile détruite, mémoire libérée" << std::endl;

}

Avantage majeur : Le destructeur est appelé automatiquement à la fin de la portée, contrairement au C où on doit appeler free
manuellement.

void fonction() {
PileContigue<int> p(50); // Constructeur appelé
[Link](10);
[Link](20);
// ... code ...
} // Destructeur appelé automatiquement ici !

Méthodes de Vérification
 /**
* Vérifie si la pile est vide
* Complexité : O(1)
*/
template <typename T>
bool PileContigue<T>::estVide() const {
return sommet == -1;
}

/**
* Vérifie si la pile est pleine
* Complexité : O(1)
*/
template <typename T>
bool PileContigue<T>::estPleine() const {
return sommet == capacite - 1;
}

/**
* Retourne le nombre d'éléments
* Complexité : O(1)
*/
template <typename T>
int PileContigue<T>::taille() const {
return sommet + 1;
}

Note : Le mot-clé const après la déclaration indique que ces méthodes ne modifient pas l'objet.

Méthode Push

/**
* Ajoute un élément au sommet
* Complexité : O(1)
* Lance une exception si pile pleine
*/
template <typename T>
void PileContigue<T>::push(const T& valeur) {
// Vérification débordement
if (estPleine()) {
throw std::overflow_error("Débordement de pile : capacité maximale atteinte");
}

// Incrémentation et insertion
sommet++;
elements[sommet] = valeur;
}

Différences avec C :

1. Exceptions : Au lieu de retourner bool , on lance une exception

2. Passage par référence constante : const T& évite la copie inutile
3. Pas de pointeur : L'objet est implicite ( this )

Gestion d'erreur C vs C++ :

 // C : Vérification manuelle
int val;
if (!pop(&p, &val)) {
printf("Erreur\n");
}

// C++ : Try-catch
try {
int val = [Link]();
} catch (const std::underflow_error& e) {
std::cout << "Erreur : " << [Link]() << std::endl;
}

Méthode Pop

/**
* Retire et retourne l'élément au sommet
* Complexité : O(1)
* Lance une exception si pile vide
*/
template <typename T>
T PileContigue<T>::pop() {
// Vérification sous-dépassement
if (estVide()) {
throw std::underflow_error("Sous-dépassement de pile : aucun élément");
}

// Récupération et décrémentation
T valeur = elements[sommet];
sommet--;

return valeur;
}

Retour par valeur :

• En C, on passait un pointeur pour "retourner" : pop(&p, &val)

• En C++, on retourne directement : val = [Link]()

Méthode Top

/**
* Consulte l'élément au sommet sans le retirer
* Complexité : O(1)
*/
template <typename T>
T PileContigue<T>::top() const {
if (estVide()) {
throw std::underflow_error("Pile vide : aucun élément à consulter");
}

return elements[sommet];
}

Méthode Afficher
 /**
* Affiche le contenu de la pile
* Complexité : O(n)
*/
template <typename T>
void PileContigue<T>::afficher() const {
if (estVide()) {
std::cout << "Pile vide" << std::endl;
return;
}

std::cout << "Pile (sommet -> fond) : ";

for (int i = sommet; i >= 0; i--) {
std::cout << elements[i] << " ";
}
std::cout << std::endl;
}

Programme de Test Complet

 int main() {
std::cout << "=== Test Pile Contiguë C++ ===" << std::endl << std::endl;

try {
// Création de la pile
PileContigue<int> pile(5);

// Test 1 : Empilage
std::cout << "Test 1 : Empilage" << std::endl;
[Link](10);
[Link](20);
[Link](30);
[Link]();
std::cout << "Taille : " << [Link]() << std::endl;

// Test 2 : Consultation
std::cout << "\nTest 2 : Consultation du sommet" << std::endl;
std::cout << "Sommet : " << [Link]() << std::endl;
[Link](); // Inchangé

// Test 3 : Dépilage
std::cout << "\nTest 3 : Dépilage" << std::endl;
std::cout << "Dépilé : " << [Link]() << std::endl;
[Link]();

// Test 4 : Débordement
std::cout << "\nTest 4 : Test de débordement" << std::endl;
[Link](40);
[Link](50);
[Link](60);
[Link](70); // Devrait lancer une exception

} catch (const std::overflow_error& e) {

std::cout << "Exception attrapée : " << [Link]() << std::endl;
} catch (const std::underflow_error& e) {
std::cout << "Exception attrapée : " << [Link]() << std::endl;
}

// Test 5 : Pile avec des strings

std::cout << "\n=== Test avec des chaînes ===" << std::endl;
PileContigue<std::string> pile_str(3);
pile_str.push("Bonjour");
pile_str.push("le");
pile_str.push("monde");
pile_str.afficher();

return 0;
}

Sortie attendue :
 === Test Pile Contiguë C++ ===

Pile créée avec capacité 5

Test 1 : Empilage
Pile (sommet -> fond) : 30 20 10
Taille : 3

Test 2 : Consultation du sommet

Sommet : 30
Pile (sommet -> fond) : 30 20 10

Test 3 : Dépilage
Dépilé : 30
Pile (sommet -> fond) : 20 10

Test 4 : Test de débordement

Exception attrapée : Débordement de pile : capacité maximale atteinte

=== Test avec des chaînes ===

Pile créée avec capacité 3
Pile (sommet -> fond) : monde le Bonjour
Pile détruite, mémoire libérée
Pile détruite, mémoire libérée

6.2 Implémentation Chaînée en C++

Structure de la Classe
 /**
* Classe pour les nœuds de la pile chaînée
*/
template <typename T>
class Noeud {
public:
T donnee;
Noeud<T>* suivant;

// Constructeur
Noeud(const T& val) : donnee(val), suivant(nullptr) {}
};

/**
* Classe représentant une pile chaînée
*/
template <typename T>
class PileChainee {
private:
Noeud<T>* sommet;
int taille_pile;

public:
// Constructeur
PileChainee();

// Destructeur
~PileChainee();

// Constructeur de copie (important !)

PileChainee(const PileChainee<T>& autre);

// Opérateur d'affectation
PileChainee<T>& operator=(const PileChainee<T>& autre);

// Méthodes principales
void push(const T& valeur);
T pop();
T top() const;

// Méthodes de vérification
bool estVide() const;
int taille() const;

// Affichage
void afficher() const;
};

Nouvelle notion : La Règle des Trois

En C++, quand une classe gère des ressources dynamiques (pointeurs), elle doit définir :

1. Destructeur : pour libérer la mémoire

2. Constructeur de copie : pour copier correctement
3. Opérateur d'affectation : pour affecter correctement

Sinon, on risque des copies superficielles (shallow copy) qui causent des problèmes.

Problème des Copies Superficielles

 Copie superficielle (MAUVAIS) :
[Link] → [9] → [7] → NULL
↑
[Link] ────┘
(Deux piles pointent vers la même mémoire !)

Copie profonde (CORRECT) :

[Link] → [9] → [7] → NULL
[Link] → [9] → [7] → NULL
(Deux copies indépendantes)

Implémentation du Constructeur

/**
* Constructeur : initialise une pile vide
* Complexité : O(1)
*/
template <typename T>
PileChainee<T>::PileChainee() : sommet(nullptr), taille_pile(0) {
std::cout << "Pile chaînée créée" << std::endl;
}

Implémentation du Destructeur

/**
* Destructeur : libère tous les nœuds
* Complexité : O(n)
*/
template <typename T>
PileChainee<T>::~PileChainee() {
while (!estVide()) {
pop(); // Dépile et libère chaque nœud
}
std::cout << "Pile chaînée détruite" << std::endl;
}

Constructeur de Copie
 /**
* Constructeur de copie : crée une copie profonde
* Complexité : O(n)
*/
template <typename T>
PileChainee<T>::PileChainee(const PileChainee<T>& autre)
: sommet(nullptr), taille_pile(0) {

if ([Link]()) {
return;
}

// Copier tous les nœuds

Noeud<T>* courant_autre = [Link];
Noeud<T>* precedent = nullptr;

while (courant_autre != nullptr) {

// Créer nouveau nœud
Noeud<T>* nouveau = new Noeud<T>(courant_autre->donnee);

if (precedent == nullptr) {
sommet = nouveau; // Premier nœud
} else {
precedent->suivant = nouveau;
}

precedent = nouveau;
courant_autre = courant_autre->suivant;
taille_pile++;
}
}

Logique détaillée :

autre : [9] → [7] → [3] → NULL

Itération 1 : Copier 9
nouveau → [9] → nullptr
sommet → [9]

Itération 2 : Copier 7
nouveau → [7] → nullptr
sommet → [9] → [7]

Itération 3 : Copier 3
nouveau → [3] → nullptr
sommet → [9] → [7] → [3] → NULL

Résultat : Copie complète et indépendante

Opérateur d'Affectation
 /**
* Opérateur d'affectation : affecte une pile à une autre
* Complexité : O(n + m) où n est la taille de this, m celle de autre
*/
template <typename T>
PileChainee<T>& PileChainee<T>::operator=(const PileChainee<T>& autre) {
// Vérification d'auto-affectation
if (this == &autre) {
return *this;
}

// Libérer la mémoire existante

while (!estVide()) {
pop();
}

// Copier depuis autre (comme constructeur de copie)

if (![Link]()) {
Noeud<T>* courant_autre = [Link];
Noeud<T>* precedent = nullptr;

while (courant_autre != nullptr) {

Noeud<T>* nouveau = new Noeud<T>(courant_autre->donnee);

if (precedent == nullptr) {
sommet = nouveau;
} else {
precedent->suivant = nouveau;
}

precedent = nouveau;
courant_autre = courant_autre->suivant;
taille_pile++;
}
}

return *this;
}

Pourquoi vérifier l'auto-affectation ?

pile = pile; // Sans vérification, on détruirait pile avant de la copier !

Méthode Push
 /**
* Ajoute un élément au sommet
* Complexité : O(1)
*/
template <typename T>
void PileChainee<T>::push(const T& valeur) {
// Créer nouveau nœud
Noeud<T>* nouveau = new Noeud<T>(valeur);

// Lier au sommet actuel

nouveau->suivant = sommet;

// Mettre à jour sommet

sommet = nouveau;

taille_pile++;
}

Comparaison C vs C++ :

// C
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->donnee = valeur;
nouveau->suivant = p->sommet;

// C++
Noeud<T>* nouveau = new Noeud<T>(valeur); // Constructeur fait tout
nouveau->suivant = sommet;

Méthode Pop

/**
* Retire et retourne l'élément au sommet
* Complexité : O(1)
*/
template <typename T>
T PileChainee<T>::pop() {
if (estVide()) {
throw std::underflow_error("Pile vide : impossible de dépiler");
}

// Sauvegarder le nœud à supprimer

Noeud<T>* ancien_sommet = sommet;
T valeur = ancien_sommet->donnee;

// Mettre à jour le sommet

sommet = sommet->suivant;

// Libérer la mémoire
delete ancien_sommet;

taille_pile--;
return valeur;
}

Méthodes Auxiliaires
 /**
* Vérifie si la pile est vide
* Complexité : O(1)
*/
template <typename T>
bool PileChainee<T>::estVide() const {
return sommet == nullptr;
}

/**
* Retourne le nombre d'éléments
* Complexité : O(1)
*/
template <typename T>
int PileChainee<T>::taille() const {
return taille_pile;
}

/**
* Consulte le sommet sans le retirer
* Complexité : O(1)
*/
template <typename T>
T PileChainee<T>::top() const {
if (estVide()) {
throw std::underflow_error("Pile vide : aucun élément");
}
return sommet->donnee;
}

/**
* Affiche le contenu de la pile
* Complexité : O(n)
*/
template <typename T>
void PileChainee<T>::afficher() const {
if (estVide()) {
std::cout << "Pile vide" << std::endl;
return;
}

std::cout << "Pile (sommet -> fond) : ";

Noeud<T>* courant = sommet;
while (courant != nullptr) {
std::cout << courant->donnee << " ";
courant = courant->suivant;
}
std::cout << std::endl;
}

Programme de Test Complet

int main() {
std::cout << "=== Test Pile Chaînée C++ ===" << std::endl << std::endl;

try {
// Test 1 : Opérations de base
std::cout << "Test 1 : Opérations de base" << std::endl;
PileChainee<int> pile1;
[Link](100);
[Link](200);
[Link](300);
[Link]();
std::cout << "Taille : " << [Link]() << std::endl;

// Test 2 : Consultation et dépilage

std::cout << "\nTest 2 : Consultation et dépilage" << std::endl;
std::cout << "Sommet : " << [Link]() << std::endl;
std::cout << "Dépilé : " << [Link]() << std::endl;
[Link]();

// Test 3 : Constructeur de copie

std::cout << "\nTest 3 : Constructeur de copie" << std::endl;
PileChainee<int> pile2(pile1); // Copie profonde
std::cout << "Pile 1 : ";
[Link]();
std::cout << "Pile 2 (copie) : ";
[Link]();

// Modifier pile2 ne doit pas affecter pile1

[Link](999);
std::cout << "Après [Link](999) :" << std::endl;
std::cout << "Pile 1 : ";
[Link]();
std::cout << "Pile 2 : ";
[Link]();

// Test 4 : Opérateur d'affectation

std::cout << "\nTest 4 : Opérateur d'affectation" << std::endl;
PileChainee<int> pile3;
[Link](1);
[Link](2);
std::cout << "Pile 3 avant : ";
[Link]();

pile3 = pile1; // Affectation

std::cout << "Pile 3 après affectation : ";
[Link]();

// Test 5 : Pile de strings

std::cout << "\nTest 5 : Pile de strings" << std::endl;
PileChainee<std::string> pile_str;
pile_str.push("Premier");
pile_str.push("Deuxième");
pile_str.push("Troisième");
pile_str.afficher();

// Test 6 : Sous-dépassement
std::cout << "\nTest 6 : Test de sous-dépassement" << std::endl;
PileChainee<int> pile_vide;
pile_vide.pop(); // Lance une exception
 } catch (const std::underflow_error& e) {
std::cout << "Exception : " << [Link]() << std::endl;
}

return 0;
}

Sortie attendue :

=== Test Pile Chaînée C++ ===

Pile chaînée créée

Test 1 : Opérations de base
Pile (sommet -> fond) : 300 200 100
Taille : 3

Test 2 : Consultation et dépilage

Sommet : 300
Dépilé : 300
Pile (sommet -> fond) : 200 100

Test 3 : Constructeur de copie

Pile 1 : Pile (sommet -> fond) : 200 100
Pile 2 (copie) : Pile (sommet -> fond) : 200 100
Après [Link](999) :
Pile 1 : Pile (sommet -> fond) : 200 100
Pile 2 : Pile (sommet -> fond) : 999 200 100

Test 4 : Opérateur d'affectation

Pile chaînée créée
Pile 3 avant : Pile (sommet -> fond) : 2 1
Pile 3 après affectation : Pile (sommet -> fond) : 200 100

Test 5 : Pile de strings

Pile chaînée créée
Pile (sommet -> fond) : Troisième Deuxième Premier

Test 6 : Test de sous-dépassement

Pile chaînée créée
Exception : Pile vide : impossible de dépiler
Pile chaînée détruite
Pile chaînée détruite
Pile chaînée détruite
Pile chaînée détruite

6.3 Tableau Comparatif C vs C++

Aspect C (Procédural) C++ (Orienté Objet)

Définition struct + fonctions séparées class avec méthodes

Création Pile p; initialiser(&p); PileContigue<int> p(100);

Opérations push(&p, val) [Link](val)

Gestion mémoire Manuelle ( malloc / free ) Semi-automatique ( new / delete + destructeur)

Erreurs Codes de retour Exceptions

 Aspect C (Procédural) C++ (Orienté Objet)

Généricité Macros ou void* Templates

Encapsulation Aucune (tout public) Public/Private

Copie Manuelle (fonction spéciale) Constructeur de copie

Sécurité Faible (pointeurs nus) Moyenne (RAII, exceptions)

7. Applications Avancées et Algorithmes avec Piles

7.1 Vérification de Parenthèses Équilibrées

Problème Formel
Entrée : Une chaîne contenant des caractères ( , ) , [ , ] , { , }

Sortie : VRAI si les parenthèses sont équilibrées, FAUX sinon

Définition mathématique de "équilibré" :

1. Chaque parenthèse ouvrante a une fermante correspondante

2. Les paires sont correctement imbriquées
3. L'ordre de fermeture respecte l'ordre d'ouverture (LIFO)

Exemples :

VALIDES :
- "()" → Paire simple
- "([{}])" → Imbrication correcte
- "{[()()]}" → Imbrication multiple
- "" → Chaîne vide (valide par convention)

INVALIDES :
- "(()" → Manque une fermante
- "())" → Trop de fermantes
- "([)]" → Mauvais ordre d'imbrication
- "}{" → Commence par fermante

Algorithme avec Pile

Idée clé : Utiliser la pile pour "mémoriser" les parenthèses ouvrantes en attente de fermeture.

Pseudocode détaillé :
 ALGORITHME VerifierParentheses(chaine)
ENTRÉE : chaine de caractères
SORTIE : VRAI si équilibré, FAUX sinon

DÉBUT
Créer une pile P vide

POUR chaque caractère c dans chaine FAIRE

SI c est une ouvrante ('(', '[', '{') ALORS
// Mémoriser cette ouvrante
PUSH(P, c)

SINON SI c est une fermante (')', ']', '}') ALORS

// Vérifier correspondance
SI P est vide ALORS
// Fermante sans ouvrante correspondante
Retourner FAUX
FIN SI

ouvrante ← POP(P)

SI ouvrante et c ne correspondent pas ALORS

// Exemple : '(' avec ']'
Retourner FAUX
FIN SI
FIN SI
FIN POUR

// À la fin, la pile doit être vide

SI P est vide ALORS
Retourner VRAI
SINON
Retourner FAUX // Il reste des ouvrantes
FIN SI
FIN

Trace d'Exécution Complète

Exemple 1 : Expression valide "([{}])"

Caractère | Action | État de la pile | Explication

----------|-----------------|-----------------|-------------
( | PUSH('(') | ( | Ouvrante
[ | PUSH('[') | ( [ | Ouvrante
{ | PUSH('{') | ( [ { | Ouvrante
} | POP, correspond | ( [ | '{' et '}' correspondent
] | POP, correspond | ( | '[' et ']' correspondent
) | POP, correspond | [vide] | '(' et ')' correspondent

Pile finale : vide → VALIDE ✓

Exemple 2 : Expression invalide "([)]"

 Caractère | Action | État de la pile | Explication
----------|-----------------|-----------------|-------------
( | PUSH('(') | ( | Ouvrante
[ | PUSH('[') | ( [ | Ouvrante
) | POP → '[' | ( | ERREUR : '[' ne correspond pas à ')'

Retour immédiat : INVALIDE ✗

Exemple 3 : Expression invalide "(("

Caractère | Action | État de la pile | Explication

----------|-----------------|-----------------|-------------
( | PUSH('(') | ( | Ouvrante
( | PUSH('(') | ( ( | Ouvrante

Fin de chaîne
Pile finale : ( ( → NON VIDE → INVALIDE ✗

Implémentation en C++
#include <iostream>
#include <string>
#include <stack> // Pile de la STL

/**
* Vérifie si un caractère est une parenthèse ouvrante
*/
bool estOuvrante(char c) {
return (c == '(' || c == '[' || c == '{');
}

/**
* Vérifie si un caractère est une parenthèse fermante
*/
bool estFermante(char c) {
return (c == ')' || c == ']' || c == '}');
}

/**
* Vérifie si deux parenthèses correspondent
*/
bool correspondent(char ouvrante, char fermante) {
return (ouvrante == '(' && fermante == ')') ||
(ouvrante == '[' && fermante == ']') ||
(ouvrante == '{' && fermante == '}');
}

/**
* Vérifie si les parenthèses sont équilibrées
* Complexité : O(n) où n est la longueur de la chaîne
* Espace : O(n) dans le pire cas (toutes ouvrantes)
*/
bool verifierParentheses(const std::string& expression) {
std::stack<char> pile;

for (char c : expression) {

if (estOuvrante(c)) {
// Empiler les ouvrantes
[Link](c);

} else if (estFermante(c)) {
// Vérifier les fermantes
if ([Link]()) {
return false; // Fermante sans ouvrante
}

char ouvrante = [Link]();

[Link]();

if (!correspondent(ouvrante, c)) {
return false; // Mauvaise correspondance
}
}
// Ignorer les autres caractères
}

// Vérifier que toutes les ouvrantes ont été fermées

return [Link]();
}
 int main() {
// Tests
std::string tests[] = {
"()",
"([])",
"([{}])",
"(()",
"())",
"([)]",
"{[()()]}",
"}{"
};

std::cout << "=== Test de Vérification de Parenthèses ===" << std::endl;

for (const std::string& test : tests) {

bool resultat = verifierParentheses(test);
std::cout << "\"" << test << "\" → "
<< (resultat ? "VALIDE ✓" : "INVALIDE ✗")
<< std::endl;
}

return 0;
}

Sortie :

=== Test de Vérification de Parenthèses ===

"()" → VALIDE ✓
"([])" → VALIDE ✓
"([{}])" → VALIDE ✓
"(()" → INVALIDE ✗
"())" → INVALIDE ✗
"([)]" → INVALIDE ✗
"{[()()]}" → VALIDE ✓
"}{" → INVALIDE ✗

Analyse de Complexité
Complexité temporelle :
T (n) = O(n)

Justification :

• Une seule passe sur la chaîne : O(n)

• Chaque PUSH/POP est en O(1)
• Au plus n opérations sur la pile

Complexité spatiale :
S(n) = O(n)

Pire cas : Toutes les parenthèses sont ouvrantes → pile contient n éléments

7.2 Conversion Infixe vers Postfixe (Notation Polonaise Inverse)

Motivation
Les humains écrivent : 3 + 5 * 2 (notation infixe)
Les machines préfèrent : 3 5 2 * + (notation postfixe ou RPN)

Pourquoi postfixe ?

1. Pas de parenthèses nécessaires : L'ordre est explicite

2. Évaluation simple : Une seule passe avec une pile
3. Utilisé par : Calculatrices HP, compilateurs (code intermédiaire), JVM

Notations Comparées

Infixe Préfixe Postfixe Arbre

3 + 5 + 3 5 3 5 + <br> +<br> / \<br>3 5<br>

3 + 5 * 2 + 3 * 5 2 3 5 2 * + <br> +<br> / \<br> 3 *<br> / \<br> 5 2<br>

(3 + 5) * 2 * + 3 5 2 3 5 + 2 * <br> *<br> / \<br> + 2<br> / \<br> 3 5<br>

Algorithme de Shunting Yard (Dijkstra)

Idée clé : Utiliser deux structures :

1. Pile d'opérateurs : Pour mémoriser les opérateurs en attente

2. File de sortie : Pour construire l'expression postfixe

Règles de priorité :
Prioritˊe : ∗ / > +− > (

Pseudocode :
 ALGORITHME InfixeVersPostfixe(expression)
ENTRÉE : Expression infixe (string)
SORTIE : Expression postfixe (string)

DÉBUT
Créer une pile P pour les opérateurs
Créer une chaîne sortie vide

POUR chaque symbole s dans expression FAIRE

CAS s :
EST_OPERANDE (nombre) :
Ajouter s à sortie

EST_PARENTHESE_OUVRANTE '(' :
PUSH(P, s)

EST_PARENTHESE_FERMANTE ')' :
TANT QUE sommet(P) ≠ '(' FAIRE
Ajouter POP(P) à sortie
FIN TANT QUE
POP(P) // Retirer '('

EST_OPERATEUR (+, -, *, /) :
TANT QUE P non vide ET
priorité(sommet(P)) >= priorité(s) FAIRE
Ajouter POP(P) à sortie
FIN TANT QUE
PUSH(P, s)
FIN CAS
FIN POUR

// Vider la pile restante

TANT QUE P non vide FAIRE
Ajouter POP(P) à sortie
FIN TANT QUE

Retourner sortie
FIN

Trace d'Exécution : "3 + 5 * 2"

Symbole | Action | Pile | Sortie

--------|---------------------|-----------|--------
3 | Ajouter à sortie | [vide] | 3
+ | PUSH | + | 3
5 | Ajouter à sortie | + | 3 5
* | PUSH (* > +) | + * | 3 5
2 | Ajouter à sortie | + * | 3 5 2
FIN | Vider pile | [vide] | 3 5 2 * +

Résultat : "3 5 2 * +"

Vérification :
 Évaluation de "3 5 2 * +" :
3 → Pile : [3]
5 → Pile : [3, 5]
2 → Pile : [3, 5, 2]
* → Pop 2, Pop 5, Push (5*2=10) → Pile : [3, 10]
+ → Pop 10, Pop 3, Push (3+10=13) → Pile : [13]

Résultat : 13 ✓

Trace d'Exécution : "(3 + 5) * 2"

Symbole | Action | Pile | Sortie

--------|---------------------|-----------|--------
( | PUSH | ( |
3 | Ajouter à sortie | ( | 3
+ | PUSH | ( + | 3
5 | Ajouter à sortie | ( + | 3 5
) | Dépiler jusqu'à '(' | [vide] | 3 5 +
* | PUSH | * | 3 5 +
2 | Ajouter à sortie | * | 3 5 + 2
FIN | Vider pile | [vide] | 3 5 + 2 *

Résultat : "3 5 + 2 *"

Vérification :

Évaluation de "3 5 + 2 *" :

3 → [3]
5 → [3, 5]
+ → [8]
2 → [8, 2]
* → [16]

Résultat : 16 ✓

Implémentation en C++
#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <map>

/**
* Retourne la priorité d'un opérateur
*/
int priorite(char op) {
static std::map<char, int> priorites = {
{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2}
};
return priorites[op];
}

/**
* Vérifie si un caractère est un opérateur
*/
bool estOperateur(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}

/**
* Convertit une expression infixe en postfixe
* Complexité : O(n) où n est la longueur de l'expression
* Espace : O(n) pour la pile
*/
std::string infixeVersPostfixe(const std::string& expression) {
std::stack<char> pile;
std::string sortie = "";

for (char c : expression) {

// Ignorer les espaces
if (c == ' ') continue;

if (std::isdigit(c)) {
// Opérande : ajouter à la sortie
sortie += c;
sortie += ' ';

} else if (c == '(') {
// Parenthèse ouvrante : empiler
[Link](c);

} else if (c == ')') {
// Parenthèse fermante : dépiler jusqu'à '('
while (![Link]() && [Link]() != '(') {
sortie += [Link]();
sortie += ' ';
[Link]();
}
[Link](); // Retirer '('

} else if (estOperateur(c)) {
// Opérateur : dépiler selon priorité
while (![Link]() &&
 [Link]() != '(' &&
priorite([Link]()) >= priorite(c)) {
sortie += [Link]();
sortie += ' ';
[Link]();
}
[Link](c);
}
}

// Vider la pile restante

while (![Link]()) {
sortie += [Link]();
sortie += ' ';
[Link]();
}

return sortie;
}

int main() {
std::string expressions[] = {
"3 + 5",
"3 + 5 * 2",
"(3 + 5) * 2",
"3 * 5 + 2",
"3 * (5 + 2)",
"((3 + 5) * 2) / 4"
};

std::cout << "=== Conversion Infixe → Postfixe ===" << std::endl;

for (const std::string& expr : expressions) {

std::string postfixe = infixeVersPostfixe(expr);
std::cout << "Infixe : " << expr << std::endl;
std::cout << "Postfixe: " << postfixe << std::endl << std::endl;
}

return 0;
}

Sortie :
 === Conversion Infixe → Postfixe ===
Infixe : 3 + 5
Postfixe: 3 5 +

Infixe : 3 + 5 * 2
Postfixe: 3 5 2 * +

Infixe : (3 + 5) * 2
Postfixe: 3 5 + 2 *

Infixe : 3 * 5 + 2
Postfixe: 3 5 * 2 +

Infixe : 3 * (5 + 2)
Postfixe: 3 5 2 + *

Infixe : ((3 + 5) * 2) / 4
Postfixe: 3 5 + 2 * 4 /

7.3 Évaluation d'Expression Postfixe

Algorithme
Idée : Utiliser une pile pour mémoriser les opérandes.

Pseudocode :

ALGORITHME EvaluerPostfixe(expression)
ENTRÉE : Expression postfixe (string)
SORTIE : Résultat (nombre)

DÉBUT
Créer une pile P de nombres

POUR chaque symbole s dans expression FAIRE

SI s est un nombre ALORS
PUSH(P, s)
SINON SI s est un opérateur ALORS
operande2 ← POP(P)
operande1 ← POP(P)
resultat ← appliquer(operande1, s, operande2)
PUSH(P, resultat)
FIN SI
FIN POUR

// À la fin, la pile contient le résultat

Retourner POP(P)
FIN

Note importante : L'ordre des opérandes est crucial !

Pour "3 5 -" :

operande2 = 5 (dépilé en premier)
operande1 = 3 (dépilé en second)
Calcul : 3 - 5 = -2 (pas 5 - 3)
Trace d'Exécution Complète : "3 5 2 * +"

Symbole | Action | Pile | Explication

--------|---------------------|-----------------|-------------
3 | PUSH(3) | [3] | Opérande
5 | PUSH(5) | [3, 5] | Opérande
2 | PUSH(2) | [3, 5, 2] | Opérande
* | POP(2), POP(5) | [3] | 5 * 2 = 10
| PUSH(10) | [3, 10] |
+ | POP(10), POP(3) | [] | 3 + 10 = 13
| PUSH(13) | [13] |
FIN | POP() | [] | Résultat = 13

Résultat final : 13 ✓

Visualisation détaillée de l'opérateur * :

État avant * :
┌────┐
│ 2 │ ← sommet (operande2)
├────┤
│ 5 │ ← (operande1)
├────┤
│ 3 │
└────┘

Étape 1 : operande2 = POP() = 2

┌────┐
│ 5 │ ← sommet
├────┤
│ 3 │
└────┘

Étape 2 : operande1 = POP() = 5

┌────┐
│ 3 │ ← sommet
└────┘

Étape 3 : resultat = 5 * 2 = 10
Étape 4 : PUSH(10)
┌────┐
│ 10 │ ← sommet
├────┤
│ 3 │
└────┘

Trace d'Exécution : "3 5 + 2 *" (équivaut à (3+5)*2 )

Symbole | Action | Pile | Calcul

--------|---------------------|-----------------|--------
3 | PUSH(3) | [3] |
5 | PUSH(5) | [3, 5] |
+ | POP(5), POP(3) | [] | 3 + 5 = 8
| PUSH(8) | [8] |
2 | PUSH(2) | [8, 2] |
* | POP(2), POP(8) | [] | 8 * 2 = 16
| PUSH(16) | [16] |
FIN | POP() | [] | Résultat = 16 ✓
Implémentation en C++
#include <iostream>
#include <string>
#include <stack>
#include <sstream>
#include <cctype>

/**
* Applique un opérateur à deux opérandes
*/
int appliquerOperateur(int operande1, char op, int operande2) {
switch (op) {
case '+': return operande1 + operande2;
case '-': return operande1 - operande2;
case '*': return operande1 * operande2;
case '/':
if (operande2 == 0) {
throw std::runtime_error("Division par zéro");
}
return operande1 / operande2;
default:
throw std::invalid_argument("Opérateur inconnu");
}
}

/**
* Évalue une expression postfixe
* Complexité : O(n) où n est le nombre de symboles
* Espace : O(n) dans le pire cas (tous les symboles sont des opérandes)
*/
int evaluerPostfixe(const std::string& expression) {
std::stack<int> pile;
std::istringstream iss(expression);
std::string symbole;

while (iss >> symbole) {

// Vérifier si c'est un nombre
if (std::isdigit(symbole[0]) ||
([Link]() > 1 && symbole[0] == '-')) {
// Convertir en entier et empiler
[Link](std::stoi(symbole));

} else if ([Link]() == 1 &&

(symbole[0] == '+' || symbole[0] == '-' ||
symbole[0] == '*' || symbole[0] == '/')) {
// C'est un opérateur
if ([Link]() < 2) {
throw std::runtime_error("Expression invalide : pas assez d'opérandes");
}

// IMPORTANT : ordre des opérandes !

int operande2 = [Link](); [Link]();
int operande1 = [Link](); [Link]();

int resultat = appliquerOperateur(operande1, symbole[0], operande2);

[Link](resultat);
}
}

if ([Link]() != 1) {
throw std::runtime_error("Expression invalide : résultat incorrect");
 }

return [Link]();
}

int main() {
std::string expressions[] = {
"3 5 +", // 3 + 5 = 8
"3 5 2 * +", // 3 + (5 * 2) = 13
"3 5 + 2 *", // (3 + 5) * 2 = 16
"15 7 1 1 + - / 3 * 2 1 1 + + -" // Complexe
};

std::cout << "=== Évaluation d'Expressions Postfixe ===" << std::endl;

for (const std::string& expr : expressions) {

try {
int resultat = evaluerPostfixe(expr);
std::cout << "Expression : " << expr << std::endl;
std::cout << "Résultat : " << resultat << std::endl << std::endl;
} catch (const std::exception& e) {
std::cout << "Erreur : " << [Link]() << std::endl;
}
}

return 0;
}

Sortie :

=== Évaluation d'Expressions Postfixe ===

Expression : 3 5 +
Résultat : 8

Expression : 3 5 2 * +
Résultat : 13

Expression : 3 5 + 2 *
Résultat : 16

Expression : 15 7 1 1 + - / 3 * 2 1 1 + + -
Résultat : 5

Analyse de Complexité
Complexité temporelle :

T (n) = O(n)

Justification :

• Une seule passe sur l'expression : O(n)

• Chaque symbole traité une fois
• Chaque PUSH/POP est O(1)

Complexité spatiale :

S(n) = O(n)

Pire cas : Expression avec tous des opérandes suivis d'opérateurs

Exemple : "1 2 3 4 5 + + + +" → pile contient jusqu'à 5 éléments

Comparaison avec évaluation infixe :

Infixe : Nécessite analyse de précédence → O(n) mais plus complexe

Postfixe: Une seule passe simple → O(n) plus efficace

7.4 Parcours en Profondeur (DFS) avec Pile

Problème : Explorer un Graphe
Définition mathématique d'un graphe :

G = (V , E)

où :

• V = ensemble de sommets (vertices)

• E ⊆ V × V = ensemble d'arêtes (edges)

Exemple de graphe :

A
/|\
B C D
| |
E F

V = {A, B, C, D, E, F}
E = {(A,B), (A,C), (A,D), (B,E), (D,F)}

Parcours en Profondeur (DFS - Depth-First Search)

Principe : Explorer le plus profondément possible avant de revenir en arrière.

Stratégie avec pile :

1. Empiler le sommet de départ

2. Tant que la pile n'est pas vide :
• Dépiler un sommet
• Le marquer comme visité
• Empiler tous ses voisins non visités

Pseudocode :
 ALGORITHME DFS_Iteratif(graphe, depart)
ENTRÉE : Graphe G, sommet de départ s
SORTIE : Ordre de visite des sommets

DÉBUT
Créer une pile P
Créer un tableau visite[] initialisé à FAUX

PUSH(P, depart)

TANT QUE P non vide FAIRE

sommet ← POP(P)

SI visite[sommet] = FAUX ALORS

visite[sommet] ← VRAI
Afficher sommet

POUR chaque voisin v de sommet FAIRE

SI visite[v] = FAUX ALORS
PUSH(P, v)
FIN SI
FIN POUR
FIN SI
FIN TANT QUE
FIN

Trace d'Exécution sur le Graphe Exemple

Graphe :
A
/|\
B C D
| |
E F

Adjacences :
A → [B, C, D]
B → [E]
C → []
D → [F]
E → []
F → []

Exécution DFS depuis A :

 Étape | Action | Pile | Visité | Affichage
------|----------------|-------------|-------------|----------
1 | PUSH(A) | [A] | {} |
2 | POP(A) | [] | {A} | A
3 | PUSH(B,C,D) | [B,C,D] | {A} |
4 | POP(D) | [B,C] | {A,D} | D
5 | PUSH(F) | [B,C,F] | {A,D} |
6 | POP(F) | [B,C] | {A,D,F} | F
7 | POP(C) | [B] | {A,D,F,C} | C
8 | POP(B) | [] | {A,D,F,C,B} | B
9 | PUSH(E) | [E] | {A,D,F,C,B} |
10 | POP(E) | [] | {A,D,F,C,B,E}| E

Ordre de visite : A → D → F → C → B → E

Visualisation de la pile au fil du temps :

Temps 1 : Temps 3 : Temps 5 : Temps 7 :

┌───┐ ┌───┐ ┌───┐ ┌───┐
│ A │ │ D │ │ F │ │ C │
└───┘ ├───┤ ├───┤ ├───┤
│ C │ │ C │ │ B │
├───┤ ├───┤ └───┘
│ B │ │ B │
└───┘ └───┘

Implémentation en C++
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

/**
* Classe représentant un graphe non orienté
*/
class Graphe {
private:
int nbSommets;
std::vector<std::vector<int>> adjacence;

public:
Graphe(int n) : nbSommets(n) {
[Link](n);
}

void ajouterArete(int u, int v) {

adjacence[u].push_back(v);
adjacence[v].push_back(u); // Non orienté
}

/**
* Parcours en profondeur itératif avec pile
* Complexité : O(V + E) où V = sommets, E = arêtes
* Espace : O(V) pour la pile et le tableau de visite
*/
void DFS_Iteratif(int depart) {
std::stack<int> pile;
std::unordered_set<int> visite;

[Link](depart);

std::cout << "Ordre de visite DFS : ";

while (![Link]()) {
int sommet = [Link]();
[Link]();

if ([Link](sommet) == [Link]()) {
// Marquer comme visité
[Link](sommet);
std::cout << sommet << " ";

// Empiler tous les voisins non visités

for (int voisin : adjacence[sommet]) {
if ([Link](voisin) == [Link]()) {
[Link](voisin);
}
}
}
}

std::cout << std::endl;

}

/**
* Pour comparaison : DFS récursif
* Complexité : O(V + E)
 * Espace : O(V) pour la pile d'appels (récursion)
*/
void DFS_Recursif(int sommet, std::unordered_set<int>& visite) {
[Link](sommet);
std::cout << sommet << " ";

for (int voisin : adjacence[sommet]) {

if ([Link](voisin) == [Link]()) {
DFS_Recursif(voisin, visite);
}
}
}

void lancerDFS_Recursif(int depart) {

std::unordered_set<int> visite;
std::cout << "Ordre de visite DFS (récursif) : ";
DFS_Recursif(depart, visite);
std::cout << std::endl;
}
};

int main() {
// Créer le graphe exemple
Graphe g(6); // Sommets 0-5 représentent A-F

// Ajouter les arêtes

[Link](0, 1); // A-B
[Link](0, 2); // A-C
[Link](0, 3); // A-D
[Link](1, 4); // B-E
[Link](3, 5); // D-F

std::cout << "=== Parcours en Profondeur (DFS) ===" << std::endl;

std::cout << "\nGraphe :" << std::endl;
std::cout << " 0(A)" << std::endl;
std::cout << " /|\\ " << std::endl;
std::cout << " 1 2 3 (B C D)" << std::endl;
std::cout << " | | " << std::endl;
std::cout << " 4 5 (E F)" << std::endl << std::endl;

// Version itérative (avec pile explicite)

g.DFS_Iteratif(0);

// Version récursive (avec pile d'appels implicite)

g.lancerDFS_Recursif(0);

return 0;
}

Sortie :
 === Parcours en Profondeur (DFS) ===

Graphe :
0(A)
/|\
1 2 3 (B C D)
| |
4 5 (E F)

Ordre de visite DFS : 0 3 5 2 1 4

Ordre de visite DFS (récursif) : 0 1 4 2 3 5

Note : L'ordre peut varier selon l'ordre d'insertion des voisins.

Comparaison DFS Itératif vs Récursif

Aspect Itératif (Pile Explicite) Récursif (Pile Implicite)

Pile utilisée std::stack<int> Pile d'appels système

Contrôle Manuel, visible Automatique

Débordement Contrôlable Risque de stack overflow

Lisibilité Moins naturelle Plus intuitive

Performance Légèrement plus rapide Overhead d'appels

Espace O(V) O(V)

7.5 Simulation de la Pile d'Appels de Fonctions

Problème : Comprendre l'Exécution Récursive
Quand une fonction s'appelle récusivement, le système utilise une pile d'appels pour :

1. Sauvegarder les variables locales

2. Mémoriser l'adresse de retour
3. Préserver le contexte d'exécution

Exemple : Factorielle Récursive

int factorielle(int n) {
if (n <= 1) return 1;
return n * factorielle(n - 1);
}

Simulation Manuelle avec une Pile

Structure d'un cadre d'activation (activation record) :

┌─────────────────────────┐
│ Paramètres : n │
│ Variables locales │
│ Adresse de retour │
│ Valeur de retour │
└─────────────────────────┘
Trace de factorielle(4) :
Étape 1 : Appel factorielle(4)
┌─────────────────┐
│ n = 4 │
│ retour = ? │
└─────────────────┘

Étape 2 : Appel factorielle(3)

┌─────────────────┐
│ n = 3 │ ← Sommet
│ retour = ? │
├─────────────────┤
│ n = 4 │
│ retour = ? │
└─────────────────┘

Étape 3 : Appel factorielle(2)

┌─────────────────┐
│ n = 2 │ ← Sommet
│ retour = ? │
├─────────────────┤
│ n = 3 │
│ retour = ? │
├─────────────────┤
│ n = 4 │
│ retour = ? │
└─────────────────┘

Étape 4 : Appel factorielle(1)

┌─────────────────┐
│ n = 1 │ ← Sommet
│ retour = ? │
├─────────────────┤
│ n = 2 │
│ retour = ? │
├─────────────────┤
│ n = 3 │
│ retour = ? │
├─────────────────┤
│ n = 4 │
│ retour = ? │
└─────────────────┘

Étape 5 : Retour 1 (cas de base)

┌─────────────────┐
│ n = 2 │ ← Sommet
│ retour = ? │
├─────────────────┤
│ n = 3 │
│ retour = ? │
├─────────────────┤
│ n = 4 │
│ retour = ? │
└─────────────────┘
Calcul : 2 * 1 = 2

Étape 6 : Retour 2
┌─────────────────┐
│ n = 3 │ ← Sommet
│ retour = ? │
├─────────────────┤
 │ n = 4 │
│ retour = ? │
└─────────────────┘
Calcul : 3 * 2 = 6

Étape 7 : Retour 6
┌─────────────────┐
│ n = 4 │ ← Sommet
│ retour = ? │
└─────────────────┘
Calcul : 4 * 6 = 24

Étape 8 : Retour 24
┌─────────────────┐
│ [vide] │
└─────────────────┘
Résultat final : 24

Conversion Récursion → Itération avec Pile

Principe : Simuler explicitement la pile d'appels.
#include <iostream>
#include <stack>

// Structure représentant un cadre d'activation

struct CadreFactorielle {
int n;
int resultat;
bool calculEnCours;

CadreFactorielle(int val) : n(val), resultat(0), calculEnCours(true) {}

};

/**
* Calcul de factorielle de manière itérative avec pile
* Simule la récursion
* Complexité : O(n) temps, O(n) espace
*/
int factorielleIteratif(int n) {
std::stack<CadreFactorielle> pile;
[Link](CadreFactorielle(n));

int resultatFinal = 1;

while (![Link]()) {
CadreFactorielle& cadre = [Link]();

if (cadre.n <= 1) {
// Cas de base
[Link] = 1;
[Link] = false;
resultatFinal = [Link];
[Link]();

} else if ([Link]) {
// Premier passage : "descente"
[Link] = false;
[Link](CadreFactorielle(cadre.n - 1));

} else {
// Deuxième passage : "remontée"
[Link] = cadre.n * resultatFinal;
resultatFinal = [Link];
[Link]();
}
}

return resultatFinal;
}

/**
* Version récursive classique pour comparaison
*/
int factorielleRecursif(int n) {
if (n <= 1) return 1;
return n * factorielleRecursif(n - 1);
}

int main() {
std::cout << "=== Calcul de Factorielle ===" << std::endl;
 for (int i = 0; i <= 10; i++) {
int res1 = factorielleIteratif(i);
int res2 = factorielleRecursif(i);

std::cout << i << "! = " << res1 << " (itératif) = "
<< res2 << " (récursif)" << std::endl;
}

return 0;
}

Sortie :

=== Calcul de Factorielle ===

0! = 1 (itératif) = 1 (récursif)
1! = 1 (itératif) = 1 (récursif)
2! = 2 (itératif) = 2 (récursif)
3! = 6 (itératif) = 6 (récursif)
4! = 24 (itératif) = 24 (récursif)
5! = 120 (itératif) = 120 (récursif)
6! = 720 (itératif) = 720 (récursif)
7! = 5040 (itératif) = 5040 (récursif)
8! = 40320 (itératif) = 40320 (récursif)
9! = 362880 (itératif) = 362880 (récursif)
10! = 3628800 (itératif) = 3628800 (récursif)

8. Analyse Comparative et Choix d'Implémentation

8.1 Tableau Récapitulatif des Complexités

Opération Contiguë Chaînée

Initialisation O(1) O(1)

Push O(1)* O(1)

Pop O(1) O(1)

Top/Sommet O(1) O(1)

EstVide O(1) O(1)

EstPleine O(1) N/A

Taille O(1) O(1)**

Destruction O(1) O(n)

* : Amortie si redimensionnement dynamique

** : Si compteur maintenu

8.2 Consommation Mémoire

Pour une pile de n éléments (int = 4 octets, pointeur = 8 octets) :

Pile Contiguë (capacité C) :

Mcontiguë = C × 4 + O(1) octets

Pile Chaînée (n éléments) :

Mchaı̂nˊee = n × (4 + 8) + O(1) = 12n + O(1) octets

Graphique de comparaison :

Mémoire (octets)
│
2000│ ╱ Chaînée
│ ╱
1500│ ╱
│ ╱
1000│ ╱
│ ╱
500│ ╱─────────────────────── Contiguë (cap=100)
│╱
0└──────────────────────────> n (nombre d'éléments)
0 25 50 75 100

Observation :

• Contiguë : coût fixe, indépendant de n (si n ≤ capacité)

• Chaînée : coût proportionnel à n

8.3 Critères de Choix

Utilisez une pile CONTIGUË si :

• ✓ Taille maximale connue à l'avance

• ✓ Performance critique (accès mémoire rapide)
• ✓ Environnement à mémoire limitée
• ✓ Pas besoin de redimensionnement fréquent

Utilisez une pile CHAÎNÉE si :

• ✓ Taille imprévisible ou très variable

• ✓ Pas de contrainte sur la capacité
• ✓ Insertions/suppressions dans d'autres structures
• ✓ Besoin de partager des nœuds

Tableau de décision :

Contexte | Recommandation
--------------------------------|----------------
Calculatrice RPN (taille ≤ 100) | Contiguë
Historique navigateur (illimité)| Chaînée
Pile d'appels système | Contiguë
Parser XML/JSON (profond) | Chaînée
Évaluation d'expressions | Contiguë
DFS sur grand graphe | Chaînée

9. Extensions et Variantes de la Pile

9.1 Pile avec Minimum en O(1)

Problème : Implémenter une pile qui supporte getMin() en temps constant.

Solution : Utiliser une pile auxiliaire pour mémoriser les minimums.

Structure :

Pile principale Pile des minimums

┌────┐ ┌────┐
│ 3 │ ← sommet │ 1 │ ← min actuel
├────┤ ├────┤
│ 5 │ │ 1 │
├────┤ ├────┤
│ 1 │ │ 1 │
├────┤ ├────┤
│ 7 │ │ 7 │
└────┘ └────┘

Implémentation C++ :
class PileAvecMin {
private:
std::stack<int> pile;
std::stack<int> mins;

public:
void push(int valeur) {
[Link](valeur);

// Mettre à jour le minimum

if ([Link]() || valeur <= [Link]()) {
[Link](valeur);
} else {
[Link]([Link]());
}
}

void pop() {
if ([Link]()) {
throw std::underflow_error("Pile vide");
}
[Link]();
[Link]();
}

int top() const {

if ([Link]()) {
throw std::underflow_error("Pile vide");
}
return [Link]();
}

int getMin() const {

if ([Link]()) {
throw std::underflow_error("Pile vide");
}
return [Link]();
}

bool estVide() const {

return [Link]();
}
};

int main() {
PileAvecMin p;

[Link](7);
std::cout << "Min après push(7) : " << [Link]() << std::endl; // 7

[Link](1);
std::cout << "Min après push(1) : " << [Link]() << std::endl; // 1

[Link](5);
std::cout << "Min après push(5) : " << [Link]() << std::endl; // 1

[Link](3);
std::cout << "Min après push(3) : " << [Link]() << std::endl; // 1

[Link]();
 std::cout << "Min après pop() : " << [Link]() << std::endl; // 1

[Link]();
std::cout << "Min après pop() : " << [Link]() << std::endl; // 1

[Link]();
std::cout << "Min après pop() : " << [Link]() << std::endl; // 7

return 0;
}

Complexité :

• push() : O(1)
• pop() : O(1)
• getMin() : O(1)
• Espace : O(n) pour la pile auxiliaire

9.2 Pile avec Capacité Dynamique (Auto-redimensionnement)

Problème : Éviter le débordement en augmentant automatiquement la capacité.

Stratégie : Doubler la capacité quand elle est atteinte.

template <typename T>
class PileDynamique {
private:
T* elements;
int sommet;
int capacite;

void redimensionner() {
int nouvelleCapacite = capacite * 2;
T* nouveauTableau = new T[nouvelleCapacite];

// Copier les éléments

for (int i = 0; i <= sommet; i++) {
nouveauTableau[i] = elements[i];
}

delete[] elements;
elements = nouveauTableau;
capacite = nouvelleCapacite;

std::cout << "Redimensionnement : " << capacite/2

<< " → " << capacite << std::endl;
}

public:
PileDynamique(int cap = 2) : capacite(cap), sommet(-1) {
elements = new T[capacite];
}

~PileDynamique() {
delete[] elements;
}

void push(const T& valeur) {

if (sommet == capacite - 1) {
redimensionner();
}
elements[++sommet] = valeur;
}

T pop() {
if (sommet < 0) {
throw std::underflow_error("Pile vide");
}
return elements[sommet--];
}

bool estVide() const {

return sommet < 0;
}

int taille() const {

return sommet + 1;
}
};

int main() {
PileDynamique<int> pile(2); // Capacité initiale : 2

for (int i = 1; i <= 10; i++) {

 [Link](i);
std::cout << "Push(" << i << "), taille = " << [Link]() << std::endl;
}

return 0;
}

Sortie :

Push(1), taille = 1
Push(2), taille = 2
Redimensionnement : 2 → 4
Push(3), taille = 3
Push(4), taille = 4
Redimensionnement : 4 → 8
Push(5), taille = 5
Push(6), taille = 6
Push(7), taille = 7
Push(8), taille = 8
Redimensionnement : 8 → 16
Push(9), taille = 9
Push(10), taille = 10

Analyse de complexité amortie :

Coût total pour n insertions = n + (2 + 4 + 8 + ... + n) < 3n

3n
Coût amorti par insertion = = O(1)
n

10. Conclusion et Perspectives

10.1 Récapitulatif des Points Clés

La pile est une structure fondamentale car :

1. Principe LIFO simple mais puissant : Naturel pour inverser, mémoriser temporairement
2. Efficacité optimale : Toutes les opérations en O(1)
3. Utilisée partout :
• Systèmes d'exploitation (pile d'appels)
• Compilateurs (analyse syntaxique)
• Navigation web (historique)
• Éditeurs (Undo/Redo)
• Algorithmes de graphes (DFS)

Formule mathématique récapitulative :

Pile : {S, Push, Pop, Top, isEmpty}

avec ∀s ∈ S, Pop(Push(s)) = s

10.2 Relations avec d'Autres Structures

 Pile (LIFO)
│
├─ Inverse de → File (FIFO)
│
├─ Cas particulier de → Liste (accès restreint)
│
├─ Utilise → Tableau ou Liste chaînée
│
└─ Utilisée par → DFS, évaluation d'expressions, récursion

10.3 Exercices Proposés

Niveau Débutant :

1. Implémenter une pile en C sans utiliser de structure

2. Inverser une chaîne de caractères avec une pile
3. Vérifier si une séquence de push/pop est valide

Niveau Intermédiaire : 4. Implémenter une pile qui retourne le maximum en O(1) 5. Trier une pile en utilisant une pile auxiliaire 6.
Convertir une expression infixe avec parenthèses en postfixe

Niveau Avancé : 7. Implémenter deux piles dans un seul tableau 8. Créer une pile thread-safe (multi-threading) 9. Simuler une
machine à pile (stack machine) pour bytecode

10.4 Ressources pour Aller Plus Loin

Livres recommandés :

• Introduction to Algorithms (CLRS) - Chapitre 10

• Data Structures and Algorithm Analysis in C++ (Weiss)

Concepts à explorer ensuite :

• Files (FIFO)
• Listes chaînées avancées
• Arbres (qui utilisent des piles pour le parcours)
• Graphes (DFS approfondi)

Annexe A : Tableau de Correspondance C/C++

Concept C C++

Structure struct Pile class Pile<T>

Allocation malloc() new

Libération free() delete

Gestion automatique Non Destructeur

Généricité void* ou macros Templates

Erreurs Codes de retour Exceptions

Annexe B : Pile dans la STL C++

#include <stack>

// Utilisation de std::stack
std::stack<int> pile;

[Link](10); // Empiler
[Link](20);

int sommet = [Link](); // Consulter : 20

[Link](); // Dépiler

bool vide = [Link]();

size_t taille = [Link]();

Avantages de std::stack :

• Déjà testée et optimisée

• Interface propre
• Conteneur sous-jacent configurable ( deque , vector , list )

FIN DU CHAPITRE 5

Ce chapitre a couvert en profondeur la structure de données Pile, depuis les concepts fondamentaux jusqu'aux applications
avancées, avec des implémentations complètes en C et C++. La compréhension de la pile est essentielle pour aborder les
structures de données plus complexes et les algorithmes qui les utilisent.