---
title: "Calculatrices, liste chaînée, et files d'attente"
date: "2023-12-12"
---

# La calculatrice (Rappel)

## Écrire `2 * 3 * 4 + 2` en notation `postfixe`

. . .

```C
2 3 4 * * 2 + = (2 * (3 * 4)) + 2.
```

## Quelle structure de données utiliser pour la calculatrice?

. . .

La pile!

# La calculatrice (Rappel 2)

\footnotesize

## Quel est l'algorithme pour `infix_to_postfix`?

. . .

```C
char *infix_to_postfix(char* infix) { // init and alloc stack and postfix
    for (size_t i = 0; i < strlen(infix); ++i) {
        if (is_operand(infix[i])) { 
            // we just add operands in the new postfix string
        } else if (infix[i] == '(') { 
            // we push opening parenthesis into the stack
        } else if (infix[i] == ')') { 
            // we pop everything into the postfix
        } else if (is_operator(infix[i])) {
            // this is an operator. We add it to the postfix based 
            // on the priority of what is already in the stack and push it
        }    
    } 
    // pop all the operators from the s at the end of postfix
    // and end the postfix with `\0`
    return postfix;
} 
```


# La calculatrice (nouveautés)

## Évaluation d'expression postfixe: algorithme

* Chaque *opérateur* porte sur les deux opérandes qui le précèdent.
* Le *résultat d'une opération* est un nouvel *opérande* qui est remis au
  sommet de la pile.

## Exemple

```C
2 3 4 + * 5 - = ?
```

* On parcours de gauche à droite:

```C
Caractère lu        Pile opérandes
    2               2
    3               2, 3
    4               2, 3, 4
    +               2, (3 + 4)
    *               2 * 7
    5               14, 5
    -               14 - 5 = 9
```

# La calculatrice (nouveautés 2)

## Évaluation d'expression postfixe: algorithme

1. La valeur d'un opérande est *toujours* empilée.
2. L'opérateur s'applique *toujours* au 2 opérandes au sommet.
3. Le résultat est remis au sommet.

## Exercice: écrire l'algorithme en C (et poster sur matrix)

. . .

```C
double evaluate(char *postfix) { // init stack
    for (size_t i = 0; i < strlen(postfix); ++i) {
        if (is_operand(postfix[i])) {
            stack_push(&s, postfix[i]);
        } else if (is_operator(postfix[i])) {
            double rhs = stack_pop(&s);
            double lhs = stack_pop(&s);
            stack_push(&s, op(postfix[i], lhs, rhs));
        }    
    }
    return stack_pop(&s);
}
```



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

## 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/6)

## 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/6)

## 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/6)

## 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/6)

## 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);
}
```

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

## 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, &val);
    }
}
```


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

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

## Structure de données en C?

. . .

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

. . .

```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) {
    element* 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éfiler?

. . .

* Détruire?

. . .

* Est vide?


# Implémentation alternative

## Comment implémenter la file autrement?

. . .

* Données stockées dans un tableau;
* Tableau de taille connue à la compilation ou pas (réallouable);
* `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

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

# File basée sur un tableau

* Initialisation?

. . .

```C




```

* Est vide?

. . .

```C




```


* Enfiler?

. . .

```C




```

* Défiler?

. . .

```C




```

# Complexité

## Quelle sont les complexités de:

* Initialisation?

. . .

```C




```

* Est vide?

. . .

```C

```


* Enfiler?

. . .

```C




```

* Défiler?

. . .

```C




```

# Une file plus efficace

## Comment faire une file plus efficace?

* Où est-ce que ça coince?

. . .

* Défiler est particulièrement lent $\mathcal{O}(N)$.

## Solution?

. . .

* Utiliser un indice séparé pour `head`.

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

# Une file plus efficace (implémentation)

## Enfilage

\footnotesize

```C
void queue_enqueue(queue *fa, int val) {
    if ((fa->head == 0 && fa->tail == fa->capacity-1) ||
            (fa->tail == (fa->head-1) % (fa->capacity-1))) {
        return; // queue is full
    }
    if (fa->head == -1) { // queue was empty
        fa->head = fa->tail = 0;
        fa->data[fa->tail] = val;
    } else if (fa->tail == fa->capacity-1 && fa->head != 0) {
        // the tail reached the end of the array
        fa->tail = 0;
        fa->data[fa->tail] = val;
    } else {
        // nothing particular
        fa->tail += 1;
        fa->data[fa->tail] = val;
    }
}
```

# Une file plus efficace (implémentation)

## Défilage

```C
void queue_dequeue(queue *fa, int *val) {
    if (queue_is_empty(*fa)) {
        return; // queue is empty
    }
    *val = fa->data[fa->head];
    if (fa->head == fa->tail) { // that was the last element
        fa->head = fa->tail = -1;
    } else if (fa->head == fa->capacity-1) {
        fa->head = 0;
    } else {
        fa->head += 1;
    }
}
```


# Les listes triées

Une liste chaînée triée est:

* une liste chaînée
* dont les éléments sont insérés dans l'ordre.

![Exemple de liste triée.](./figs/sorted_list_example.svg)

. . .

* L'insertion est faite telle que l'ordre est maintenu.

## Quelle structure de données?

```C





```

# Les listes triées

## Quel but?

* Permet de retrouver rapidement un élément.
* Utile pour la recherche de plus court chemin dans des graphes.
* Ordonnancement de processus par degré de priorité.

## Comment?

* Les implémentations les plus efficaces se basent sur les tableaux.
* Possibles aussi avec des listes chaînées.

# Les listes triées

\footnotesize

## Quelle structure de données dans notre cas?


Une liste chaînée bien sûr (oui c'est pour vous entraîner)!

```C
typedef struct _element { // chaque élément
    int data;
    struct _element *next;
} element;
typedef element* sorted_list; // la liste
```

## Fonctionnalités

```C
// insertion de val
sorted_list sorted_list_push(sorted_list list, int val);
// la liste est-elle vide?
bool is_empty(sorted_list list); // list == NULL
// extraction de val (il disparaît)
sorted_list sorted_list_extract(sorted_list list, int val); 
 // rechercher un élément et le retourner
element* sorted_list_search(sorted_list list, int val);
```

# L'insertion

## Trois cas

1. La liste est vide.

. . .

![Insertion dans une liste vide, `list == NULL`.](figs/sorted_list_insert_one.svg){width=30%}

. . .

```C
sorted_list sorted_list_push(sorted_list list, int val) {
    if (sorted_list_is_empty(list)) {
        list = malloc(sizeof(*list));
        list->data = val;
        list->next = NULL;
        return list;
    }
}
```

# L'insertion

2. L'insertion se fait en première position.

. . .

![Insertion en tête de liste, `list->data >=
val`.](figs/sorted_list_insert_first.svg){width=80%}

. . .

```C
sorted_list sorted_list_push(sorted_list list, int val) {
    if (list->data >= val) {
        element *tmp = malloc(sizeof(*tmp));
        tmp->data = val;
        tmp->next = list;
        list = tmp;
        return list;
    }
}
```

# L'insertion

3. L'insertion se fait sur une autre position que la première.

. . .

![Insertion sur une autre position, list->data <
val.](figs/sorted_list_insert_any.svg){width=70%}

. . .

\footnotesize

```C
sorted_list sorted_list_push(sorted_list list, int val) {
    element *tmp = malloc(sizeof(*tmp));
    tmp->data = val;
    element *crt = list;
    while (NULL != crt->next && val > crt->next->data) {
        crt = crt->next;
    }
    tmp->next = crt->next;
    crt->next = tmp;
    return list;
}
```


