cours_11.md

title: "Files d'attente et listes triées"
date: "2021-12-15"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto

La file d'attente (1/N)

• Structure de données abstraite permettant le stockage d'éléments.
• FIFO: First In First Out, ou première entrée première sortie.
• Analogue de la vie "réelle"":
  • File à un guichet,
  • Serveur d'impressions,
  • Mémoire tampon, ...

Fonctionnalités

. . .

• Enfiler, ajouter un élément à la fin de la file.
• Défiler, extraire un élément au devant de la file.
• Tester si la file est vide.

. . .

• Lire l'élément de la fin de la file.
• Lire l'élément du devant de la file.
• Créer une liste vide.
• Détruire une liste vide.

La file d'attente (2/N)

Implémentation possible

• La structure file, contient un pointeur vers la tête et un vers la queue.
• Entre les deux, les éléments sont stockés dans une liste chaînée (comme une pile).

Structure de données en C?

. . .

txpedef struct _element {  // Elément de liste
   int data;
   struct _element* next;
} element;

typedef struct _queue {    // File d'attente:
   element* head;  //    tête de file d'attente
   element* tail;  //    queue de file d'attente
} queue;

Fonctionnalités d'une file d'attente (gitlab)

Creation et consultations

. . .

void queue_init(queue *fa); // head = tail = NULL
bool queue_is_empty(queue fa); // fa.head == fa.tail == NULL
int queue_tail(queue fa); // return fa.head->data
int queue_head(queue fa); // return fa.tail->data

Manipulations et destruction

. . .

void queue_enqueue(queue *fa, int val); // adds an element before the tail
int queue_dequeue(queue *fa); // removes the head and returns stored value
void queue_destroy(queue *fa); // dequeues everything into oblivion

Enfilage

Deux cas différents:

1. La file est vide (faire un dessin):

. . .

2. La file n'est pas vide (faire un dessin):

. . .

Enfilage

Live (implémentation)

. . .

void queue_enqueue(queue *fa, int val) {
    element elmt = malloc(sizeof(*elmt));
    elmt->data = val;
    elmt->next = NULL;
    if (queue_is_empty(*fa)) {
        fa->head = elmt;
        fa->tail = elmt;
    } else {
        fa->tail->next = elmt;
        fa->tail = elmt;
    }
}

Défilage

Trois cas différents

1. La file a plus d'un élément (faire un dessin):

. . .

2. La file un seul élément (faire un dessin):

. . .

3. La file est vide (problème)

Défilage

Live (implémentation)

. . .

int queue_dequeue(queue *fa) {
    elmt = fa->head;
    int val = elmt->data;
    fa->head = fa->head->next;
    free(elmt);
    if (NULL == fa->head) {
        fa->tail = NULL;
    }
    return val;
}

. . .

Problème avec cette implémentation?

Destruction

Comment on faire la désallocation?

. . .

On défile jusqu'à ce que la file soit vide!

Complexité

Quelle sont les complexité de:

• Enfiler?

. . .

• Dépiler?

. . .

• Détruire?

. . .

• Est vide?

Implémentation alternative

Comment implémenter la file auterment?

. . .

• Données stockées dans un tableau;
• Tableau de taille connue à la compilation ou pas (reallouable);
• tail seraient les indices du tableau;
• capacity seraient la capacité maximale;
• On enfile "au bout" du tableau, au défile au début (indice 0).

. . .

Structure de données

typedef struct _queue {
    int *data;
    int tail, capacity;
} queue;

File basée sur un tableau