Structures de Données Essentielles: Piles, Files, Listes

Correction :

1. Une Pile :

   Une pile est une structure de données linéaire qui suit le principe LIFO (Last-In, First-Out). Le dernier élément ajouté est le premier à être retiré. Imagine une pile d'assiettes : tu ajoutes des assiettes sur le dessus, et tu retires toujours celle du dessus.

   Exemple d'application : La gestion des appels de fonctions dans un programme (pile d'exécution), l'historique "annuler/rétablir" d'un éditeur de texte, la vérification de parenthèses équilibrées.

2. Une File :

   Une file est une structure de données linéaire qui suit le principe FIFO (First-In, First-Out). Le premier élément ajouté est le premier à être retiré. Imagine une file d'attente à la caisse : le premier client arrivé est le premier servi.

   Exemple d'application : La gestion des tâches dans un système d'exploitation, l'impression de documents (spool d'impression), les requêtes réseau en attente, les algorithmes de parcours en largeur (BFS).

3. Une Liste Chaînée (simple) :

   Une liste chaînée est une collection ordonnée d'éléments (appelés nœuds), où chaque nœud contient une donnée et une référence (ou pointeur) vers le nœud suivant. Contrairement aux tableaux, les éléments ne sont pas stockés de manière contiguë en mémoire. On peut parcourir la liste en suivant les références d'un nœud à l'autre.

   Exemple d'application : L'implémentation de piles et de files, la gestion de listes de lecture musicales, la représentation de polynômes, les systèmes de gestion de mémoire.

Point méthode : Comprendre la différence entre LIFO et FIFO est crucial. LIFO pour "pile" (stack), FIFO pour "file" (queue).

Correction :

On représente la pile verticalement, le sommet étant le dernier élément.

1. Empiler 'A' :

   [A]
   

2. Empiler 'B' :

   [B]
   [A]
   

3. Dépiler : 'B' est retiré.

   [A]
   

4. Empiler 'C' :

   [C]
   [A]
   

5. Empiler 'D' :

   [D]
   [C]
   [A]
   

6. Dépiler : 'D' est retiré.

   [C]
   [A]
   

Astuce : Visualise toujours le sommet de la pile pour savoir quel élément sera dépilé. Le principe LIFO est la clé.

Correction :

On représente la file horizontalement, le début (tête) à gauche et la fin (queue) à droite.

1. Enfiler 'X' :

   [X]
   

2. Enfiler 'Y' :

   [X, Y]
   

3. Défiler : 'X' est retiré (le premier arrivé).

   [Y]
   

4. Enfiler 'Z' :

   [Y, Z]
   

5. Enfiler 'W' :

   [Y, Z, W]
   

6. Défiler : 'Y' est retiré (le premier arrivé parmi les restants).

   [Z, W]
   

Astuce : Pense à la file d'attente d'une caisse. Le premier qui arrive est le premier à partir. Le principe FIFO est essentiel ici.

Correction :

Pour parcourir une liste chaînée, tu dois commencer par le premier nœud (la tête de la liste) et suivre les pointeurs de nœud en nœud jusqu'à atteindre NULL.

PROCEDURE AfficherListe(tete_liste)
 nœud_actuel = tete_liste
 TANT QUE nœud_actuel EST NON_NULL FAIRE
 AFFICHER nœud_actuel.valeur
 nœud_actuel = nœud_actuel.suivant
 FIN TANT QUE
FIN PROCEDURE

Point méthode : Le parcours de liste chaînée est un concept fondamental. Il est important de ne pas oublier d'avancer le pointeur nœud_actuel pour éviter une boucle infinie.

Correction :

Une pile peut être facilement implémentée à l'aide d'un tableau dynamique où l'on ajoute et retire toujours à la fin.

CLASSE Pile:
 ATTRIBUT tableau_interne : liste vide

 PROCEDURE empiler(element):
 AJOUTER element À LA FIN de tableau_interne
 FIN PROCEDURE

 PROCEDURE depiler():
 SI est_vide() ALORS
 AFFICHER "Erreur: Pile vide"
 RETOURNE NULL // Ou lever une exception
 SINON
 RETOURNE ET SUPPRIMER LE DERNIER élément de tableau_interne
 FIN SI
 FIN PROCEDURE

 FONCTION est_vide():
 RETOURNE VRAI SI tableau_interne EST VIDE, FAUX SINON
 FIN FONCTION

 FONCTION sommet():
 SI est_vide() ALORS
 RETOURNE NULL
 SINON
 RETOURNE LE DERNIER élément de tableau_interne
 FIN SI
 FIN FONCTION
