Aller au contenu

Piles et Files

Sont traitées dans cette page les notions du CM n°3.

Piles avec les listes

Utilisation des piles avec les listes chaînées

Lorsque nous souhaitons empiler les éléments par la tête de la pile, alors dans ce cas nous passons par les listes chaînées pour les actions d'empilement et de dépilement.

On définit le type pile comme une liste simplement chaînée t_std_list, ce qui nous donne la syntaxe suivante :

typedef t_std_list t_stack_list;
Avec les listes, une pile n'est jamais pleine (on peut toujours ajouter des éléments en tête).

Fonctions générales

Créer une pile

Comme une pile est une liste simplement chaînée (t_stack_list est synonyme de t_std_list), alors on procède comme vu précédemment.

Le prototype de la fonction est :

t_stack_list createEmptyStack()
Implémentation en langage C 
t_stack_list createEmptyStack()
{
    t_stack_list s;
    s.head = NULL;
    return s;
}

Tester si la pile est vide

Tester qu'une pile est vide revient à tester si une liste simplement chaînée est vide. Donc la fonction doit renvoyer 1 si jamais la tête de la liste pointe vers l'adresse NULL, ou renvoie 0 dans le cas contraire.

Le prototype de la fonction est :

int isEmptyStack(t_stack_list s)
Implémentation en langage C 
int isEmptyStack(t_stack_list s)
{
    return (s.head == NULL); // (1)!
}
  1. Cette instruction renvoie True (1) ou False (0) au test de comparaison entre l'adresse de head et NULL sans avoir à passer par un if-else.

Afficher le contenu d'une pile

Avant de vouloir afficher quelque valeur que ce soit, il faut considérer le cas spécial où la liste est vide : on affiche stack [empty].

Si la liste contient au moins un élément, alors on vient parcourir la liste à l'aide d'une variable temporaire (cur par exemple) qui est un pointeur sur maillon, comme on le fait avec une liste simplement chaînée.

Le prototype de la fonction est :

void displayStack(t_stack_list s)
Implémentation en langage C 
void displayStack(t_stack_list s)
{
    t_cell *cur = s.head;

    if(s.head == NULL)
    {
        printf("stack [empty]\n");
        return; // (1)!
    }

    printf("stack [");

    while(cur != NULL)
    {
        printf(" : %d ", cur->value);
        cur = cur->next;
    }
    printf(" ]\n");

    return;
}
Exemple d'affichage
# Pile vide
stack [empty]

# Pile avec 3 éléments
stack [ : 30  : 20  : 10 ]
  1. Dans le cas d'une pile vide, on vient afficher stack [empty] puis "casser" la fonction avec un return de telle sorte que les lignes du dessous ne soient pas exécutées.

Empiler et dépiler

Empiler une valeur

Empiler une valeur consiste à rajouter une nouvelle cellule au début de la liste (chaînage en tête). On vient donc procéder comme vu précédemment pour les listes simplement chaînées.

Le prototype de la fonction est :

void stack(t_stack_list *ps, int val)
Implémentation en langage C 
void stack(t_stack_list *ps, int val)
{
    t_cell *pn = createCell(val); // (1)!
    pn->next = ps->head;
    ps->head = pn;
    return;
}
  1. On fait appel à la fonction createCell définie précédemment, c'est la même que pour les listes simplement chaînées.

Dépiler

Contrairement à la fonction suppressCell définie pour les listes simplement chaînées, ici on ne cherche pas à enlever une certaine valeur de la liste. En effet, on ne peut dépiler que la valeur en tête de notre liste, ce qui revient à constamment supprimer la tête.

Le prototype de la fonction est :

int unstack(t_stack_list *ps)
Implémentation en langage C 
int unstack(t_stack_list *ps)
{
    int res;
    t_cell *temp;

    if (isEmptyStack(*ps) == 0)
    {
        temp = ps->head;
        res = temp->value; // (1)!
        ps->head = temp->next;
        free(temp);
    }

    return res; // (2)!
}
  1. On affecte à la variable res la valeur qui a été dépilée, et c'est cette valeur qui sera retournée par la fonction.
  2. La fonction renvoie la valeur de res. Si la liste est vide, alors cette valeur est indéfinie : c'est pourquoi il faudra prendre en compte le cas où la liste est vide dans notre programme principal.

