1. La Pile (Stack)

La pile est une structure de données linéaire régie par le principe LIFO (Last In, First Out). Dans ce modèle, le dernier élément ajouté est obligatoirement le premier à être extrait. Les opérations se limitent exclusivement au sommet de la pile.

Propriétés et Performance

• Accès restreint au dernier élément inséré.
• Complexité temproelle de O(1) pour l'insretion (push) et la suppression (pop).

Exemple pratique : Validation de parenthèses

Cet algorithme vérifie si une séquence de parenthèses est correctement équilibrée.

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

bool estSequenceValide(std::string chaine) {
    std::stack<char> p;
    for (char sym : chaine) {
        if (sym == '(') {
            p.push(sym);
        } else if (sym == ')') {
            if (p.empty()) return false;
            p.pop();
        }
    }
    return p.empty();
}

# Implémentation en Python
def verifier_parentheses(s: str) -> bool:
    conteneur = []
    for caractere in s:
        if caractere == '(':
            conteneur.append(caractere)
        elif caractere == ')':
            if not conteneur:
                return False
            conteneur.pop()
    return len(conteneur) == 0

// Implémentation en Java
import java.util.Stack;

public class Validateur {
    public static boolean estCorrect(String flux) {
        Stack<Character> pile = new Stack<>();
        for (char c : flux.toCharArray()) {
            if (c == '(') pile.push(c);
            else {
                if (pile.isEmpty()) return false;
                pile.pop();
            }
        }
        return pile.isEmpty();
    }
}

2. La File (Queue)

À l'inverse de la pile, la file suit le principe FIFO (First In, First Out). L'insertion s'effectue à l'arrière (tail) et la suppression à l'avant (head), simulant une file d'attente réelle.

Applications types

• Gestion des prcoessus système (Scheduling).
• Parcours en largeur (BFS) dans les graphes ou arbres.

Exemple pratique : Parcours par niveau d'un arbre binaire

// Implémentation en C++
#include <queue>
#include <vector>

struct Noeud {
    int donnee;
    Noeud *gauche, *droite;
};

std::vector<std::vector<int>> parcoursNiveaux(Noeud* racine) {
    std::vector<std::vector<int>> resultat;
    if (!racine) return resultat;
    std::queue<Noeud*> fileAttente;
    fileAttente.push(racine);
    while (!fileAttente.empty()) {
        int nbNoeuds = fileAttente.size();
        std::vector<int> etage;
        for (int i = 0; i < nbNoeuds; ++i) {
            Noeud* courant = fileAttente.front();
            fileAttente.pop();
            etage.push_back(courant->donnee);
            if (courant->gauche) fileAttente.push(courant->gauche);
            if (courant->droite) fileAttente.push(courant->droite);
        }
        resultat.push_back(etage);
    }
    return resultat;
}

3. Le Tas (Heap)

Le tas est un arbre binaire complet utilisé pour implémenter des files de priorité. Dans un tas min, la clé de chaque nœud est inférieure ou égale aux clés de ses enfants.

Structure et Accès

Pour un élément à l'indice i dans un tableau :

• Parent : (i - 1) / 2
• Enfant gauche : 2i + 1
• Enfant droit : 2i + 2

Exemple : Extraction des K plus grands éléments

# Implémentation en Python utilisant heapq
import heapq

def extraire_k_max(nombres, k):
    return heapq.nlargest(k, nombres)

# Exemple d'usage
data = [10, 20, 5, 15, 30]
print(extraire_k_max(data, 2)) # [30, 20]

// Implémentation en Java
import java.util.*;

public class AnalyseurTas {
    public static List<Integer> obtenirTopK(int[] tab, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int val : tab) {
            minHeap.offer(val);
            if (minHeap.size() > k) minHeap.poll();
        }
        List<Integer> res = new ArrayList<>(minHeap);
        res.sort(Collections.reverseOrder());
        return res;
    }
}

4. Union-Find (Disjoint Set Union)

Cette structure gère une partition d'un ensemble en plusieurs sous-ensembles disjoints. Elle est optimisée par la compression de chemin et l'union par rang.

// Implémentation en C++ optimisée
class GestionnaireEnsembles {
    std::vector<int> parent;
public:
    GestionnaireEnsembles(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int trouver(int i) {
        if (parent[i] == i) return i;
        return parent[i] = trouver(parent[i]); // Compression de chemin
    }
    void unir(int i, int j) {
        int racineI = trouver(i);
        int racineJ = trouver(j);
        if (racineI != racineJ) parent[racineI] = racineJ;
    }
};

5. Arbre de Fenwick (Binary Indexed Tree)

L'Arbre de Fenwick permet de calculer efficacement des sommes de préfixes et de mettre à jour des éléments dans un tableau dynamique.

// Implémentation en Java
class ArbreFenwick {
    private int[] bit;

    public ArbreFenwick(int n) {
        this.bit = new int[n + 1];
    }

    public void ajouter(int index, int valeur) {
        index++; // Passage en index 1
        while (index < bit.length) {
            bit[index] += valeur;
            index += index & -index;
        }
    }

    public int sommePrefixe(int index) {
        index++;
        int somme = 0;
        while (index > 0) {
            somme += bit[index];
            index -= index & -index;
        }
        return somme;
    }
}