cours_12.md

title: "Files d'attente, listes triées, et listes doublement chaînées"
date: "2023-12-19"

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)

\footnotesize

Implémentation possible

• La structure file, contient un pointeur vers la tête et un vers le début de la file.
• Entre les deux, les éléments sont stockés dans une liste chaînée.

Structure de données en C?

. . .

typedef 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

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.tail->data
int queue_head(queue fa); // return fa.head->data