Piles avec les tableaux

Utilisation des piles avec les tableaux

Lorsque nous souhaitons empiler les éléments par la fin de la pile, alors dans ce cas nous passons par les tableaux pour les actions d'empilement et de dépilement.

On peut représenter la structure attendue par le schéma suivant :

Schéma de la structure d'une pile avec un tableau
Schéma de la structure d'une pile avec un tableau

Pour définir une pile à l'aide d'un tableau, on définit une valeur NBMAX comme suit :

#define NBMAX 50

Et on définit également une structure s_stack_tab (ainsi que son type associé) qui stockera le tableau et sa taille logique :

struct s_stack_tab
{
    int values[NBMAX];
    int nbElts; // nbElts correspond à la taille logique
};
typedef struct s_stack_tab t_stack_tab;

Une autre version de cette structure, plus complète, permet de s'affranchir de la définition d'une constante NBMAX. Pour cela, on passe par un pointeur sur tableau et on inclut la taille maximale directement dans la structure :

typedef struct s_stack_tab
{
    int *values;    // les valeurs à stocker
    int max_size;   // la taille max du tableau
    int nbElts;     // nbElts, le repère pour empiler/dépiler
} t_stack_tab;

C'est cette structure que nous allons utiliser pour l'implémentation des fonctions de cette partie.

Fonctions générales

Créer une pile

Comme une pile est un tableau, alors on vient créer un tableau vide de size cases (valeur entrée en paramètre) en allouant la mémoire et mettant à jour la taille maximale du tableau (max_size).

Le prototype de la fonction est :

t_stack_tab createEmptyStack(int size)
Implémentation en langage C 
t_stack_tab createEmptyStack(int size)
{
    t_stack_tab s;
    s.nbElts = 0; // (1)!

    if(size < 0)
    {
        s.max_size = 0; // (2)!
        s.values = NULL;
    }

    else
    {
        s.max_size = size;
        s.values = (int *)malloc(size * sizeof(int));
    }

    return s;
}
  1. Comme le tableau que l'on crée est vide, alors il ne contient aucun élément pour le moment.
  2. Ici on prend le parti de forcer la taille du tableau à 0 si la valeur entrée en paramètres est négative.

Tester si la pile est vide ou pleine

Tester qu'une pile est vide revient à tester si un tableau est vide. Donc la fonction doit renvoyer 1 si jamais le nombre d'éléments nbElts est 0.

Le prototype de la fonction est :

int isEmptyStack(t_stack_tab s)
Implémentation en langage C 
int isEmptyStack(t_stack_tab s)
{
    return (s.nbElts == 0); // (1)!
}
  1. Cette instruction renvoie True (1) ou False (0) au test de comparaison entre l'entier nbElts et 0 sans avoir à passer par un if-else.

Tester qu'une pile est pleine revient à tester si le nombre d'éléments de la liste (nbElts) est le même que la taille maximale (max_size). La fonction renvoie 1 si la condition est respectée, ou renvoie 0 dans le cas contraire.

Le prototype de la fonction est :

int isFullStack(t_stack_tab s)
Implémentation en langage C 
int isFullStack(t_stacktab s)
{
    return (s.nbElts==s.max_size); // (1)!
}
  1. Cette instruction renvoie True (1) ou False (0) au test de comparaison entre l'entier nbElts et max_size sans avoir à passer par un if-else.

Afficher le contenu d'une pile

Avant de vouloir afficher quelque valeur que ce soit, il faut considérer le cas spécial où le tableau est vide : on affiche stack [empty].

Si le tableau contient au moins un élément, alors on vient parcourir le tableau de la fin vers le début à l'aide d'une boucle for.

Le prototype de la fonction est :

