Algorithmique · Écoles d'ingénieurs — ENSIAS

Structures de données linéaires : Listes, Piles et Files

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

Les structures linéaires organisent les données de manière séquentielle.

Listes chaînées : Composées de nœuds contenant une valeur et un pointeur vers le suivant. Accès séquentiel : $O(n)$ .
Piles (Stack) : Structure LIFO (Last In, First Out). Opérations : Empiler (push) et Dépiler (pop). Complexité $O(1)$ .
Files (Queue) : Structure FIFO (First In, First Out). Opérations : Enfiler (enqueue) et Défiler (dequeue). Complexité $O(1)$ .

Méthodes à maîtriser

Insertion/Suppression : Savoir manipuler les pointeurs pour insérer un nœud dans une liste sans perdre la chaîne.
Gestion des bornes : Toujours vérifier si la structure est vide (estVide) ou pleine (pour les implémentations statiques).
Conversion : Savoir simuler une pile avec deux files ou vice-versa.

Exemples corrigés

Pile : Pour inverser une chaîne de caractères, on empile chaque lettre puis on dépile.
File : Gestion des tâches d'impression (le premier arrivé est le premier servi).

Erreurs fréquentes

Oublier de mettre à jour le pointeur NULL à la fin d'une liste.
Confusion entre LIFO (Pile) et FIFO (File).
Perdre l'adresse du premier élément (tête) lors d'une insertion.

L'essentiel du cours

Les structures linéaires organisent les données de manière séquentielle.

Listes chaînées : Composées de nœuds contenant une valeur et un pointeur vers le suivant. Accès séquentiel : $O(n)$.
Piles (Stack) : Structure LIFO (Last In, First Out). Opérations : Empiler (push) et Dépiler (pop). Complexité $O(1)$.
Files (Queue) : Structure FIFO (First In, First Out). Opérations : Enfiler (enqueue) et Défiler (dequeue). Complexité $O(1)$.

Méthodes à maîtriser

Insertion/Suppression : Savoir manipuler les pointeurs pour insérer un nœud dans une liste sans perdre la chaîne.
Gestion des bornes : Toujours vérifier si la structure est vide (estVide) ou pleine (pour les implémentations statiques).
Conversion : Savoir simuler une pile avec deux files ou vice-versa.

Exemples corrigés

Pile : Pour inverser une chaîne de caractères, on empile chaque lettre puis on dépile.
File : Gestion des tâches d'impression (le premier arrivé est le premier servi).

Erreurs fréquentes

Oublier de mettre à jour le pointeur NULL à la fin d'une liste.
Confusion entre LIFO (Pile) et FIFO (File).
Perdre l'adresse du premier élément (tête) lors d'une insertion.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Structures de données linéaires : Listes, Piles et Files

1/4

Quelle est la complexité de l'opération Enfiler dans une file implémentée par liste chaînée ?

❓ Questions fréquentes

C'est quoi la différence entre une liste chaînée et un tableau ?

Le tableau a une taille fixe et ses éléments sont contigus en mémoire.
La liste chaînée a une taille dynamique et les nœuds sont dispersés en mémoire, reliés par des pointeurs.

💡 À retenir : Le tableau est rapide pour l'accès indexé $O(1)$ , la liste est meilleure pour les insertions/suppressions $O(1)$ si on a déjà le pointeur.

Le tableau a une taille fixe et ses éléments sont contigus en mémoire.
La liste chaînée a une taille dynamique et les nœuds sont dispersés en mémoire, reliés par des pointeurs.

💡 À retenir : Le tableau est rapide pour l'accès indexé $O(1)$, la liste est meilleure pour les insertions/suppressions $O(1)$ si on a déjà le pointeur.

Kifach n7seb la complexité dyal l'insertion f liste chaînée ?

Si tu insères au début, c'est $O(1)$ car tu changes juste le pointeur de tête.
Si tu insères à une position $k$ , tu dois parcourir $k$ éléments, donc $O(k)$ .

