Dans ce chapitre, nous allons étudier les structures de données permettant de stocker des éléments et de les récupérer ultérieurement. Ces structures sont omniprésentes en algorithmique pour gérer des collections d'éléments "en attente" de traitement.

Nous adopterons une démarche en deux temps : d'abord la définition formelle de ces structures de manière abstraite (quelles opérations offrent-elles ? comment les manipuler sans connaître leur mécanique interne ?), puis l'étude de leurs implémentations concrètes en machine, avec un focus sur les complexités temporelles et spatiales.

Structures abstraites¶

Le concept de Sac (Bag)¶

De manière très générale, on peut définir un concept abstrait de structure d'attente appelé le Sac (Bag en anglais).

Définition : Structure de Sac

Un Sac est une structure de données abstraite qui maintient une collection d'éléments. L'ordre interne n'est pas spécifié à ce niveau d'abstraction. Un sac abstrait expose minimalement les opérations suivantes :

creer_sac() : initialise un sac vide.
est_vide(s) : renvoie vrai si le sac s ne contient aucun élément.
ajouter(s, x) : insère l'élément x dans le sac s.
retirer(s) : retire et renvoie un élément du sac s. Si le sac est vide, le comportement est indéfini (erreur).

En pratique, on utilise très rarement un "Sac" générique. On le spécialise en imposant une règle stricte sur l'ordre de retrait des éléments. C'est cette règle de retrait qui distingue fondamentalement une pile d'une file.

Piles (Stacks)¶

Principe et vocabulaire¶

Une pile est une spécialisation du sac fonctionnant sur le principe LIFO (Last In First Out). Le dernier élément ajouté est le premier à être retiré.

La bonne manière de se représenter une pile est d'imaginer une pile d'assiettes ou de dossiers sur un bureau : on ajoute toujours un dossier sur le dessus de la pile, et lorsqu'on traite un dossier, on prend toujours celui qui est au sommet.

Dictionnaire Anglais / Français

Dans la littérature algorithmique et dans la plupart des bibliothèques standards (API), le vocabulaire anglophone est la norme incontournable. Il est impératif de le maîtriser :

