1. Introduction

Les implémentations des types abstraits Pile et File mises en place dans les 2 fiches précédentes s'appuient sur des listes chaînées dynamiques (circulaire, ou non). Ces implémentation "de référence" on ceci d'intéressant qu'elles ne limitent pas le nombre d'élément pouvant être placé dans la pile (resp. la file).

Par contre, elles recourent à l'allocation dynamique. Or, la réservation de la mémoire avec calloc() pour chaque maillon et la segmentation de la mémoire qui en résulte implique, en pratique, un coût algorithmique à chaque enfilage/empilage qui, dans certains contextes où il faut aller très vite, s'avèrent pénalisant.

Le fait d'utiliser un tableau alloué une fois pour toute pour stocker les éléments :

• évite toute allocation dynamique et libération de mémoire lors de l'ajout ou la suppresssion d'un élément
• et évite la segmentation mémoire, puisque tous les éléments soient concentrés dans le tableau, en une seule zone mémoire.

Le nombre maximal d'élément que pourra contenir la pile, ou la file, est alors le nombre de cases du tableau.

Exemples de cas où l'implémentation basée tableau est intéressante pour les Piles :

• Lorsqu'on exécute un programme la "pile d'appel de fonction" est implantée au moyen d'un tableau. D'ailleurs, c'est pour cela qu'il existe une limite, fixée par le système d'exploitation, au nombre d'appels de fonction pouvant être empilés, par exemple lors d'un appel récursif.

Exemples de cas où l'implémentation basée tableau est intéressante pour les Files :

• En traitement du signal, lorsque par exemple des échantillons doivent être stockés entre un algorithme qui les produit et un algorithme qui les consomme.
• Dans certaines communications entre processus, ou entre processeurs. Par exemple, dans la communication entre la lecture d'échantillons audio dans un fichier audio par le processeur central, et l'utilisation des échantillons sur la carte son de la machine, via le bus PCI.

2. Implémentation du TAD Pile s'appuyant sur un tableau

En langage C, le type Pile, que nous nommerons lifotab_t, est alors défini par :