void displayStack(t_stack_tab s)
Implémentation en langage C 
void displayStack(t_stack_tab s)
{
    int size = s.nbElts;

    printf("stack [");
    if (size==0)
    {
        printf("empty");
    }
    for (int cpt = size - 1; cpt >= 0; cpt--) // (1)!
    {
        printf(" : %d ", s.values[cpt]);
    }
    printf("]\n");

    return;
}
Exemple d'affichage
# Pile vide
stack [empty]

# Pile avec 3 éléments
stack [ : 30  : 20  : 10 ]
  1. On initialise notre compteur sur l'indice du dernier élément du tableau, puis l'on remonte jusqu'à l'indice 0.

Empiler et dépiler

Empiler une valeur

Empiler une valeur consiste à rajouter une nouvelle valeur après le dernier élément du tableau. On vient donc insérer la valeur puis mettre à jour le nombre d'éléments que contient la pile.

On peut représenter la situation par un schéma :

Schéma de l'empilement avec un tableau
Schéma de l'empilement avec un tableau

Le prototype de la fonction est :

void stack(t_stack_tab *ps, int val)
Implémentation en langage C 
void stack(t_stack_tab *ps, int val)
{
    int pos;
    pos = ps->nbElts; // (1)!
    ps->values[pos] = val;
    ps->nbElts = pos+1;
    return;
}
  1. Ici nbElts est l'indice où l'on doit positionner la nouvelle valeur puisque cette variable compte le nombre d'éléments, mais le tableau débutant à l'indice 0 on positionne bien après l'actuel dernier élément.

Dépiler

Dépiler avec un tableau revient à extraire la dernière valeur du tableau et à décrémenter le nombre d'éléments présents dans ce dernier. Cette fonction retourne la valeur dépilée.

On peut représenter la situation par un schéma :

Schéma du dépilement avec un tableau
Schéma du dépilement avec un tableau

Le prototype de la fonction est :

int unstack(t_stack_tab *ps)
Implémentation en langage C 
int unstack(t_stack_tab *ps)
{
    int res, pos;
    pos = ps->nbElts-1;
    res = ps->values[pos];
    ps->nbElts = pos; // (1)!
    return res;
}
  1. Comme on a pos = ps->nbElts-1 à la première ligne de cette fonction, alors le nombre d'éléments correspond bien à pos.

Files avec les listes

Création de files avec les listes

Une file est une structure de données dans laquelle on ajoute les valeurs à une extrémité et on les retire par l'autre. La première manière d'implémenter une file est de passer par une liste Head & Tail.

On définit donc le type d'une file comme suit :

typedef t_ht_list t_queue_list;

Fonctions générales

Créer une file

Comme une file est une liste Head & Tail, alors on réutilise la méthode de création de ce type de liste.

Le prototype de la fonction est :

t_queue_list createEmptyQueue()
Implémentation en langage C 
t_queue_list createEmptyQueue()
{
    t_queue_list ql;

    ql.head = NULL;
    ql.tail = NULL;

    return ql;
}

Tester si la file est vide

Tester qu'une file est vide revient à tester si une liste Head & Tail est vide. C'est-à-dire que la fonction renvoie 1 si la tête et la queue de la liste pointent tous les deux sur NULL, ou renvoie 0 dans le cas contraire. (1)

Le prototype de la fonction est :

int isEmptyQueue(t_queue_list ql)
Implémentation en langage C 
int isEmptyQueue(t_queue_list ql)
{
    return (ql.head == NULL && ql.tail == NULL);
}
  1. En soi, on pourrait se contenter de seulement vérifier si l'un des deux champs pointe bien sur NULL puisque dans ce cas nécessairement (si la file est bien implémentée) l'autre pointe aussi sur NULL.

Afficher le contenu d'une file

Pour afficher les éléments contenus dans une file, on vient tout simplement parcourir notre liste Head & Tail comme vu précédemment. On passe donc par un pointeur temporaire en parcourant de la tête vers la queue : on affiche les valeurs dans l'ordre de sortie tel que la valeur la plus à gauche soit la première à quitter la file.

Le prototype de la fonction est :

