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

# Les piles (1/5)

## Qu'est-ce donc?

* Structure de données abstraite...

. . .

* de type `LIFO` (*Last in first out*).

![Une pile où on ajoute A, puis B avant de les retirer. Source:
[Wikipedia](https://upload.wikimedia.org/wikipedia/commons/e/e1/Stack_%28data_structure%29_LIFO.svg)](figs/Stack.svg){width=70%}

## Des exemples de la vraie vie

. . .

* Pile d'assiettes, de livres, ...
* Adresses visitées par un navigateur web.
* Les calculatrices du passé (en polonaise inverse).
* Les boutons *undo* de vos éditeurs de texte (aka *u* dans vim).

# Les piles (2/5)

## Fonctionnalités

. . .

1. Empiler (push): ajouter un élément sur la pile.
2. Dépiler (pop): retirer l'élément du sommet de la pile et le retrouner.
3. Liste vide? (is_empty?).

. . .

4. Jeter un oeil (peek): retourner l'élément du sommet de la pile (sans le dépiler).
5. Nombre d'éléments (length).

## Comment faire les 4,5 à partir de 1 à 3?

. . .

4. Dépiler l'élément, le copier, puis l'empiler à nouveau.
5. Dépiler jusqu'à ce que la pile soit vide, puis empiler à nouveau.

. . .

## Existe en deux goûts

* Pile avec ou sans limite de capacité (à concurrence de la taille de la
mémoire).

# Les piles (3/5)

## Implémentation

* Jusqu'ici on n'a pas du tout parlé d'implémentation (d'où le nom de structure
  abstraite).
* Pas de choix unique d'implémentation.

## Quelle structure de données allons nous utiliser?

. . .

Et oui vous avez deviné: un tableau!

## La structure: de quoi avons-nous besoin (pile de taille fixe)?

. . .

```C
#define MAX_CAPACITY 500
typedef struct _stack {
    int data[MAX_CAPACITY]; // les données
    int top;                // indice du sommet
} stack;
```

# Les piles (4/5)

## Initialisation

. . .

```C
void stack_init(stack *s) {
    s->top = -1;
}
```

## Est vide?

. . .

```C
bool stack_is_empty(stack s) {
    return s.top == -1;
} 
```

## Empiler (ajouter un élément au sommet)

. . .

```C
void stack_push(stack *s, int val) {
    s->top += 1;
    s->data[s->top] = val;
}
```

# Les piles (5/5)

## Dépiler (enlever l'élément du sommet)

. . .

```C
int stack_pop(stack *s) {
    s->top -= 1;
    return s->data[s->top+1];
}
```

## Jeter un oeil (regarder le sommet)

. . .

```C
int stack_peek(stack *s) {
    return s->data[s->top];
}
```

## Quelle est la complexité de ces opérations?

. . .

## Voyez-vous des problèmes potentiels avec cette implémentation?

. . .

* Empiler avec une pile pleine.
* Dépiler avec une pile vide.
* Jeter un oeil au sommet d'une pile vide.

# Gestion d'erreur, level 0

* Il y a plusieurs façon de traiter les erreur:
    * Ne rien faire (laisser la responsabilité à l'utilisateur).
    * Faire paniquer le programme (il plante plus ou moins violemment).
    * Utiliser des codes d'erreurs.

## La panique

* En C, on a les `assert()` pour faire paniquer un programme.


# Assertions (1/3)

```C
#include <assert.h>
void assert(int expression);
```

## Qu'est-ce donc?

- Macro permettant de tester une condition lors de l'exécution d'un programme:
  - Si `expression == 0`{.C} (condition fausse), `assert()`{.C} affiche un message d'erreur sur `stderr`{.C} et termine l'exécution du programme.
  - Sinon l'exécution se poursuit normalement.
  - Peuvent être désactivés à la compilation avec `-DNDEBUG` (équivalent à `#define
    NDEBUG`)

## À quoi ça sert?

- Permet de réaliser des tests unitaires.
- Permet de tester des conditions catastrophiques d'un programme.
- **Ne permet pas** de gérer les erreurs.

# Assertions (2/3)

<!-- \footnotesize -->

## Exemple

```C
#include <assert.h>
void stack_push(stack *s, int val) {
    assert(s->top < MAX_CAPACITY-1);
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    assert(s->top >= 0);
    s->top -= 1;
    return s->data[s->top+1];
}
int stack_peek(stack *s) {
    assert(s->top >= 0);
    return s->data[s->top];
}
```

# Assertions (3/3)

## Cas typiques d'utilisation

- Vérification de la validité des pointeurs (typiquement `!= NULL`{.C}).
- Vérification du domaine des indices (dépassement de tableau).

## Bug vs. erreur de *runtime*

- Les assertions sont là pour détecter les bugs (erreurs d'implémentation).
- Les assertions ne sont pas là pour gérer les problèmes externes au programme (allocation mémoire qui échoue, mauvais paramètre d'entrée passé par l'utilisateur, ...).

. . .

- Mais peuvent être pratiques quand même pour ça...
- Typiquement désactivées dans le code de production.

# La pile dynamique

## Comment modifier le code précédent pour avoir une taille dynamique?

. . .

```C
// alloue une zone mémoire de size octets
void *malloc(size_t size); 
// change la taille allouée à size octets (contiguïté garantie)
void *realloc(void *ptr, size_t size);
```

## Et maintenant?

. . .

```C
stack_create(); // crée une pile avec une taille par défaut
// vérifie si la pile est pleine et réalloue si besoin
stack_push();
// vérifie si la pile est vide/trop grande 
// et réalloue si besoin
stack_pop(); 
```

## Exercice: ouvrir un repo/issues pour l'implémentation

* Oui-oui cela est une introduction au développement collaboratif (et
  hippie).

# Le tri à deux piles (1/N)

## Cas pratique

![Un exemple de tri à deux piles](figs/tri_piles.svg){width=70%}

# Le tri à deux piles (2/N)

## Exercice: formaliser l'algorithme

. . .

## Algorithme de tri nécessitant 2 piles (G, D)

Soit `tab` le tableau à trier:

```C
Pour tous les i = 0 à N-1
    
    tant que (tab[i] > que le sommet de G) {
        dépiler G dans D
    } 
    tant que (tab[i] < que le sommet de D) {
        dépiler de D dans G
    }

    empiler tab[i] sur G
dépiler tout D dans G
tab est trié dans G
```

# Le tri à deux piles (3/N)

## Exercice: trier le tableau `[2, 10, 5, 20, 15]`

```C
















```

# La calculatrice (1/8)

## Vocabulaire

```C
2 + 3 = 2 3 +,
```

`2` et `3` sont les *opérandes*, `+` l'*opérateur*.

. . .

## La notation infixe

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

## La notation postfixe

```C
2 3 2 + * 4 - = 6.
```

## Exercice: écrire `2 * 3 * 4 + 2` en notation `postfixe`

. . .

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

# La calculatrice (2/8)

## De infixe à post-fixe

* Une *pile* est utilisée pour stocker *opérateurs* et *parenthèses*.
* Les opérateurs on des *priorités* différentes.

```C
^   : priorité 3
* / : priorité 2
+ - : priorité 1
( ) : priorité 0 // pas un opérateur mais bon
```


# La calculatrice (3/8)

## De infixe à post-fixe: algorithme

* On lit l'expression infixe de gauche à droite.

* On examine le prochain caractère de l'expression infixe.
    * Si opérande, le placer dans l'expression du résultat.
    * Si parenthèse le mettre dans la pile (priorité 0).
    * Si opérateur, comparer sa priorité avec celui du sommet de la pile:
        * Si sa priorité est plus élevée, empiler.
        * Sinon dépiler l'opérateur de la pile dans l'expression du résultat et
          recommencer jusqu'à apparition d'un opérateur de priorité plus faible
          au sommet de la pile (ou pile vide).
    * Si parenthèse fermée, dépiler les opérateurs du sommet de la pile et les
      placer dans l'expression du résultat, jusqu'à ce qu'une parenthèse
      ouverte apparaisse au sommet, dépiler également la parenthèse.
    * Si il n'y a pas de caractère dans l'expression dépiler tous les
      opérateurs dans le résultat.

# La calculatrice (4/8)

## De infixe à post-fixe: exemple

```C
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
 (A*B)/D-F)/(G+H)   Vide                (       0
  A*B)/D-F)/(G+H)   Vide                ((      0
   *B)/D-F)/(G+H)   A                   ((      0
    B)/D-F)/(G+H)   A                   ((*     2
     )/D-F)/(G+H)   AB                  ((*     2
      /D-F)/(G+H)   AB*                 (       0
       D-F)/(G+H)   AB*                 (/      2
        -F)/(G+H)   AB*D                (/      2
         F)/(G+H)   AB*D/               (-      1
          )/(G+H)   AB*D/F              (-      1
           /(G+H)   AB*D/F-             Vide    Néant
```

# La calculatrice (5/8)

## De infixe à post-fixe: exemple

```C
Infixe              Postfixe            Pile    Priorité
((A*B)/D-F)/(G+H)   Vide                Vide    Néant
--------------------------------------------------------
           /(G+H)   AB*D/F-             Vide    Néant
            (G+H)   AB*D/F-             /       2
             G+H)   AB*D/F-             /(      0
              +H)   AB*D/F-G            /(      0
               H)   AB*D/F-G            /(+     1
                )   AB*D/F-GH           /(+     1
             Vide   AB*D/F-GH+          /       2
             Vide   AB*D/F-GH+/         Vide    Néant
```

# La calculatrice (6/8)

\footnotesize

## Exercice: écrire le code et le poster sur matrix

* Quelle est la signature de la fonction?

. . .

```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
            stack_push(&s, infix[i]); 
        } 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 (7/8)

## É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 (8/8)

## É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 (et poster sur matrix)

```C
bool evaluate(char *postfix, double *val) { // 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);
}
```

