Piles (Stacks)

Principe LIFO

Une pile (stack) est une structure de données abstraite fonctionnant selon le principe LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré. Ce comportement est analogue à une pile d’assiettes, on ne peut accéder qu’à l’assiette du sommet.

Trois opérations fondamentales définissent une pile :

  • push : ajouter un élément au sommet, $O(1)$
  • pop : retirer l’élément au sommet, $O(1)$
  • peek/top : consulter l’élément au sommet sans le retirer, $O(1)$
Opération :  push(3)  push(7)  push(1)  pop()  peek()
Pile :       [^3]      [3,7]    [3,7,1]  [3,7]  → 7

Implémentation sur tableau

L’implémentation la plus directe repose sur un buffer linéaire avec un indice top repérant le sommet. C’est la version la plus performante grâce à la contiguïté mémoire (cf. cours précédent).

struct stack {
    int *data;
    int top;
    int capacity;
};

struct stack *stack_new(int capacity) {
    struct stack *s = (struct stack*)malloc(sizeof(struct stack));
    s->data = (int*)malloc(sizeof(int) * capacity);
    s->top = -1;
    s->capacity = capacity;
    return s;
}

void push(struct stack *s, int value) {
    if (s->top == s->capacity - 1) return; // stack overflow
    s->data[++s->top] = value;
}

int pop(struct stack *s) {
    if (s->top == -1) return -1; // stack underflow
    return s->data[s->top--];
}

int peek(struct stack *s) {
    if (s->top == -1) return -1;
    return s->data[s->top];
}

Avantages :

  • Localité cache parfaite : le sommet est toujours dans les dernières lignes accédées.
  • Aucun overhead de pointeurs.
  • Toutes les opérations en $O(1)$.

Inconvénient :

  • Capacité fixe (sauf si on accepte la réallocation amortie comme std::vector).

Implémentation sur liste chaînée

On peut aussi implémenter une pile via une liste simplement chaînée, où le sommet correspond à la tête de la liste.

struct node {
    int data;
    struct node *next;
};

void push(struct node **top, int value) {
    struct node *n = (struct node*)malloc(sizeof(struct node));
    n->data = value;
    n->next = *top;
    *top = n;
}

int pop(struct node **top) {
    if (*top == NULL) return -1;
    struct node *tmp = *top;
    int val = tmp->data;
    *top = tmp->next;
    free(tmp);
    return val;
}

L’insertion et la suppression en tête restent en $O(1)$, mais on retrouve les inconvénients bien connus de la liste chaînée : overhead mémoire de 8 octets par nœud (pointeur next), fragmentation mémoire, et cache misses systématiques. En pratique, l’implémentation sur tableau est quasiment toujours préférable sauf contraintes très spécifiques.

Applications des piles

La pile est omniprésente en informatique :

  • Pile d’appels (call stack) : chaque appel de fonction empile un stack frame contenant les variables locales, l’adresse de retour et les registres sauvegardés. Le return dépile ce frame. C’est la raison pour laquelle une récursion infinie provoque un stack overflow.
  • Évaluation d’expressions : la notation polonaise inversée (RPN) s’évalue directement avec une pile. Pour 3 4 + 2 * : on empile 3, empile 4, dépile les deux pour calculer 7, empile 7, empile 2, dépile les deux pour calculer 14.
  • Parsing et vérification de parenthèses : pour chaque ( ou { on empile, pour chaque ) ou } on dépile et vérifie la correspondance. Si la pile est vide à la fin, l’expression est bien formée.
  • Parcours en profondeur (DFS) : la pile (explicite ou implicite via la récursion) est le mécanisme sous-jacent du DFS sur les graphes et arbres.
  • Undo/Redo : chaque action est empilée ; Ctrl+Z dépile la dernière action.

Files (Queues)

Principe FIFO

Une file (queue) fonctionne selon le principe FIFO (First In, First Out) : le premier élément inséré est le premier retiré. C’est le modèle de la file d’attente classique.

Deux opérations fondamentales :

  • enqueue : ajouter un élément en queue (tail), $O(1)$
  • dequeue : retirer l’élément en tête (head), $O(1)$
Opération :  enq(A)  enq(B)  enq(C)  deq()  deq()
File :       [A]     [A,B]   [A,B,C] [B,C]  [C]
                                      → A    → B

Implémentation sur buffer circulaire

L’implémentation naturelle d’une file repose sur le buffer circulaire que nous avons vu dans le cours précédent. On réutilise les deux indices read (head) et write (tail) pour une gestion FIFO efficace :

struct queue {
    int *data;
    int head;
    int tail;
    int size;
    int capacity;
};

struct queue *queue_new(int capacity) {
    struct queue *q = (struct queue*)malloc(sizeof(struct queue));
    q->data = (int*)malloc(sizeof(int) * capacity);
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(struct queue *q, int value) {
    if (q->size == q->capacity) return; // full
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) & (q->capacity - 1); // capacité = 2^k
    q->size++;
}

int dequeue(struct queue *q) {
    if (q->size == 0) return -1; // empty
    int val = q->data[q->head];
    q->head = (q->head + 1) & (q->capacity - 1);
    q->size--;
    return val;
}

On retrouve l’astuce du masque binaire ($C = 2^k$) pour éviter le modulo. Le champ size permet de distinguer sans ambiguïté un buffer plein d’un buffer vide (cas où head == tail dans les deux situations).

Implémentation sur tableau linéaire naïve (et ses problèmes)

Une implémentation naïve avec un simple tableau et un dequeue qui décale tous les éléments est en $O(n)$ par retrait. C’est exactement le problème que le buffer circulaire résout. De même, une implémentation sur liste simplement chaînée (avec pointeur head et tail) fonctionne en $O(1)$ pour les deux opérations, mais souffre du surcoût mémoire et de la fragmentation déjà discutés.

Deque (Double-Ended Queue)

Un deque (prononcé “deck”) généralise la file en autorisant l’insertion et la suppression aux deux extrémités :

  • push_front / push_back : $O(1)$
  • pop_front / pop_back : $O(1)$

Un deque peut donc simuler à la fois une pile et une file. L’implémentation classique repose sur un buffer circulaire avec gestion bidirectionnelle des indices. En C++, std::deque utilise une approche par blocs de mémoire contigus (un tableau de pointeurs vers des chunks de taille fixe), ce qui offre un compromis entre l’accès indexé en $O(1)$ amorti et la flexibilité d’insertion aux deux bouts.

File de priorité (Priority Queue)

Une file de priorité ne respecte plus l’ordre d’insertion mais retourne toujours l’élément de plus haute priorité. Les opérations fondamentales sont :

  • insert : ajouter un élément avec une priorité
  • extract_min (ou extract_max) : retirer l’élément de priorité extrême

L’implémentation naïve avec une liste non triée donne insert en $O(1)$ mais extract en $O(n)$. Avec une liste triée, c’est l’inverse. La bonne implémentation repose sur le tas binaire (binary heap), que nous détaillons dans la section suivante.

Applications des files

  • Ordonnancement de processus : les schedulers utilisent des files (round-robin, files multi-niveaux) pour organiser l’accès CPU.
  • Parcours en largeur (BFS) : la file est le mécanisme fondamental du BFS. On enfile les voisins du nœud courant, puis on défile le prochain nœud à explorer.
  • Buffers de communication : les files de messages inter-processus (pipes, sockets, MPMC) que nous avons vues en cours de C/Unix sont des files.
  • Impression, I/O : les requêtes d’impression ou d’E/S sont placées dans une file d’attente.