FIN CLASSE

Astuce : En Python, tu utiliserais append() pour empiler, pop() pour dépiler, et len() == 0 pour vérifier si la pile est vide. C'est l'un des moyens les plus simples d'implémenter une pile.

Correction :

L'implémentation d'une file avec un tableau dynamique est un peu plus délicate qu'une pile. Si tu utilises pop() au début du tableau pour defiler(), cela peut être coûteux en performance car tous les éléments doivent être décalés. Cependant, pour cet exercice en pseudo-code, on acceptera cette approche simple.

CLASSE File:
 ATTRIBUT tableau_interne : liste vide

 PROCEDURE enfiler(element):
 AJOUTER element À LA FIN de tableau_interne
 FIN PROCEDURE

 PROCEDURE defiler():
 SI est_vide() ALORS
 AFFICHER "Erreur: File vide"
 RETOURNE NULL
 SINON
 RETOURNE ET SUPPRIMER LE PREMIER élément de tableau_interne
 FIN SI
 FIN PROCEDURE

 FONCTION est_vide():
 RETOURNE VRAI SI tableau_interne EST VIDE, FAUX SINON
 FIN FONCTION

 FONCTION premier():
 SI est_vide() ALORS
 RETOURNE NULL
 SINON
 RETOURNE LE PREMIER élément de tableau_interne
 FIN SI
 FIN FONCTION
FIN CLASSE

Point méthode : Bien que fonctionnelle, l'opération supprimer le premier élément d'un tableau dynamique peut avoir une complexité de $O(N)$ car elle nécessite de décaler tous les autres éléments. Pour une file plus performante, on utiliserait souvent une liste chaînée ou un tableau circulaire.

Correction :

Ce problème est un cas d'école pour l'utilisation des piles. L'idée est d'empiler les parenthèses ouvrantes et de dépiler quand une parenthèse fermante correspond. Si la pile est vide à la fin et qu'aucune incohérence n'a été trouvée, l'expression est équilibrée.

FONCTION SontParenthèsesÉquilibrées(expression):
 pile = CREER_PILE_VIDE()
 parenthèses_ouvrantes = "([{"
 parenthèses_fermantes = ")]}"
 paires_parenthèses = {')': '(', ']': '[', '}': '{'}

 POUR CHAQUE caractère DANS expression FAIRE
 SI caractère EST DANS parenthèses_ouvrantes ALORS
 empiler(pile, caractère)
 SINON SI caractère EST DANS parenthèses_fermantes ALORS
 SI est_vide(pile) ALORS
 RETOURNE FAUX // Une parenthèse fermante sans parenthèse ouvrante correspondante
 FIN SI
 dernier_ouvrant = depiler(pile)
 SI dernier_ouvrant N'EST PAS paires_parenthèses[caractère] ALORS
 RETOURNE FAUX // Non-correspondance
 FIN SI
 FIN SI
 FIN POUR

 RETOURNE est_vide(pile) // Vrai si toutes les parenthèses ont été appariées
FIN FONCTION

Point méthode : L'utilisation d'un dictionnaire (ou map) pour stocker les paires de parenthèses est une approche élégante et efficace.

Correction :

L'exploration par niveaux est exactement ce que le Parcours en Largeur (BFS - Breadth-First Search) fait, et une file est l'outil parfait pour cela.

Voici l'explication conceptuelle :

1. Initialisation : Tu commences avec la personne de départ. Tu l'ajoutes à une file (c'est la première personne à "visiter") et tu la marques comme "visitée" pour ne pas la traiter plusieurs fois.
2. Boucle d'exploration : Tant que la file n'est pas vide :
   • Tu défiles une personne de la file (c'est la personne actuelle que tu explores).
   • Tu regardes tous les amis de cette personne (ses voisins dans le réseau).
   • Pour chaque ami :
     • Si cet ami n'a pas encore été visité, tu l'ajoutes à la file (pour le visiter plus tard) et tu le marques comme "visitée".
3. Résultat : En utilisant une file, tu t'assures que toutes les personnes à distance 1 (amis directs) sont ajoutées à la file et traitées avant que tu ne commences à traiter les personnes à distance 2 (amis d'amis), et ainsi de suite. Cela garantit un parcours "par couches" ou "par niveaux".