💡 À retenir : La complexité dépend toujours de la position de l'opération.

Si tu insères au début, c'est $O(1)$ car tu changes juste le pointeur de tête.
Si tu insères à une position $k$, tu dois parcourir $k$ éléments, donc $O(k)$.

💡 À retenir : La complexité dépend toujours de la position de l'opération.

Est-ce qu'on peut utiliser une pile pour parcourir un graphe ?

Oui, le parcours en profondeur (DFS) utilise une pile (ou la récursivité qui repose sur une pile d'appels).

💡 À retenir : Pile = DFS, File = BFS.

Chno hiya l'utilité dyal "sentinelle" f liste chaînée ?

C'est un nœud fictif ajouté au début ou à la fin pour éviter de gérer les cas particuliers (liste vide ou insertion en tête).

💡 À retenir : Ça simplifie le code et évite les erreurs de segmentation.

Comment implémenter une file avec deux piles ?

Utilise pile1 pour enfiler.
Pour défiler, si pile2 est vide, transfère tout de pile1 vers pile2 et dépile pile2.

💡 À retenir : L'inversion des éléments par la deuxième pile rétablit l'ordre FIFO.

Wach momkin nkhdem b liste chaînée f l'examen ?

Oui, c'est une structure fondamentale au programme. Tu dois savoir écrire les fonctions ajouterDebut et supprimer.

💡 À retenir : Maîtrise bien la manipulation des pointeurs p->suivant.

Quelle est la complexité de dépiler dans une pile ?

C'est $O(1)$ car on accède directement au sommet de la pile sans parcourir les autres éléments.

💡 À retenir : Les opérations de base sur pile et file sont toujours en temps constant.

C'est $O(1)$ car on accède directement au sommet de la pile sans parcourir les autres éléments.

💡 À retenir : Les opérations de base sur pile et file sont toujours en temps constant.

Pourquoi on dit que la file est FIFO ?

Parce que le premier élément inséré est le premier à être traité, comme dans une file d'attente à la caisse.

💡 À retenir : FIFO = First In, First Out.

Kifach n3ref wach la liste chaînée hiya l'meilleure structure ?

Si tu as besoin d'ajouter/supprimer souvent des éléments au milieu et que la taille change tout le temps, la liste est idéale.

💡 À retenir : Évite la liste si tu as besoin d'un accès aléatoire fréquent (index).

Est-ce que la récursivité utilise une pile ?

Oui, le système utilise une "pile d'appels" (call stack) pour stocker les variables locales de chaque appel récursif.

💡 À retenir : Trop de récursivité peut causer un Stack Overflow.

C'est quoi un pointeur NULL ?

C'est une valeur spéciale qui indique qu'un pointeur ne pointe vers aucune adresse mémoire valide.

💡 À retenir : Toujours tester si (p != NULL) avant d'accéder à p->valeur.

Est-ce que la taille d'une pile est limitée ?

Si elle est implémentée avec un tableau, oui. Si elle est implémentée avec une liste chaînée, elle est limitée par la mémoire disponible.

💡 À retenir : La limite dépend de l'implémentation choisie.

✍️ Exercices type examen national

Exercice 1

Soit une liste chaînée simple dont chaque nœud contient un entier. Écrire un algorithme permettant d'inverser l'ordre des éléments de la liste.

Voir la correction détaillée : inscription gratuite

Exercice 2

On dispose d'une pile P contenant des entiers. Écrire un algorithme qui supprime toutes les occurrences d'une valeur x donnée dans la pile, en utilisant uniquement une pile auxiliaire.

Voir la correction détaillée : inscription gratuite

Exercice 3

Implémenter une file à l'aide d'une liste chaînée simple. Donnez les structures et les fonctions Enfiler et Défiler.

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Algorithmique

Introduction à l'algorithmique et complexité Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)