• Un tableau, alloué dynamiquement
• La taille du tableau (nombre maximum d'éléments que peut accueillir la pile)
• Le nombre d'éléments présents dans la pile (nombre de cases utilisées au début du tableau)

Voici, par l'image, comment s'utiliserait le tableau :

Implémentation du TAD pile par un tableau.
Dans cet exemple, les éléments sont de type double et la pile peut contenir au maximum 7 éléments.

On donne ci-dessous ce que pourrait être le fichier lifotab.h pour cette implémentation. Notez :

• La déclaration du type lifotab_t
• Le fait que, dans cette API, pour les fonction d'empilage int lifotab_push(element_t e, lifotab_t * p_stack), et de défilage si la pile est pleine et que l'empilage n'est pas possible, on préfère retourner un code erreur que déclarer des préconditions.

        // fichier lifotab.h pour l'implantation du TAD pile au moyen d'un tableau
        #ifndef lifotab_TAB_H_
        #define lifotab_TAB_H_

        #include "element.h"  // Comme introduit dans l'implémentation de référence des listes
                              // on suppose qu'il existe un fichier définissant
                              // le type des éléments placés dans la pile

        // 1. declaration du type lifotab_t
        typedef struct {
          element_t * tab;  // pointeur sur tableau d'élément alloué dynamiquement
          int tab_size;     // taille du tableau
          int nb_elts;      // nombre d'éléments dans la pile (nombre de cases utilisées dans le tableau)
        } lifotab_t;

        // 2. prototype des fonctions de l'API du TAD Pile

        // Crée et retourne un pile vide pouvant accueillir au maximum  nb_max  éléments
        // ou une pile vide en cas d'erreur
        lifotab_t lifotab_new(int nb_max);

        // Détruit la pile et retourne une pile vide
        lifotab_t lifotab_delete(lifotab_t pile);

        // Retourne 1 si la pile  stack   est vide, 0 sinon
        int lifotab_is_empty(lifotab_t stack);

        // Retourne le nombre d'éléments présents dans la pile
        int lifotab_count(lifotab_t stack);

        // Ajoute l'élément e à la pile pointée par  p_stack
        // Retourne 1 si l'ajout a pu être fait ; 0 sinon (nombre max d'éléments atteint)
        int lifotab_push(element_t e, lifotab_t * p_stack);

        // Retourne l'élément en tête de pile (sans l'enlever de la pile)
        // PRECONDITION : la pile  stack  ne doit pas être vide
        element_t lifotab_peek(lifotab_t stack);

        // Enlève l'élément en tête de la pile, et stocke cet élément dans   *p_tete
        // Retourne 1 si la suppression a pu être faite ; 0 sinon (pile vide)
        int lifotab_pop(lifotab_t * p_stack, element_t *p_tete);

        #endif
        

Et voici un extrait du fichier lifotab.c, avec les fonctions lifotab_new(), lifotab_push(), et lifotab_pop().

        // Extrait du fichier lifotab.c pour l'implantation du TAD pile au moyen d'un tableau
        #include <assert.h>
        #include "lifotab.h"

        // Retourne un pile vide pouvant accueillir au maximum  nb_max  éléments
        lifotab_t lifotab_new(int nb_max) {
          lifotab_t stack;
          stack.tab = NULL;
          stack.tab_size = 0;
          stack.nb_elt = 0;
          stack.tab = calloc(nb_max, sizeof(element_t));
          i(stack.tab == NULL) {
            return stack ; // en cas d'echec d'allocation, on retourne une pile vide
          }
          stack.tab_size = nb_max;
          return stack;
        }

        // Retourne 1 si la pile  s   est vide, 0 sinon
        int lifotab_is_empty(lifotab_t stack) {
          return (stack.nb_elt == 0) ;
        }

        // Ajoute l'élément e à la pile pointée par p_stack
        // Retourne 1 si l'ajout a pu être fait ; 0 sinon (nombre max d'éléments atteint)
        int lifotab_push(element_t e, lifotab_t * p_stack) {
          // gestion du cas "pile pleine"
          if( p_stack->nb_elt == p_stack->tab_size) {
            return 0;
          }
          // on place l'élément dans la première case vide du tableau
          p_stack->tab[ p_stack->nb_elt ] = e;
          p_stack->nb_elt ++;
          return 1;
        }

        ... ...

        // Enlève l'élément en tête de la pile, et stocke cet élément dans   *p_tete
        // Retourne 1 si la suppression a pu être faite ; 0 sinon (pile vide)
        int lifotab_pop(lifotab_t * p_stack, element_t *p_tete) {
          // gestion du cas "pile vide"
          if( lifotab_is_empty(*p->stack) ) {
            return 0;
          }
          *p_tete = p_stack->tab[p_stack->nb_elt -1];
          p_stack->nb_elt --;   // on indique que la dernière case qui était occupée devient libre
          return 1;
        }

        ... ...

        

3. Buffer circulaire (Ring Buffer) : implémentation du TAD File s'appuyant sur un tableau

Pour implanter une File au moyen d'un tableau, on étend le principe utilisé pour les piles. Dans un premier temps, les éléments sont enfilés à la fin de la zone occupée dans le tableau et on défilés au début de la zone occupée.

Au fur et à mesure des opérations d'enfilage et de défilage, il arrive un moment ou la fin du tableau est pleine, mais le début est vide. Si on enfile un nouvel élément, il sera alors ajouté dans la première case du tableau, comme le montre l'image suivante :

Implémentation du TAD file par un tableau ("buffer circulaire").
Dans cet exemple, les éléments sont de type double et la file peut contenir au maximum 7 éléments.

Autrement dit, le tableau est utilisé "circulairement", modulo sa taille.

De ce fait, de façon théorique, et même si cela n'est pas une représentation bien propre de la mémoire, un buffer circulaire est souvent représenté graphiquement au moyen d'un cercle :

Représentation théorique d'un buffer circulaire au moyen d'un cercle.

Le buffer ici représenté peut contenir au maximum 12 éléments (ici des double).

Etat après ajout (enfilage) de 4 éléments.

Etat après ajout (enfilage) d'un élément.

Etat après suppression (défilage) d'un élément.

Etat après suppression (défilage) de 2 éléments.

Etat après ajout (enfilage) de 8 éléments.

Etat après suppression (défilage) de 5 éléments.

         // extrait du fichier ringbuffer.h pour l'implantation du TAD file au moyen d'un buffer circulaire
         typedef struct {
           element_t     *buffer; // tableau qui sera alloué dynamiquement
           int size;              // taille du tableau (nb max d'elements)
           int id_head;           // indice de la case du tableau contenant la tête
           int nb;                // nombre d'éléments utilisés dans le buffer
         } ringbuffer_t ;
         

[En savoir plus] Implémentation en C d'un ring buffer

         // fichier ringbuffer.h pour l'implantation du TAD file au moyen d'un buffer circulaire
         #ifndef ringbuffer_H_
         #define ringbuffer_H_

         #include 

         #include "element.h" // on suppse que le type element_t est déclaré dans ce fichier

         // 1. declaration explicite du type ringbuffer_t.
         typedef struct {
           element_t     *buffer; // tableau qui sera alloué dynamiquement
           int size;
           int id_head;  // indice de la case du tableau contenant la tête
           int nb;       // nombre d'éléments utilisés dans le buffer
         } ringbuffer_t ;

         // 2. prototype des fonctions de l'API du TAD Pile

         // Crée et retourne un pile vide pouvant accueillir au maximum  nb_max  éléments
         // ou une pile vide en cas d'erreur
         ringbuffer_t ringbuffer_new(int nb_max);

         // Détruit la pile et retourne une pile vide
         ringbuffer_t ringbuffer_delete(ringbuffer_t rb);

         // Retourne 1 si le buffer est vide, 0 sinon
         int ringbuffer_is_empty(ringbuffer_t rb);

         // Retourne le nombre d'éléments présents dans la pile
         int ringbuffer_count(ringbuffer_t rb);

         // Ajoute l'élément e au buffer pointée par p_rb
         // Retourne 0 si l'ajout a pu être fait ; une valeur non nulle sinon (nombre max d'éléments atteint)
         int ringbuffer_enqueue(element_t e, ringbuffer_t * p_rb);

         // Retourne l'élément en tête dans dans *p_e (sans l'enlever de la pile)
         // PRECONDITION :  ring buffer non vide
         element_t ringbuffer_peek(ringbuffer_t rb);

         // Retourne l'élément en tête du buffer *p_rb dans dans *p_e
         // et enlève cet élément du buffer.
         // Retourne 0 si OK ; une valeur non nulle en cas d'erreur (cas ring buffer vide)
         int ringbuffer_dequeue(element_t *p_e, ringbuffer_t * p_rb);
         #endif
       

       // fichier ringbuffer.c pour l'implantation du TAD file au moyen d'un buffer circulaire
       #include "ringbuffer.h"
       // Crée et retourne un pile vide pouvant accueillir au maximum  nb_max  éléments
       // ou un ringbuffer vide en cas d'erreur
       ringbuffer_t ringbuffer_new(int nb_max) {
         ringbuffer_t rb;
         rb.buffer   = NULL;
         rb.size     = 0;
         rb.id_head  = 0;
         rb.nb       = 0;
         rb.buffer = calloc(nb_max, sizeof(element_t));
         if(rb.buffer == NULL) {
           return rb;
         }
         rb.size     = nb_max;
         return rb;
       }

       // Détruit la pile et retourne une pile vide
       ringbuffer_t ringbuffer_delete(ringbuffer_t rb) {
         free(rb.buffer);
         rb.buffer   = NULL;
         rb.size     = 0;
         rb.id_head  = 0;
         rb.nb       = 0;
         return rb;
       }

       // Retourne 1 si le buffer est vide, 0 sinon
       int ringbuffer_is_empty(ringbuffer_t rb) {
         return rb.nb == 0;
       }

       // Retourne le nombre d'éléments présents dans la pile
       int ringbuffer_count(ringbuffer_t rb) {
         return rb.nb;
       }

       // Ajoute l'élément e au buffer pointée par p_rb
       // Retourne 0 si l'ajout a pu être fait ; une valeur non nulle sinon (nombre max d'éléments atteint)
       int ringbuffer_enqueue(element_t e, ringbuffer_t * p_rb){
         if(p_rb->nb == p_rb->size) {
           return 1;
         }
         // calcul de l'indice de la case où ajouter
         int id_tail = (p_rb->id_head + p_rb->nb) % p_rb->size ; // notez le modulo !
         p_rb->buffer[id_tail] = e;
         p_rb->nb ++;
         return 0;
       }

       // Retourne l'élément en tête dans dans *p_e (sans l'enlever de la pile)
       // PRECONDITION :  ring buffer non vide
       element_t ringbuffer_peek(ringbuffer_t rb) {
         assert( ! ringbuffer_is_empty(rb)) ; // vérification de la précondition
         return rb.buffer[rb.id_head];
       }

       // Retourne l'élément en tête du buffer *p_rb dans dans *p_e
       // et enlève cet élément du buffer.
       // Retourne 0 si OK ; une valeur non nulle en cas d'erreur (cas ring buffer vide)
       int ringbuffer_dequeue(element_t *p_e, ringbuffer_t * p_rb){
         // on récupère la tête
         if(ringbuffer_peek(p_e, *p_rb) != 0){
           return 1;
         }
         // on libère la case en tête
         p_rb->nb -- ;
         p_rb->id_head = (p_rb->id_head + 1) % p_rb->size ; // notez le modulo !
         return 0;
       }
       

         // fichier ringbuffer_test.c
         #include 
         #include "ringbuffer.h"

         int main() {
           element_t e;

           ringbuffer_t rb = ringbuffer_new(10);
           ringbuffer_enqueue(1.0, &rb);

           ringbuffer_peek(&e, rb);
           printf("TETE %lf\n", e);

           for(int i = 2 ; i<= 10 ; i ++) {
             printf("ajout de %lf\n", (double)i);
             ringbuffer_enqueue(i, &rb);
           }

           printf("Count (doit valoir 10) %d\n", ringbuffer_count(rb));

           ringbuffer_peek(&e, rb);
           printf("TETE %lf\n", e);

           printf("Ajout invalide ? %d \n", ringbuffer_enqueue(11.0, &rb));
           printf("Count (doit valoir 10) %d\n", ringbuffer_count(rb));

           ringbuffer_peek(&e, rb);
           printf("TETE %lf\n", e);

           for(int i = 0 ; i< 8 ; i ++) {
             ringbuffer_dequeue(&e, &rb);
             printf("POP %d =>  %lf\n", i, e);
           }
           printf("Count (doit valoir 2) %d\n", ringbuffer_count(rb));

           ringbuffer_enqueue(11.0, &rb);
           ringbuffer_enqueue(12.0, &rb);

           printf("Count (doit valoir 4) %d\n", ringbuffer_count(rb));

           for(int i = 0 ; i< 4 ; i ++) {
             ringbuffer_dequeue(&e, &rb);
             printf("POP %d =>  %lf\n", i, e);
           }

           printf("Count (doit valoir 0) %d\n", ringbuffer_count(rb));
           printf("Suppression invalide ? %d \n", ringbuffer_dequeue(&e, &rb));

           ringbuffer_enqueue(13.0, &rb);
           ringbuffer_dequeue(&e, &rb);
           printf("POP %d =>  %lf\n", 13, e);
           printf("Count (doit valoir 0) %d\n", ringbuffer_count(rb));
           rb = ringbuffer_delete(rb);
         }