Pile : Stack
Empiler (ajouter un élément au sommet) : Push
Dépiler (retirer et renvoyer l'élément au sommet) : Pop
Sommet (lire l'élément au sommet sans le retirer) : Peek ou Top
Est vide : Is_empty ou Empty

Évolution d'une pile représentée par un tableau : deux empilements puis un dépilement

Le principe du parcours destructeur¶

Dans le paradigme des structures abstraites pures, il n'y a pas d'opération pour accéder au $i$-ème élément d'une pile. Le seul élément accessible est le sommet. Pour parcourir ou chercher un élément au fond d'une pile, on est obligé de dépiler les éléments un à un. Ce processus détruit la pile originale.

Si l'on a besoin de conserver les données de la pile initiale, il faut impérativement sauvegarder les éléments dépilés dans une structure temporaire (généralement une seconde pile).

Longueur d'une pile avec deux piles¶

Imaginons le problème suivant : on souhaite écrire une fonction longueur qui calcule le nombre d'éléments d'une pile p, en n'utilisant que les opérations abstraites de pile, et qui garantit qu'à la fin de la fonction, la pile p a retrouvé son état exact d'origine.

L'algorithme consiste à :

Créer une pile temporaire temp.
Tant que p n'est pas vide, pop(p), incrémenter un compteur, et push(temp, element).
Une fois p vide, vider temp pour remettre les éléments dans p : tant que temp n'est pas vide, push(p, pop(temp)).

pythonocaml

def longueur_pile(p):
    '''Calcule la longueur de la pile p sans la modifier de manière permanente.'''
    temp = creer_pile()
    compteur = 0

    # Parcours destructeur et sauvegarde
    while not est_vide(p):
        x = depiler(p)
        empiler(temp, x)
        compteur += 1

    # Restauration de la pile initiale
    while not est_vide(temp):
        x = depiler(temp)
        empiler(p, x)

    return compteur

let longueur_pile p =
  let temp = cree_pile () in
  let rec depiler_tout acc =
    if est_vide p then acc
    else begin
      let x = depile p in
      empile temp x;
      depiler_tout (acc + 1)
    end
  in
  let res = depiler_tout 0 in

  let rec restaurer () =
    if not (est_vide temp) then begin
      empile p (depile temp);
      restaurer ()
    end
  in
  restaurer ();
  res

Files (Queues)¶

Principe et vocabulaire¶

Une file est une structure de données abstraite permettant d'ajouter et de retirer des éléments selon le principe FIFO (First In First Out). Le premier élément inséré sera le premier à en sortir, exactement comme une file d'attente à la caisse d'un magasin.

Dictionnaire Anglais / Français

File : Queue
Enfiler (ajouter un élément à l'arrière) : Enqueue (parfois Push)
Défiler (retirer et renvoyer l'élément à l'avant) : Dequeue (parfois Pop)
Avant / Tête : Front ou Head
Arrière / Queue : Rear ou Tail

Rotation d'une file¶

Contrairement à la pile qui nécessite une seconde pile pour préserver ses éléments lors d'un parcours, la file possède une propriété remarquable due à sa géométrie "en tube" : la rotation. L'opération de rotation consiste à défiler l'élément en tête et à le ré-enfiler immédiatement à la fin de la file.

def rotation(f):
    x = defiler(f)
    enfiler(f, x)

En effectuant exactement $N$ rotations consécutives (où $N$ est la taille de la file), la file retrouve son état initial !

Calcul de la longueur à l'aide d'une sentinelle¶

Comment calculer la longueur d'une file si l'on ne connaît pas $N$ à l'avance, tout en utilisant la rotation pour ne pas la détruire ? L'astuce classique consiste à enfiler une sentinelle : une valeur spéciale reconnaissable (par exemple None en Python, ou un pointeur NULL en C), dont on est sûr qu'elle n'apparaît pas parmi les éléments de la file.

L'algorithme :

Enfiler la sentinelle.
Initialiser un compteur à 0.
Boucle : défiler un élément.
- Si c'est la sentinelle, on arrête la boucle.
- Sinon, on incrémente le compteur, et on ré-enfile l'élément (rotation).

À la fin de cet algorithme, tous les éléments originaux ont fait exactement un tour complet de la file, et la sentinelle a été détruite. La file est restaurée, et on a la longueur.

python

def longueur_file(f):
    enfiler(f, None)  # La sentinelle
    compteur = 0

    while True:
        x = defiler(f)
        if x is None:
            break
        compteur += 1
        enfiler(f, x) # Rotation

    return compteur

Files de priorité (Priority Queues)¶

Une file de priorité est une structure où chaque élément ajouté possède une "priorité" (qui peut être sa propre valeur, ou une clé associée). La règle de retrait n'est ni LIFO ni FIFO : l'opération retirer() extrait systématiquement l'élément de plus haute priorité (souvent défini comme la plus petite valeur, par exemple dans un algorithme de graphe).

Dictionnaire Anglais / Français

File de priorité : Priority Queue
En général, l'implémentation sous-jacente utilise un Tas (Heap).

Choisir la bonne structure et applications¶

Le choix de la structure "sac" dicte l'ordre d'exploration d'un espace de recherche, ce qui modifie drastiquement le comportement des algorithmes.

Illustration classique : le Flood-Fill¶

Prenons l'algorithme de remplissage par diffusion (flood-fill), typique de l'outil "pot de peinture" des logiciels de dessin. L'objectif est de colorier une zone de pixels de même couleur. On maintient un Sac de pixels à visiter. À chaque étape, on retire un pixel du Sac ; s'il n'est pas déjà colorié, on le colorie et on ajoute au Sac ses voisins ayant encore la couleur d'origine (un même pixel peut donc être présent plusieurs fois dans le Sac).

Si le Sac est une Pile (LIFO) : Le comportement sera un Parcours en Profondeur (Depth-First Search ou DFS). L'algorithme va suivre un chemin le plus loin possible avant de revenir sur ses pas. Visuellement, le remplissage avance sous la forme de longs "serpents" qui rebondissent sur les bords.
Si le Sac est une File (FIFO) : Le comportement sera un Parcours en Largeur (Breadth-First Search ou BFS). L'algorithme traitera tous les pixels à distance 1, puis à distance 2. Visuellement, le remplissage se fait par "fronts concentriques" réguliers autour du point de départ (des losanges si l'on considère les 4 voisins d'un pixel, puisque la distance est alors celle de Manhattan).

Implémentations concrètes¶

D'un point de vue algorithmique, les opérations d'ajout et de retrait dans une pile ou une file doivent s'exécuter en temps constant, $\mathcal{O}(1)$, éventuellement seulement en complexité amortie. Nous allons voir comment garantir cette complexité en C et en OCaml.

Implémentation des piles¶

Dans un tableau borné (C)¶

C'est l'implémentation la plus courante et la plus rapide si on connaît une borne supérieure au nombre d'éléments. On utilise un tableau statique (ou alloué dynamiquement) t de taille $N$, et un entier fond qui représente l'indice de la première case libre.

Initialisation : fond = 0
Empiler(x) : On écrit x à l'indice fond, puis on incrémente fond.
Dépiler() : On décrémente fond, et on renvoie l'élément à ce nouvel indice. (L'élément reste physiquement en mémoire, mais il est logiquement "hors" de la pile et sera écrasé au prochain empiler).

c

#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#define N 1000 // Capacité maximale de la pile

struct pile {
    int *t;
    int fond;
};
typedef struct pile pile;

pile *pile_creer() {
    pile *p = malloc(sizeof(pile));
    p->t = malloc(sizeof(int) * N);
    p->fond = 0;
    return p;
}

void pile_detruire(pile *p) {
    free(p->t);
    free(p);
}

void empiler(pile *p, int x) {
    assert(p->fond < N); // Vérification de débordement (Stack Overflow)
    p->t[p->fond] = x;
    p->fond++;
}

int depiler(pile *p) {
    assert(p->fond > 0); // Vérification de pile vide (Stack Underflow)
    p->fond--;
    return p->t[p->fond];
}

bool est_vide(pile *p) {
    return p->fond == 0;
}

Avec des listes chaînées (OCaml)¶

Dans les langages fonctionnels, les listes chaînées (simples) sont la structure de base. Ajouter un élément en tête d'une liste chaînée (x :: liste) ou récupérer la tête (match liste with x :: q -> ...) sont des opérations en $\mathcal{O}(1)$. Une liste est donc naturellement une pile.

Pour offrir une interface mutable (opérations avec effets de bord), on encapsule la liste dans une référence (pointeur) :

ocaml

type 'a pile = 'a list ref

let cree_pile () = ref []

let est_vide p = !p = []

let empile p x =
  p := x :: !p

let depile p =
  match !p with
  | [] -> failwith "Erreur : dépiler sur une pile vide"
  | x :: q ->
    p := q;
    x

Implémentation des files¶

L'implémentation des files est plus délicate car les opérations se font aux deux extrémités de la structure (ajout à l'arrière, retrait à l'avant).

Dans un tableau borné (Circulaire en C)¶

Si l'on implémentait une file naïvement dans un tableau en ajoutant à l'indice $i$ et en retirant à l'indice $0$ (en décalant tout le monde), le retrait prendrait un temps $\mathcal{O}(N)$, ce qui est inacceptable.

On utilise donc un tableau circulaire avec deux indices : debut et fin.

File dans un tableau circulaire : debut repère le premier élément, fin la première case libre.

Dans cette représentation, debut est l'indice du premier élément de la file et fin celui de la première case libre, située juste après le dernier élément (les indices croissent dans le sens des aiguilles d'une montre).

Pour enfiler, on écrit l'élément dans la case fin puis on avance fin d'une case :

Enfiler 3 : on écrit dans la case fin, puis fin avance d'une case. — Enfiler $3$ : on écrit dans la case fin, puis fin avance d'une case.

Pour défiler, on lit l'élément de la case debut puis on avance debut d'une case :

Défiler : on lit la case debut (on renvoie 1), puis debut avance d'une case. — Défiler : on lit la case debut (on renvoie $1$), puis debut avance d'une case.

Lorsque fin (ou debut) arrive au bout du tableau en mémoire, il doit repartir à l'indice $0$. L'astuce est d'utiliser l'opérateur modulo (% N).

Le même tableau circulaire, coupé et mis à plat comme il est rangé en mémoire.

c

struct file {
    int *t;
    int debut;
    int fin;
    int taille; // On maintient la taille courante pour distinguer file vide de file pleine
};
typedef struct file file;

file *file_creer() {
    file *f = malloc(sizeof(file));
    f->t = malloc(sizeof(int) * N);
    f->debut = 0;
    f->fin = 0;
    f->taille = 0;
    return f;
}

void file_detruire(file *f) {
    free(f->t);
    free(f);
}

bool file_est_vide(file *f) {
    return f->taille == 0;
}

void enfiler(file *f, int x) {
    assert(f->taille < N);
    f->t[f->fin] = x;
    f->fin = (f->fin + 1) % N; // Circularité
    f->taille++;
}

int defiler(file *f) {
    assert(f->taille > 0);
    int res = f->t[f->debut];
    f->debut = (f->debut + 1) % N; // Circularité
    f->taille--;
    return res;
}

Remarque

Le C ne permet pas de définir deux fonctions de même nom, même si elles portent sur des types différents. Si l'on souhaite utiliser une pile et une file dans un même programme, on ne peut pas appeler est_vide les deux tests : on préfixe donc le nom des fonctions par celui de la structure, comme pour file_creer et file_detruire. Le test de la pile gagnerait ainsi à s'appeler pile_est_vide.

Implémentation avec deux listes (OCaml)¶

Comment créer une file FIFO efficace dans un langage fonctionnel sans utiliser de tableaux ? L'astuce brillante consiste à utiliser deux piles (donc deux listes) :

Une pile entree dédiée aux insertions.
Une pile sortie dédiée aux retraits.

Pour enfiler, on pousse simplement dans entree ($\mathcal{O}(1)$). Pour défiler, on extrait de sortie ($\mathcal{O}(1)$). Mais que faire si sortie est vide ? On prend alors l'intégralité de la pile entree, on la renverse (List.rev), et on la place dans sortie.

Renverser une liste de longueur $k$ coûte $\mathcal{O}(k)$. Mais ce coût élevé n'est payé que ponctuellement. Sur une longue séquence d'opérations, chaque élément est empilé une fois dans entree, transféré une seule fois dans sortie lors d'un renversement, et dépilé une fois. Le coût amorti reste donc de $\mathcal{O}(1)$ par opération.

Preuve

Comptons une unité de coût par cellule de liste créée ou parcourue. Considérons une suite de $m$ opérations partant d'une file vide, dont $e$ appels à enfile. Chaque élément enfilé passe au plus une fois de entree vers sortie (une fois dans sortie, il n'en sort que pour être défilé). Le coût total des renversements est donc au plus proportionnel à $e \le m$, et en dehors des renversements chaque opération est en $\mathcal{O}(1)$. Le coût total est ainsi en $\mathcal{O}(m)$, soit $\mathcal{O}(1)$ amorti par opération.

