---
title: "Piles et files d'attente"
date: "2021-12-08"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# La liste chaînée et pile (1/N)

## Structure de données

* Chaque élément de la liste contient:
    1. une valeur,
    2. un pointeur vers le prochain élément.
* La pile est un pointeur vers le premier élément.

![Un exemple de liste chaînée.](figs/Singly-linked-list.svg){width=80%}

# La liste chaînée et pile (2/N)

## Une pile-liste-chaînée

```C
typedef struct _element {
    int data;
    struct _element *next;
} element;
typedef element* stack;
```

## Fonctionnalités?

. . .

```C
void stack_create(stack *s); // *s = NULL;
void stack_destroy(stack *s);
void stack_push(stack *s, int val);
void stack_pop(stack *s, int *val);
void stack_peek(stack s, int *val);
bool stack_is_empty(stack s); // reutrn NULL == stack;
```

# La liste chaînée et pile (3/N)

## Empiler? (faire un dessin)

. . .

```C







```

## Empiler? (le code ensemble)

. . .

```C
void stack_push(stack *s, int val) {
    element *elem = malloc(sizeof(*elem));
    elem->data = val;
    elem->next = *s;
    s = elem;
}
```

# La liste chaînée et pile (4/N)

## Jeter un oeil? (faire un dessin)

. . .

```C







```

## Jeter un oeil? (le code ensemble)

. . .

```C
void stack_peek(stack s, int *val) {
    *val = s->data;
}
```

# La liste chaînée et pile (5/N)

## Dépiler? (faire un dessin)

. . .

```C







```

## Dépiler? (le code ensemble)

. . .

```C
void stack_pop(stack *s, int *val) {
    stack_peek(*s, val);
    element *tmp = *s;
    *s = (*s)->next;
    free(tmp);
    return val;
}
```

# La liste chaînée et pile (6/N)

## Détruire? (faire un dessin)

. . .

```C







```

## Détruire? (le code ensemble)

. . .

```C
void stack_destroy(stack *s) {
    while (!stack_is_empty(*s)) {
        int val = stack_pop(s);
    }
}
```

# 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).

![Illustration d'une file
d'attente.](figs/fig_queue_representation.png)

## Structure de données en C?

. . .

```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

. . .

```C
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

. . .

```C
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):

. . .

![Insertion dans une file d'attente
vide.](./figs/fig_empty_queue_insert.png){width=40%}

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

. . .

![Insertion dans une file d'attente
non-vide.](./figs/fig_non_empty_queue_insert.png){width=70%}

# Enfilage

## Live (implémentation)

. . .

```C
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):

. . .

![Extraction d'une file d'attente](./figs/fig_queue_extract.png){width=80%}

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

. . .

![Extraction d'une file d'attente de longueur 1.](./figs/fig_queue_extract_one.svg){width=25%}


3. La file est vide (problème)

# Défilage

## Live (implémentation)

. . .

```C
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?

