Informatique · Classes prépa (CPGE) — 2ème année — TSI

Structures de données : 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

Listes : Séquences ordonnées d'éléments accessibles par index. En Python, list est dynamique.
Piles (Stack) : Structure LIFO. Opérations : push(e), pop(), is_empty(), peek().
Files (Queue) : Structure FIFO. Opérations : enqueue(e), dequeue(), is_empty().
Implémentation : En Python, on utilise list pour les piles (append/pop) et collections.deque pour les files (plus efficace en $O(1)$ pour popleft).

Méthodes à maîtriser

Conversion d'une structure à une autre (ex: vider une pile dans une file).
Utilisation de la pile pour vérifier l'équilibrage des parenthèses.
Simulation manuelle d'une séquence d'opérations sur une structure.

Exemples corrigés

Pile : S = [1, 2]; S.append(3) -> S devient [1, 2, 3]; S.pop() -> renvoie 3.
File : Q = deque([1, 2]); Q.append(3) -> Q devient [1, 2, 3]; Q.popleft() -> renvoie 1.

Erreurs fréquentes

Confondre LIFO et FIFO.
Utiliser pop(0) sur une liste Python pour simuler une file (complexité $O(n)$ au lieu de $O(1)$ ).
Oublier de vérifier si la structure est vide avant un pop ou dequeue.

L'essentiel du cours

Listes : Séquences ordonnées d'éléments accessibles par index. En Python, list est dynamique.
Piles (Stack) : Structure LIFO. Opérations : push(e), pop(), is_empty(), peek().
Files (Queue) : Structure FIFO. Opérations : enqueue(e), dequeue(), is_empty().
Implémentation : En Python, on utilise list pour les piles (append/pop) et collections.deque pour les files (plus efficace en $O(1)$ pour popleft).

Méthodes à maîtriser

Conversion d'une structure à une autre (ex: vider une pile dans une file).
Utilisation de la pile pour vérifier l'équilibrage des parenthèses.
Simulation manuelle d'une séquence d'opérations sur une structure.

Exemples corrigés

Pile : S = [1, 2]; S.append(3) -> S devient [1, 2, 3]; S.pop() -> renvoie 3.
File : Q = deque([1, 2]); Q.append(3) -> Q devient [1, 2, 3]; Q.popleft() -> renvoie 1.

Erreurs fréquentes

Confondre LIFO et FIFO.
Utiliser pop(0) sur une liste Python pour simuler une file (complexité $O(n)$ au lieu de $O(1)$).
Oublier de vérifier si la structure est vide avant un pop ou dequeue.

🌉 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 : Listes, Piles et Files

1/4

Quelle structure suit le principe FIFO ?

❓ Questions fréquentes

C'est quoi la différence entre une liste et une pile ?

Une liste est une structure d'accès direct (via index).
Une pile est une structure à accès restreint (LIFO).
On ne peut accéder qu'au sommet de la pile.

💡 À retenir : La liste est un conteneur général, la pile est une contrainte d'accès.

Chno hiya l'far9 bin l'pile o l'file f l'khedma?

Pile (LIFO) : dakchi li dkhal l'kher howa li kikhrej l'oul.
File (FIFO) : dakchi li dkhal l'oul howa li kikhrej l'oul.

💡 À retenir : Pile = Pile d'assiettes, File = File d'attente.

Est-ce qu'on peut utiliser une liste pour faire une file ?

Oui, mais ce n'est pas optimal. list.pop(0) décale tous les éléments, ce qui coûte $O(n)$ . Utilisez collections.deque.

💡 À retenir : Pour les files, deque est toujours préférable.

Oui, mais ce n'est pas optimal. list.pop(0) décale tous les éléments, ce qui coûte $O(n)$. Utilisez collections.deque.

💡 À retenir : Pour les files, deque est toujours préférable.

Kifach n7seb la complexité dyal l'operation pop() f l'pile?

Si on utilise une liste Python comme pile, pop() sur le dernier élément est $O(1)$ .
C'est une opération en temps constant car il n'y a pas de décalage.

💡 À retenir : pop() sur une pile est toujours $O(1)$ .

Si on utilise une liste Python comme pile, pop() sur le dernier élément est $O(1)$.
C'est une opération en temps constant car il n'y a pas de décalage.

💡 À retenir : pop() sur une pile est toujours $O(1)$.

Pourquoi on utilise des structures de données au lieu de variables simples ?

Pour organiser les données logiquement.
Pour optimiser les accès et les manipulations.
Pour gérer des volumes de données dynamiques.

💡 À retenir : La structure définit la performance de l'algorithme.

Chno hiya l'operation l'li katkhlina nchofo l'element l'fou9ani f l'pile bla man7eydo?

C'est l'opération peek() ou top(). En Python, on accède simplement à S[-1].

💡 À retenir : peek() ne modifie pas la structure.

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

En théorie non, en pratique elle est limitée par la mémoire vive (RAM) disponible.

💡 À retenir : La limite est la mémoire du système.

Comment savoir si une pile est vide ?

On vérifie si sa taille est égale à 0 ou si len(S) == 0.

💡 À retenir : Toujours tester is_empty avant pop.

Est-ce que le parcours d'une pile est possible ?

Oui, mais il faut dépiler tous les éléments pour les voir, ce qui détruit la pile.

💡 À retenir : Pour conserver la pile, il faut la reconstruire.

Pourquoi popleft() est plus rapide que pop(0) ?

pop(0) sur une liste force le déplacement de tous les autres éléments. popleft() sur une deque est une opération sur une liste chaînée.

💡 À retenir : deque est optimisé pour les extrémités.

Est-ce que le programme officiel demande de coder les structures de zéro ?

Non, on utilise les structures natives de Python ou les bibliothèques standards.

💡 À retenir : Maîtriser l'usage est plus important que l'implémentation bas niveau.

Kifach n3ref wach l'algorithme dyali khdam mzyan?

Vérifie les cas limites (pile vide, pile avec 1 élément).
Trace l'état de la structure à chaque étape.

💡 À retenir : Le test de la pile vide est crucial.

✍️ Exercices type examen national

Exercice 1

Soit une pile P initialement vide. On effectue les opérations suivantes : push(5), push(10), pop(), push(2), pop(), push(8). Quel est l'état final de la pile ?

Voir la correction détaillée : inscription gratuite

Exercice 2

Écrire une fonction Python inverser_file(F) qui utilise une pile pour inverser l'ordre des éléments d'une file.

Voir la correction détaillée : inscription gratuite

Exercice 3

Soit une expression parenthésée "(())()". Proposer un algorithme utilisant une pile pour vérifier si les parenthèses sont bien équilibrées.

Voir la correction détaillée : inscription gratuite

Un prof de Informatique 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 Informatique

Révision et approfondissement du langage Python Complexité des algorithmes Structures de données : Arbres binaires et Arbres binaires de recherche Algorithmes de tri et de recherche Graphes : Représentation et parcours (BFS, DFS)Programmation dynamique Bases de données relationnelles et langage SQL Architecture des ordinateurs et systèmes d'exploitation