Programmation C avancée
Cours: 2ème Année
CyclePréparatoire
Annéeuniversitaire:
2025-2026
Pr. Meryem AMANE
[Link]@[Link]
1
Mise en situation 88
diffèrent de certaines manières d’organisation
gestion des conteneurs
La structure de données qui implémente LIFO est la pile. La structure de données qui implémente FIFO est la file d'attente.
Pile(stack) File (Queue)
Les Piles et Files 89
Une pile est une structure de données linéaires auxquelles on accède dans l'ordre inverse ou on les a insérées (Last
Input, First Ouput: LIFO ou FILO (First In Last Out)), c’est-à-dire que l'insertion et la suppression se font par le
haut. La pile est une liste ordonnée sans fin d’éléments (Une pile de livres, Une pile d’assiettes),
On ne peut accéder qu'au sommet de la pile. Les opérations (primitives) sur une pile sont les suivantes:
empiler(Push): rajoute un élément sur la pile.
dépiler(Pop): renvoie la valeur de l'élément au sommet de la pile et le supprime.
vider: renvoie VRAI si et seulement si la pile est vide
E H
n G Sortie
t F
Sortie A B C D E F G H Entrée E
r D
é C
B
e A
FILE ou FIFO (Queue)
PILE ou LIFO (STACK)
Les Piles et Files 90
Dans une file, les éléments sont ajoutés en queue et supprimés en tête (First Input First Ouput).
Ils sont donc traités dans l'ordre d’arrivée. On retrouve les opérations suivantes comme pour les piles:
ajouter: rajoute un élément en queue de file.
supprimer: renvoie la valeur de l’élément en tête de la file et le supprime.
vider: renvoie VRAI si et seulement si la file est vide
E H
n G Sortie
t F
Sortie A B C D E F G H Entrée E
r D
é C
B
e A
FILE ou FIFO (Queue)
PILE ou LIFO (STACK)
Les Piles et Files 91
Une file d'attente est une structure de données linéaire dans Une pile est une structure de données linéaire dans laquelle les
laquelle les éléments ne peuvent être insérés que d'un côté éléments ne peuvent être insérés et supprimés que d'un côté de la
de la liste appelée arrière , et les éléments ne peuvent être liste, appelé le haut .
supprimés que de l'autre côté appelé l' avant . La structure Une pile suit le principe LIFO (Last In First Out), c’est-à-dire que
des données de la file d'attente suit le principe FIFO (First l’élément inséré en dernier est le premier élément à sortir.
In First Out), c'est-à-dire que l'élément inséré en premier L’insertion d'un élément dans la pile est appelée opération push, et
dans la liste est le premier élément à supprimer de la liste. la suppression d'un élément de la pile est appelée opération pop.
L'insertion d'un élément dans une file d' attente est appelé Dans la pile, nous gardons toujours une trace du dernier élément
un enqueue fonctionnement et la suppression d'un élément présent dans la liste avec un pointeur appelé top . vrai si la pile est
est appelé un dequeue opération. En file d'attente, nous vide, sinon faux.
maintenons toujours deux pointeurs, l'un pointant vers
l'élément qui a été inséré en premier et toujours présent dans
la liste avec le recto-pointeur et le deuxième pointeur
pointant vers l'élément inséré en dernier avec le pointeur
arrière .
Les piles et les files: Applications 92
Les piles Les files
• Les piles sont utilisées pour passer des paramètres à Les files sont utilisées :
une fonction ou pour stocker des variables locales. • Ordonnancement du traitement des achats d’un magasin
en ligne.
• Parcours en profondeur (DFS: Depth-First Search)
• Gestion des ordres reçus par un système embarqué.
• Inversion de nombre
• File d’attente d’une imprimante.
• Opérations d’annulations dans les éditeurs de texte.
• Traitement de signal : implémentation d’un retard
• etc
numérique.
Implémentation des Piles/Files à base des LSC (1) 93
Tout d’abord, nous allons définir une structure pour représenter un nœud dans la liste chaînée :
struct Node {
int value;
struct Node* next;
};
La structure Node contient un entier value qui représente la valeur stockée dans le nœud et un pointeur next qui
pointe vers le prochain nœud dans la liste.
Ensuite, nous définissons la structure pour la pile :
struct Stack {
struct Node* top;
};
La structure Stack contient un pointeur top qui pointe vers le sommet de la pile.
Implémentation des Piles/Files à base des LSC (2) 94
Fonction pour initialiser une pile vide :
void init_stack(struct Stack* stack) {
stack->top = NULL;
}
La fonction init_stack prend un pointeur vers une structure Stack et initialise le pointeur top à NULL, ce qui signifie
que la pile est vide.
La fonction pour empiler un élément sur la pile est la suivante :
void push(struct Stack* stack, int value) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->next = stack->top;
stack->top = node;
}
Implémentation des Piles/Files à base des LSC (3) 95
La fonction push prend un pointeur vers une structure Stack et une valeur entière value. Elle crée un nouveau nœud
avec la valeur value, met le pointeur next du nœud à stack->top et met à jour le pointeur top de la pile pour pointer
vers le nouveau nœud.
La fonction pour dépiler un élément de la pile est la suivante :
int pop(struct Stack* stack) {
if (stack->top == NULL) { La fonction pop prend un pointeur vers une structure Stack et
printf("Stack is empty"); retire et renvoie la valeur du sommet de la pile. Si la pile est
exit(1); vide, la fonction affiche un message d'erreur et quitte le
} programme avec exit(1). La fonction crée une variable value
int value = stack->top->value;
pour stocker la valeur du sommet de la pile, crée un pointeur
struct Node* temp = stack->top;
stack->top = stack->top->next; temporaire temp pour stocker l'adresse du sommet de la pile,
free(temp); met à jour le pointeur top de la pile pour pointer vers le nœud
return value; suivant et libère la mémoire allouée pour le nœud supprimé.
}
Implémentation des Piles/Files à base des LSC (3) 96
Pour la structure file:
struct Queue {
struct Node* front;
struct Node* rear;
};
La structure Queue contient deux pointeurs, front et rear, qui pointent respectivement vers le début et la fin de la file.
La fonction pour initialiser une file vide est la suivante :
struct Queue* createQueue() {
struct Queue* newQueue = (struct Queue*)malloc(sizeof(struct Queue));
newQueue->front = newQueue->rear = NULL;
return newQueue;
}
Implémentation des Piles/Files à base des LSC (4) 97
Fonction pour créer un nouveau nœud avec une donnée et un pointeur vers le noeud suivant initialisé à
NULL
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
Fonction pour ajouter un élément à la fin de la file:
void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) { // si la file est vide
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}
Implémentation des Piles/Files à base des LSC (4) 98
Fonction pour retirer le premier élément de la file et renvoyer sa valeur
int dequeue(struct Queue* queue) {
if (queue->front == NULL) { // vérifie si la file est vide
printf("La file est vide.\n");
return -1;
}
struct Node* temp = queue->front;
int dequeued = temp->data;
queue->front = queue->front->next;
if (queue->front == NULL) { // si la file est maintenant vide
queue->rear = NULL;
}
free(temp);
return dequeued;
}
int dequeue(struct Queue* queue) {
if (queue->front == NULL) {
printf("La file est vide.\n");
return -1; }
// Sauvegarde un pointeur vers le premier nœud (front)
struct Node* temp = queue->front;
// Sauvegarde la valeur contenue dans ce nœud
int dequeued = temp->data;
// Avance le pointeur front vers le nœud suivant
queue->front = queue->front->next;
// Si après le retrait, la file devient vide (front == NULL),
// on met aussi rear à NULL pour garder la cohérence de la file
if (queue->front == NULL) {
queue->rear = NULL;
}
// Libère la mémoire du nœud supprimé
free(temp);
// Retourne la valeur de l’élément qui vient d’être supprimé
return dequeued;
}
Implémentation des Piles/Files à base des LSC (5) 99
Fonction pour afficher les éléments de la file
void printQueue(struct Queue* queue) {
struct Node* currentNode = queue->front;
while (currentNode != NULL) {
printf("%d ", currentNode->data);
currentNode = currentNode->next;
}
printf("\n");
}
Piles Versus Files 100
Pile File
Les objets sont insérés et retirés de différentes
Les objets sont insérés et supprimés à la même fin.
extrémités.
Dans les piles, un seul pointeur est utilisé. Il pointe vers Dans les files, deux pointeurs différents sont utilisés
le haut de la pile. pour les extrémités; le tète et la fin.
Dans les piles, le dernier objet inséré est le premier à Dans les files, l’objet inséré en premier est le premier
sortir. qui sera supprimé.
Les piles suivent l’ordre Last In First Out (LIFO) Les files suivent l’ordre First In First Out (FIFO)
Les opérations de pile s’appellent Empiler et Dépiler. Les opérations de file sont appelées Enfiler et Défiler.
Les piles sont visualisées sous forme de collections Les files sont visualisées sous forme de collections
verticales. horizontales.
Différences : LSC, PILE et FILE 101
Les listes simplement chaînées, les piles et les files sont des structures de données couramment utilisées en
informatique pour stocker et organiser des éléments. Voici les différences clés entre ces trois structures :
1. Liste simplement chaînée : une liste simplement chaînée est une collection d'éléments connectés les uns aux
autres à l'aide de liens de pointeur. Chaque élément de la liste contient une référence à l'élément suivant. Cette
structure permet l'insertion et la suppression d'éléments à n'importe quelle position de la liste. La recherche d'un
élément dans une liste simplement chaînée nécessite de parcourir la liste élément par élément jusqu'à ce que
l'élément souhaité soit trouvé.
2. Pile : une pile est une structure de données LIFO (dernier entré, premier sorti) qui permet l'ajout et la
suppression d'éléments uniquement à partir du sommet de la pile. Les éléments sont empilés les uns sur les
autres et retirés dans l'ordre inverse. Les piles sont souvent utilisées pour implémenter des algorithmes de
traitement de données tels que la récursivité.
3. File : une file est une structure de données FIFO (premier entré, premier sorti) qui permet l'ajout d'éléments à la
fin de la file et la suppression d'éléments à partir du début de la file. Les éléments sont organisés dans l'ordre
dans lequel ils ont été ajoutés à la file et sont retirés dans le même ordre. Les files sont souvent utilisées pour
implémenter des algorithmes de traitement de données tels que le parcours en largeur d'un graphe
Conclusion 102
En résumé :
Une liste simplement chaînée est une collection d'éléments connectés les uns aux autres,
Une pile est une structure de données LIFO qui permet l'ajout et la suppression d'éléments à partir du sommet
de la pile,
Une file est une structure de données FIFO qui permet l'ajout et la suppression d'éléments à partir du début de
la file.
Chacune de ces structures de données convient mieux à des situations particulières en fonction des besoins de
l'application.
Exercice d’application :
Contexte :
Un guichet administratif reçoit des citoyens venus effectuer des
démarches (carte d’identité, passeport, etc.).
Les citoyens sont servis dans l’ordre d’arrivée → c’est donc une file
(queue) typique.
Le programme doit permettre de :
• Enregistrer une personne qui arrive au guichet.
• Servir la première personne dans la file.
• Afficher la liste des personnes en attente.
// ===============================
// Définition d'une personne
typedef struct {
// ===============================
Node* front; // tête (début)
typedef struct {
Node* rear; // queue (fin)
int id;
} File;
char nom[30];
char service[30];
} Personne;
Exercice d’application
void initialiserFile(File* f); // Initialise une file vide
int estVide(File* f); // Vérifie si la file est
vide
void enfiler(File* f, Personne p); // Ajoute une personne à la
fin de la file
Personne defiler(File* f); // Retire la première
personne de la file
void afficherFile(File* f); // Affiche toutes les
personnes en attente