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

Algorithmes et structures de données en TypeScript : de la théorie à la pratique

La compréhension des algorithmes et des structures de données est le fondement qui distingue un développeur expérimenté d'un débutant. TypeScript, grâce à son typage strict et à ses fonctionnalités modernes, permet d'écrire un code fiable et lisible pour résoudre des problèmes classiques. Dans cet article, nous analyserons les structures de données et les algorithmes clés à l'aide d'exemples pratiques utilisant TypeScript. Vous apprendrez à implémenter une pile, une file, une recherche binaire et un tri rapide, et vous découvrirez également les bases du travail avec les graphes.

1. Structures de données de base : Pile et File

La pile et la file sont des structures simples mais extrêmement utiles. La pile fonctionne selon le principe LIFO (Last In, First Out), tandis que la file fonctionne selon le principe FIFO (First In, First Out). En TypeScript, il est pratique de les implémenter à partir d'un tableau en utilisant des génériques pour la sécurité des types.

Implémentation de la Pile (Stack)

class Stack<T> {\n    private items: T[] = [];\n\n    push(item: T): void {\n        this.items.push(item);\n    }\n\n    pop(): T | undefined {\n        return this.items.pop();\n    }\n\n    peek(): T | undefined {\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Exemple d'utilisation\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

Implémentation de la File (Queue)

class Queue<T> {\n    private items: T[] = [];\n\n    enqueue(item: T): void {\n        this.items.push(item);\n    }\n\n    dequeue(): T | undefined {\n        return this.items.shift();\n    }\n\n    front(): T | undefined {\n        return this.items[0];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Exemple d'utilisation\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

Notez que la méthode intégrée shift() a une complexité O(n), donc pour de grands volumes de données, il est préférable d'implémenter une file basée sur une liste chaînée.

2. Algorithmes de recherche : Linéaire et Binaire

La recherche d'éléments est l'une des opérations les plus courantes. La recherche linéaire est simple mais lente sur de grandes données. La recherche binaire fonctionne en O(log n), mais nécessite un tableau trié.

Recherche linéaire

function linearSearch<T>(arr: T[], target: T): number {\n    for (let i = 0; i < arr.length; i++) {\n        if (arr[i] === target) {\n            return i;\n        }\n    }\n    return -1;\n}\n\nconst numbers = [3, 7, 1, 9, 4];\nconsole.log(linearSearch(numbers, 9)); // 3

Recherche binaire (version récursive)

function binarySearch<T>(arr: T[], target: T, left: number = 0, right: number = arr.length - 1): number {\n    if (left > right) {\n        return -1;\n    }\n\n    const mid = Math.floor((left + right) / 2);\n\n    if (arr[mid] === target) {\n        return mid;\n    }\n\n    if (arr[mid] > target) {\n        return binarySearch(arr, target, left, mid - 1);\n    } else {\n        return binarySearch(arr, target, mid + 1, right);\n    }\n}\n\nconst sortedArray = [1, 3, 5, 7, 9, 11];\nconsole.log(binarySearch(sortedArray, 7)); // 3\nconsole.log(binarySearch(sortedArray, 6)); // -1

Pour la version itérative, utilisez une boucle while. TypeScript aide à éviter les erreurs liées aux types : le générique <T> garantit que le tableau et l'élément cible sont du même type.

3. Tri : Tri rapide (Quick Sort)

Le tri rapide est l'un des algorithmes les plus efficaces avec une complexité moyenne O(n log n). R