Astuce : La file maintient l'ordre de découverte, ce qui est essentiel pour un parcours en largeur. Sans elle, tu pourrais te perdre dans une branche du réseau avant d'explorer les autres.

Correction :

Cet exercice est complexe car il faut penser de manière récursive à la fois pour insérer un élément au fond et pour inverser la pile.

FONCTION est_vide(pile): // Supposons cette fonction disponible
 // .
FONCTION depiler(pile): // Supposons cette fonction disponible
 // .
PROCEDURE empiler(pile, element): // Supposons cette fonction disponible
 // .

PROCEDURE insérer_au_fond(pile, element_a_inserer):
 SI est_vide(pile) ALORS
 empiler(pile, element_a_inserer)
 SINON
 temp = depiler(pile)
 insérer_au_fond(pile, element_a_inserer)
 empiler(pile, temp)
 FIN SI
FIN PROCEDURE

PROCEDURE inverser_pile(pile):
 SI NON est_vide(pile) ALORS
 element_du_sommet = depiler(pile)
 inverser_pile(pile) // Inverser le reste de la pile
 insérer_au_fond(pile, element_du_sommet) // Mettre l'ancien sommet au fond
 FIN SI
FIN PROCEDURE

Astuce : C'est un excellent exemple de la puissance de la récursion pour simuler des structures de données. La pile d'appels de fonctions agit comme une pile auxiliaire implicite.

Correction :

La liste doublement chaînée ajoute un pointeur "précédent" à chaque nœud, ce qui permet un parcours dans les deux sens et simplifie certaines opérations comme la suppression.

CLASSE Nœud:
 ATTRIBUT valeur
 ATTRIBUT précédent : Nœud (pointeur vers le Nœud précédent)
 ATTRIBUT suivant : Nœud (pointeur vers le Nœud suivant)

 CONSTRUCTEUR Nœud(valeur):
 CECI.valeur = valeur
 CECI.précédent = NULL
 CECI.suivant = NULL
 FIN CONSTRUCTEUR
FIN CLASSE

CLASSE ListeDoublementChaînée:
 ATTRIBUT tête : Nœud (premier Nœud de la liste)
 ATTRIBUT queue : Nœud (dernier Nœud de la liste)

 CONSTRUCTEUR ListeDoublementChaînée():
 CECI.tête = NULL
 CECI.queue = NULL
 FIN CONSTRUCTEUR

 PROCEDURE insérer_après(nœud_existant, nouvelle_valeur):
 SI nœud_existant EST NULL ALORS
 AFFICHER "Erreur: Le nœud existant ne peut pas être NULL."
 RETOUR
 FIN SI

 nouveau_nœud = Nœud(nouvelle_valeur)

 nouveau_nœud.suivant = nœud_existant.suivant
 nouveau_nœud.précédent = nœud_existant

 SI nœud_existant.suivant EST NON_NULL ALORS
 nœud_existant.suivant.précédent = nouveau_nœud
 SINON // Si nœud_existant était la queue
 CECI.queue = nouveau_nœud
 FIN SI

 nœud_existant.suivant = nouveau_nœud

 FIN PROCEDURE

 // Pour l'exemple, ajoutons une fonction d'ajout en fin pour initialisation
 PROCEDURE ajouter_en_fin(valeur):
 nouveau_nœud = Nœud(valeur)
 SI CECI.tête EST NULL ALORS
 CECI.tête = nouveau_nœud
 CECI.queue = nouveau_nœud
 SINON
 CECI.queue.suivant = nouveau_nœud
 nouveau_nœud.précédent = CECI.queue
 CECI.queue = nouveau_nœud
 FIN SI
 FIN PROCEDURE
FIN CLASSE

Point méthode : L'ajout ou la suppression dans une liste doublement chaînée implique de manipuler deux pointeurs (précédent et suivant) pour chaque nœud impacté, ce qui peut être un peu plus délicat que pour une liste simple. Attention aux cas limites : insertion en début, en fin, et sur une liste vide.