void displayQueue(t_queue_list ql)
Implémentation en langage C 
void displayQueue(t_queue_list ql)
{
    printf(" out <- ");
    t_cell *temp = ql.head;
    while (temp != NULL)
    {
        printf("%d <- ", temp->value);
        temp = temp->next;
    }
    printf("in\n");

    return;
}
Exemples d'affichage
# File vide
out <- in

# File contenant 5 éléments
out <- 10 <- 20 <- 30 <- 40 <- 50 <- in

Enfiler et défiler

Stratégie d'implémentation

On pourrait se dire qu'il y a deux stratégies pour réaliser l'enfilement et le défilement : soit enfiler par la tête et défiler par la queue, ou enfiler par la queue et défiler par la tête.

Pour choisir quelle stratégie est la meilleure, intéressons-nous à la complexité de chacune d'entre-elles.

  • Pour la première solution, enfiler par la tête a une complexité de o(1) puisque l'on connaît head. Toutefois, pour défiler en queue, il nous faut parcourir la liste avec un pointeur prev pour mettre à jour la nouvelle queue (on ne connaît pas le maillon précédent dans la structure de base) ce qui nécessite une complexité de o(N).
  • Quant à la deuxième option, les deux actions d'enfilement et de défilement on tous deux une complexité de o(1). En effet, puisque l'on connaît le maillon suivant de head alors pas besoin de pointeur temporaire !

On va donc implémenter toutes nos files utilisant des listes avec la deuxième stratégie. Cela explique l'ordre d'affichage des valeurs dans la fonction displayQueue déjà implémentée.

Enfiler une valeur

Enfiler une valeur consiste simplement en un chaînage en queue d'une liste Head & Tail (comme justifié dans l'encadré précédent). On procède donc comme vu précédemment.

Le prototype de la fonction est :

void enqueue(t_queue_list *ql, int val)
Implémentation en langage C 
void enqueue(t_queue_list *ql, int val)
{
    t_cell *nouv;
    nouv = createCell(val);

    if (isEmptyQueue(*ql)) // (1)!
    {
        ql->head = nouv;
        ql->tail = nouv;
    }
    else
    {
        ql->tail->next = nouv;
        ql->tail = nouv;
    }

    return;
}
  1. On considère le cas où la file est vide en utilisant la fonction précédemment implémentée. On pense bien à rajouter * avant ql pour assurer le déréférencement du pointeur. Une file vide implique que la tête et la queue pointent sur la même cellule.

Défiler

Défiler consiste en une suppression en tête de liste pour assurer le principe du First In - First Out (FIFO). Pour cela, on procède comme on l'a déjà vu pour les listes Head & Tail. Cette fonction renvoie la valeur défilée. On peut s'inspirer de la fonction unstack pour les piles avec listes chaînées pour réaliser cette implémentation.

Le prototype de la fonction est :

int dequeue(t_queue_list *ql)
Implémentation en langage C 
int dequeue(t_queue_list *ql)
{
    int res;
    t_cell *temp;
    if (isEmptyQueue(*ql) == 0) // (1)!
    {
        temp = ql->head;
        res = temp->value; 
        ql->head = temp->next;
        free(temp);
    }

    return res; 
}
  1. On teste bien que la liste n'est pas vide en utilisant la fonction déjà implémentée isEmptyQueue.

Files avec les tableaux

Création de files avec les tableaux

Une file est une structure de données dans laquelle on ajoute les valeurs à une extrémité et on les retire par l'autre. La deuxième manière d'implémenter une file est de passer par un tableau de valeurs.

On peut représenter la structure attendue par le schéma suivant :

Schéma de la structure d'une file avec un tableau
Schéma de la structure d'une file avec un tableau

On définit donc d'abord une taille maximale de ce tableau (taille physique) :

#define MAX 50

Et on définit également une structure s_queue_tab (ainsi que son type associé) qui stockera le tableau et les indices du premier élément (first) et du dernier emplecement disponible (last) :

typedef struct s_queue_tab
{
    int values[MAX];
    int first, last;
} t_queue_tab;

