Aller au contenu principal

Piles et files

#Piles et files

Les piles et les files sont des structures de données fondamentales qui organisent les éléments selon des principes spécifiques d'ajout et de retrait.

#Piles (Stack)

Une pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier à être retiré.

#Opérations principales

  • push(element) : Ajouter un élément au sommet de la pile
  • pop() : Retirer et retourner l'élément du sommet
  • peek()/top() : Consulter l'élément du sommet sans le retirer
  • is_empty() : Vérifier si la pile est vide

#Animation interactive

Pour mieux comprendre le fonctionnement d'une pile, voici une animation interactive qui illustre les opérations de push et pop :

A
B
Sommet
Pile initialisée avec 2 éléments
Étape 1 / 1 | Taille: 2

#Implémentation en Python

pythonpython
1class Pile:2    def __init__(self):3        self.elements = []4    5    def push(self, element):6        self.elements.append(element)7    8    def pop(self):9        if self.is_empty():10            raise IndexError("Pile vide")11        return self.elements.pop()12    13    def peek(self):14        if self.is_empty():

#Files (Queue)

Une file suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier à être retiré.

#Opérations principales

  • enqueue(element) : Ajouter un élément à la fin de la file
  • dequeue() : Retirer et retourner l'élément du début
  • front() : Consulter l'élément du début sans le retirer
  • is_empty() : Vérifier si la file est vide

#Animation interactive

File initialisée avec 0 éléments
Étape 1 / 1 | Taille: 0

#Implémentation en Python

pythonpython
1from collections import deque2 3class File:4    def __init__(self):5        self.elements = deque()6    7    def enqueue(self, element):8        self.elements.append(element)9    10    def dequeue(self):11        if self.is_empty():12            raise IndexError("File vide")13        return self.elements.popleft()14

#Exercice : Vérification de parenthèses équilibrées

Implémentez un algorithme qui utilise une pile pour vérifier si une chaîne de caractères contient des parenthèses correctement équilibrées.

#Instructions

  1. Utilisez une pile pour suivre les parenthèses ouvertes.
  2. Pour chaque parenthèse fermante, vérifiez qu'elle correspond à la dernière parenthèse ouverte.
  3. La chaîne est équilibrée si toutes les parenthèses sont correctement appariées et que la pile est vide à la fin.

#Exemple de code

pythonpython
1class Pile:2    def __init__(self):3        self.elements = []4    5    def push(self, element):6        self.elements.append(element)7    8    def pop(self):9        if self.is_empty():10            raise IndexError("Pile vide")11        return self.elements.pop()12    13    def peek(self):14        if self.is_empty():

#Cas d'usage

#Piles

  • Appels de fonctions : La pile d'appels gère les fonctions actives
  • Évaluation d'expressions : Conversion et évaluation d'expressions infixées
  • Backtracking : Algorithmes de parcours avec retour en arrière
  • Annuler/Rétablir : Historique des actions dans les éditeurs

#Files

  • Ordonnancement : Files d'attente dans les systèmes d'exploitation
  • Breadth-First Search : Parcours en largeur dans les graphes
  • Buffering : Gestion de flux de données
  • Impressions : File d'impression dans les systèmes