Algorithmes et structures de données en Rust : guide pratique

Introduction : Pourquoi Rust est idéal pour les algorithmes et structures de données

Rust combine les performances du C/C++ avec la sécurité mémoire, ce qui en fait un excellent choix pour implémenter des algorithmes et des structures de données. Grâce au système de possession (ownership) et d'emprunt (borrowing), vous pouvez créer des structures efficaces et sûres sans ramasse-miettes. Dans cet article, nous analyserons l'implémentation pratique des structures de données et algorithmes clés en Rust — de la pile à l'arbre binaire et au parcours de graphe.

Nous utiliserons uniquement la bibliothèque standard de Rust, afin que vous puissiez appliquer immédiatement le code dans vos projets. Tous les exemples se compilent et fonctionnent avec Rust 2021 edition.

1. Pile et file d'attente : structures classiques en Rust

Pile (Stack)

La pile fonctionne selon le principe LIFO (Last In, First Out). En Rust, le plus simple est d'implémenter une pile basée sur Vec :

struct Stack<T> {\n    elements: Vec<T>,\n}\n\nimpl<T> Stack<T> {\n    fn new() -> Self {\n        Stack { elements: Vec::new() }\n    }\n\n    fn push(&mut self, value: T) {\n        self.elements.push(value);\n    }\n\n    fn pop(&mut self) -> Option<T> {\n        self.elements.pop()\n    }\n\n    fn peek(&self) -> Option<&T> {\n        self.elements.last()\n    }\n\n    fn is_empty(&self) -> bool {\n        self.elements.is_empty()\n    }\n}\n\nfn main() {\n    let mut stack = Stack::new();\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    println!("Élément du dessus : {:?}", stack.peek()); // Some(30)\n    println!("Retrait : {:?}", stack.pop()); // Some(30)\n    println!("La pile est vide ? {}", stack.is_empty()); // false\n}

Avantage : Vec fournit déjà un O(1) amorti pour push/pop, et Rust garantit que la mémoire sera libérée à la sortie de la portée.

File d'attente (Queue)

La file d'attente fonctionne selon le principe FIFO (First In, First Out). Pour une implémentation efficace, utilisons VecDeque de la bibliothèque standard :

use std::collections::VecDeque;\n\nstruct Queue<T> {\n    elements: VecDeque<T>,\n}\n\nimpl<T> Queue<T> {\n    fn new() -> Self {\n        Queue { elements: VecDeque::new() }\n    }\n\n    fn enqueue(&mut self, value: T) {\n        self.elements.push_back(value);\n    }\n\n    fn dequeue(&mut self) -> Option<T> {\n        self.elements.pop_front()\n    }\n\n    fn front(&self) -> Option<&T> {\n        self.elements.front()\n    }\n\n    fn len(&self) -> usize {\n        self.elements.len()\n    }\n}\n\nfn main() {\n    let mut queue = Queue::new();\n    queue.enqueue("premier");\n    queue.enqueue("deuxième");\n    queue.enqueue("troisième");\n\n    println!("Premier dans la file : {:?}", queue.front()); // Some("premier")\n    println!("Service : {:?}", queue.dequeue()); // Some("premier")\n    println!("Longueur de la file : {}", queue.len()); // 2\n}

Important : VecDeque utilise un tampon circulaire, ce qui donne un O(1) pour l'insertion et la suppression aux deux extrémités. C'est nettement plus rapide que d'utiliser Vec pour une file d'attente.

2. Arbre binaire de recherche (BST) en Rust

L'arbre binaire de recherche est l'une des structures de données fondamentales. Implémentons-le en utilisant Box pour les types récursifs :

use std::cmp::Ordering;\n\n#[derive(Debug)]\nstruct Node<T: Ord> {\n    value: T,\n    left: Option<Box<Node<T>>>,\n    right: Option<Box<Node<T>>>,\n}\n\n#[derive(Debug)]\nstruct BinarySearchTree<T: Ord> {\n    root: Option<Box<Node<T>>>,\n}\n\nimpl<T: Ord> BinarySearchTree<T> {\n    fn new() -> Self {\n        BinarySearchTree { root: None }\n    }\n\n    fn insert(&mut self, value: T) {\n        let mut current = &mut se