t_queue_tab createEmptyQueue();

Fonctions générales

Créer une file

Comme une file est un tableau, alors on vient simplement affecter aux valeurs first et last l'indice par défaut 0. La fonction n'ajoute pour le moment aucune valeur dans le tableau values.

Le prototype de la fonction est :

t_queue_tab createEmptyQueue()
Implémentation en langage C 
t_queue_tab createEmptyQueue()
{
    t_queue_tab q;
    q.first = q.last = 0;
    return q;
}

Tester si la file est vide ou pleine

Tester qu'une file est vide revient à tester si toutes les cases du tableau values sont inutilisées. C'est-à-dire que la fonction renvoie 1 si l'indice stocké dans first est le même que celui stocké dans last, ou renvoie 0 dans le cas contraire.

Le prototype de la fonction est :

int isEmptyQueue(t_queue_tab ql)
Implémentation en langage C 
int isEmptyQueue(t_queue_tab ql)
{
    return (q.first == q.last);
}

Tester qu'une file est pleine revient à tester si toutes les cases du tableau values sont utilisées. C'est-à-dire que la fonction renvoie 1 si la différence des indices first et last donne bien la taille physique du tableau MAX qui a été définie préalablement, ou renvoie 0 dans le cas contraire.

Le prototype de la fonction est :

int isFullQueue(t_queue_tab q)
Implémentation en langage C 
int isFullQueue(t_queue_tab q)
{
    return (q.last-q.first == MAX);
}

Afficher le contenu d'une file

Pour afficher les éléments contenus dans une file, on vient tout simplement parcourir notre tableau. On passe donc par une boucle for en allant de l'indice first jusqu'à l'indice last : on affiche les valeurs dans l'ordre de sortie tel que la valeur la plus à gauche soit la première à quitter la file.

Le prototype de la fonction est :

void displayQueue(t_queue_tab q)
Implémentation en langage C 
void displayQueue(t_queue_tab q)
{
    printf(" out <- ");
    for (int cpt = q.first ; cpt < q.last; cpt++)
    {
        printf("%d <- ", q.values[cpt%MAX]);
    }

    printf("in\n");

    return;
}
Exemples d'affichage
# File vide
out <- in

# File contenant 5 éléments
out <- 10 <- 20 <- 30 <- 40 <- 50 <- in

Enfiler et défiler

Enfiler une valeur

Pour l'enfilement d'une valeur avec un tableau, on vient ajouter une valeur au niveau de l'indice last (qui désigne l'indice suivant le dernier élément ajouté). On pense également à incrémenter le champ last après insertion de la nouvelle valeur dans la file.

On peut représenter la situation par un schéma :

Schéma de l'enfilage avec un tableau
Schéma de l'enfilage avec un tableau

Le prototype de la fonction est :

void enqueue(t_queue_tab *pq, int val)
Implémentation en langage C 
void enqueue(t_queue_tab *pq, int val)
{
    int pos;
    pos = pq->last % MAX; // (1)!
    pq->values[pos] = val;
    pq->last = pq->last+1;
}
  1. Ici l'utilisation de l'opérateur modulo (%) permet de vérifier que la position d'insertion ne dépasse pas la taille physique du tableau.

Défiler

Défiler consiste en une suppression du premier élément du tableau pour assurer le principe du First In - First Out (FIFO). Pour cela, on vient simplement incrémenter de 1 l'indice first. Cette fonction renvoie la valeur défilée.

On peut représenter la situation par un schéma :

Schéma du défilage avec un tableau
Schéma du défilage avec un tableau

Le prototype de la fonction est :

int dequeue(t_queue_tab *pq)
Implémentation en langage C 
int dequeue(t_queue_tab *pq)
{
    int res;
    int pos = pq->first%MAX; // (1)!
    res = pq->values[pos];
    pq->first = pq->first+1;
    return res;
}
  1. Ici l'utilisation de l'opérateur modulo (%) permet de vérifier que la position de suppression ne dépasse pas la taille physique du tableau.