De manière équivalente, avec le potentiel $\Phi = |\texttt{entree}|$ : enfile a un coût réel $1$ et augmente $\Phi$ de $1$ ; un defile qui renverse une liste de longueur $k$ a un coût réel $k + 1$ et fait diminuer $\Phi$ de $k$ ; les autres defile ont un coût réel $1$ et ne modifient pas $\Phi$. Le coût amorti (coût réel $+ \Delta\Phi$) de chaque opération est donc au plus $2$, et comme $\Phi \ge 0$ avec $\Phi = 0$ initialement, le coût réel total de $m$ opérations est au plus $2m$.

Cette analyse suppose que la file est utilisée de manière éphémère (chaque version n'est utilisée qu'une fois), ce qui est le cas ici puisque les champs sont mutables. Avec une version persistante (sans mutable), on pourrait appeler plusieurs fois defile sur une même version ayant sortie vide et payer plusieurs fois le même renversement.

ocaml

type 'a file = {
  mutable entree : 'a list;
  mutable sortie : 'a list;
}

let cree_file () = { entree = []; sortie = [] }

let est_vide f = f.entree = [] && f.sortie = []

let enfile f x =
  f.entree <- x :: f.entree

let defile f =
  match f.sortie with
  | x :: q ->
      f.sortie <- q;
      x
  | [] ->
      match List.rev f.entree with
      | [] -> failwith "Erreur : défiler sur une file vide"
      | x :: q ->
          f.sortie <- q;
          f.entree <- [];
          x