Structures de données : piles, files, dictionnaires

Introduction

Les structures de données sont des éléments fondamentaux en informatique qui permettent de stocker et d'organiser les données de manière efficace. Comprendre ces structures est essentiel pour résoudre des problèmes complexes et optimiser les performances des algorithmes. Dans ce chapitre, nous allons explorer trois types de structures de données : les piles, les files et les dictionnaires, en illustrant leur utilité à travers des exemples concrets et des exercices pratiques.

Piles

Une pile est une structure de données qui fonctionne selon le principe du dernier entré, premier sorti (LIFO). Cela signifie que le dernier élément ajouté à la pile est le premier à en être retiré. Les piles sont souvent utilisées dans des situations où il est nécessaire de revenir en arrière, comme dans les appels de fonctions ou l'annulation d'actions. Elles sont également employées dans des algorithmes comme le parcours en profondeur des graphes.

Exemple concret : gestion des appels de fonction

Lorsqu'une fonction est appelée dans un programme, son état (variables locales, adresse de retour) est sauvegardé dans une pile. Par exemple, si une fonction A appelle une fonction B, puis B appelle C, l'état de A est sauvegardé avant que B ne soit exécutée. Si C termine, l'état de B est restauré, puis celui de A. Cela permet de gérer efficacement les retours de fonction.

Prenons un exemple chiffré :

• Appel de A : état de A sauvegardé dans la pile.


• Appel de B : état de B sauvegardé dans la pile.


• Appel de C : état de C sauvegardé dans la pile.

Lorsque C se termine, l'état de B est restauré, puis celui de A. Cela peut être visualisé comme suit :

```
Pile :

C (état)

B (état)

A (état)

```

#### Mini-exercice : Suivi d'appels de fonction
Considérons le code suivant :
```python
def A():
print("A")
B()

def B():
print("B")
C()

def C():
print("C")

A()
```