Les Piles

Définition et principe de fonctionnement

Une pile est une structure de données linéaire qui impose des restrictions sur l'insertion et la supprestion des éléments. Ces opérations ne sont permises qu'à une extrémité spécifique, appelée le sommet de la pile, tandis que l'autre extrémité forme la base. Le principe fondamental qui régit une pile est le LIFO (Last In, First Out), ce qui signifie que le dernier élément ajouté est le premier à être retiré.

L'ajout d'un élément dans la pile est désigné comme une emiplement (push), et la suppression comme un dépilement (pop). Ces deux opérations se produisent exclusivement au sommet de la pile.

Implémentation d'une pile dynamique

Bien qu'une pile puisse être réalisée avec un tableau ou une liste chaînée, l'approche basée sur un tableau offre généralement de meilleures performances pour les ajouts en fin de séquence, car elle évite la gestion des pointeurs liés à la liste chaînée.

Voici une implémentation possible en langage C, avec un tableau dynamique qui s'agrandit au besoin.

Fichier d'en-tête Pile.h :

typedef int TypeDonnee;

typedef struct {
    TypeDonnee* donnees;
    int sommet;
    int capacite;
} Pile;

void InitialiserPile(Pile* p);
void Empiler(Pile* p, TypeDonnee valeur);
void Depiler(Pile* p);
TypeDonnee SommetPile(Pile* p);
int TaillePile(Pile* p);
int EstVidePile(Pile* p);
void DetruirePile(Pile* p);

Fichier source Pile.c :

#include "Pile.h"
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

void InitialiserPile(Pile* p) {
    assert(p != NULL);
    p->donnees = NULL;
    p->sommet = 0;
    p->capacite = 0;
}

void Empiler(Pile* p, TypeDonnee valeur) {
    assert(p != NULL);
    if (p->capacite == p->sommet) {
        int nouvelleCapacite = (p->capacite == 0) ? 4 : p->capacite * 2;
        TypeDonnee* temp = (TypeDonnee*)realloc(p->donnees, sizeof(TypeDonnee) * nouvelleCapacite);
        if (temp == NULL) {
            perror("Échec de realloc");
            return;
        }
        p->donnees = temp;
        p->capacite = nouvelleCapacite;
    }
    p->donnees[p->sommet] = valeur;
    p->sommet++;
}

void Depiler(Pile* p) {
    assert(p != NULL);
    assert(p->sommet > 0);
    p->sommet--;
}

TypeDonnee SommetPile(Pile* p) {
    assert(p != NULL);
    assert(p->sommet > 0);
    return p->donnees[p->sommet - 1];
}

int TaillePile(Pile* p) {
    assert(p != NULL);
    return p->sommet;
}

int EstVidePile(Pile* p) {
    assert(p != NULL);
    return (p->sommet == 0) ? 1 : 0;
}

void DetruirePile(Pile* p) {
    assert(p != NULL);
    free(p->donnees);
    p->donnees = NULL;
    p->sommet = 0;
    p->capacite = 0;
}

Les Files

Concept et structure

Une file est une structure de données linéaire qui applique le principe FIFO (First In, First Out). Les ajouts s'effectuent à une extrémité appelée l'arrière (queue), et les suppressions à l'autre extrémité, l'avant (tête). Cela signifie que le premier élément inséré est le premier à être extrait.

Implémenttaion d'une file avec une liste chaînée

Pour une file, l'utilisation d'une liste chaînée est souvent préférable car elle permet des opérations d'insertion et de suppression efficaces aux deux extrémités, contrairement à un tableau où la suppression en tête pourrait être coûteuse.

Voici une réalisation possible.

Fichier d'en-tête File.h :

typedef int TypeElement;

typedef struct NoeudFile {
    TypeElement donnee;
    struct NoeudFile* suivant;
} NoeudFile;

typedef struct {
    NoeudFile* tete;
    NoeudFile* queue;
    int taille;
} File;

void InitialiserFile(File* f);
void Enfiler(File* f, TypeElement valeur);
void Defiler(File* f);
TypeElement TeteFile(File* f);
TypeElement QueueFile(File* f);
int TailleFile(File* f);
int EstVideFile(File* f);
void DetruireFile(File* f);

Fichier source File.c :

#include "File.h"
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

void InitialiserFile(File* f) {
    assert(f != NULL);
    f->tete = NULL;
    f->queue = NULL;
    f->taille = 0;
}

void Enfiler(File* f, TypeElement valeur) {
    assert(f != NULL);
    NoeudFile* nouveauNoeud = (NoeudFile*)malloc(sizeof(NoeudFile));
    if (nouveauNoeud == NULL) {
        perror("Échec de malloc");
        return;
    }
    nouveauNoeud->donnee = valeur;
    nouveauNoeud->suivant = NULL;
    if (f->queue == NULL) {
        f->tete = nouveauNoeud;
        f->queue = nouveauNoeud;
    } else {
        f->queue->suivant = nouveauNoeud;
        f->queue = nouveauNoeud;
    }
    f->taille++;
}

void Defiler(File* f) {
    assert(f != NULL);
    assert(f->taille > 0);
    NoeudFile* aSupprimer = f->tete;
    f->tete = f->tete->suivant;
    if (f->tete == NULL) {
        f->queue = NULL;
    }
    free(aSupprimer);
    f->taille--;
}

TypeElement TeteFile(File* f) {
    assert(f != NULL);
    assert(f->tete != NULL);
    return f->tete->donnee;
}

TypeElement QueueFile(File* f) {
    assert(f != NULL);
    assert(f->queue != NULL);
    return f->queue->donnee;
}

int TailleFile(File* f) {
    assert(f != NULL);
    return f->taille;
}

int EstVideFile(File* f) {
    assert(f != NULL);
    return (f->taille == 0) ? 1 : 0;
}

void DetruireFile(File* f) {
    assert(f != NULL);
    NoeudFile* courant = f->tete;
    while (courant != NULL) {
        NoeudFile* suivant = courant->suivant;
        free(courant);
        courant = suivant;
    }
    f->tete = NULL;
    f->queue = NULL;
    f->taille = 0;
}

Ces structures fondamentales ouvrent la voie à de nombreux algorithmes et applications plus complexes.