Piles et files en C

Les piles et les files sont des structures de données linéaires utilisées pour stocker et gérer des données.

Dans cette leçon, vous apprendrez :

• Comment fonctionnent les piles (LIFO - dernier entré, premier sorti).
• Comment fonctionnent les files (FIFO - premier entré, premier sorti).
• Comment implémenter des piles et des files en C.

Qu’est-ce qu’une pile ?

Une pile suit le principe dernier entré, premier sorti (LIFO).

Opérations :

• Empiler - Ajouter un élément au sommet.
• Dépiler - Retirer l’élément au sommet.
• Consulter - Afficher l’élément au sommet sans le retirer.

Exemple : implémenter une pile

Ce programme montre les opérations sur une pile à l’aide d’un tableau.

#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
    }
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

int main() {
    push(10);
    push(20);
    printf("Popped: %d\n", pop());
    return 0;
}

Qu’est-ce qu’une file ?

Une file suit le principe premier entré, premier sorti (FIFO).

Opérations :

• Enfiler - Ajouter un élément à la fin.
• Défiler - Retirer un élément au début.
• Consulter - Afficher l’élément au début sans le retirer.

Exemple : implémenter une file

Ce programme montre les opérations sur une file à l’aide d’un tableau.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
    }
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
        return -1;
    } else {
        return queue[front++];
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

File circulaire

Une file circulaire surmonte les limites d’une file classique en réutilisant les espaces vides.

Les opérations restent les mêmes, mais parcourent le tableau de manière circulaire.

Exemple : file circulaire

Ce programme montre l’implémentation d’une file circulaire.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        rear = (rear + 1) % MAX;
        queue[rear] = value;
    }
}

int dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return -1;
    }
    int data = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return data;
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

Applications des piles et des files

Les piles sont utilisées pour :

• La gestion des appels de fonctions (récursivité).
• Les opérations d’annulation et de rétablissement.
• L’évaluation des expressions.

Les files sont utilisées pour :

• La planification des tâches dans les systèmes d’exploitation.
• La gestion des requêtes dans les serveurs web.
• Le transfert de données dans les réseaux.

Résumé

Dans cette leçon, vous avez appris :

• Comment fonctionnent les piles et les files.
• Comment implémenter les opérations sur les piles et les files.
• Les applications des piles et des files.

Nous allons maintenant découvrir les arbres et les graphes en C !