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

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

Go (Golang) est un langage compilé, typé statiquement, créé chez Google. Sa simplicité, ses hautes performances et son support intégré de la concurrence en font un excellent choix pour le développement backend, les microservices et la programmation système. Cependant, pour écrire du code efficace en Go, il ne suffit pas de connaître la syntaxe — il faut comprendre le fonctionnement des algorithmes et des structures de données. Dans cet article, nous analyserons les structures de données et algorithmes clés en Go, en accompagnant chaque section d'exemples pratiques.

1. Pile (Stack) en Go

La pile est une structure de données fonctionnant selon le principe LIFO (Last In, First Out). Go n'a pas de type "pile" intégré, mais il est facile de l'implémenter à l'aide d'une tranche (slice).

Exemple d'implémentation d'une pile :

package main\n\nimport "fmt"\n\ntype Stack struct {\n    items []int\n}\n\n// Push ajoute un élément au sommet de la pile\nfunc (s *Stack) Push(item int) {\n    s.items = append(s.items, item)\n}\n\n// Pop supprime et retourne l'élément du sommet de la pile\nfunc (s *Stack) Pop() (int, bool) {\n    if len(s.items) == 0 {\n        return 0, false\n    }\n    lastIndex := len(s.items) - 1\n    item := s.items[lastIndex]\n    s.items = s.items[:lastIndex]\n    return item, true\n}\n\n// Peek retourne l'élément du sommet sans le supprimer\nfunc (s *Stack) Peek() (int, bool) {\n    if len(s.items) == 0 {\n        return 0, false\n    }\n    return s.items[len(s.items)-1], true\n}\n\nfunc main() {\n    stack := Stack{}\n    stack.Push(10)\n    stack.Push(20)\n    stack.Push(30)\n\n    item, ok := stack.Pop()\n    if ok {\n        fmt.Println("Extrait :", item) // 30\n    }\n    fmt.Println("Sommet de la pile :", stack.Peek()) // 20\n}

La pile en Go est efficace grâce à une complexité amortie O(1) pour les opérations Push et Pop. Utilisez-la pour des tâches comme la vérification de séquences de parenthèses ou l'annulation d'actions (undo).

2. File d'attente (Queue) en Go

La file d'attente fonctionne selon le principe FIFO (First In, First Out). Nous l'implémentons à l'aide d'une tranche avec des pointeurs vers le début et la fin.

Exemple d'implémentation d'une file d'attente :

package main\n\nimport "fmt"\n\ntype Queue struct {\n    items []int\n}\n\n// Enqueue ajoute un élément à la fin de la file\nfunc (q *Queue) Enqueue(item int) {\n    q.items = append(q.items, item)\n}\n\n// Dequeue supprime et retourne l'élément du début de la file\nfunc (q *Queue) Dequeue() (int, bool) {\n    if len(q.items) == 0 {\n        return 0, false\n    }\n    item := q.items[0]\n    q.items = q.items[1:]\n    return item, true\n}\n\n// Front retourne le premier élément sans le supprimer\nfunc (q *Queue) Front() (int, bool) {\n    if len(q.items) == 0 {\n        return 0, false\n    }\n    return q.items[0], true\n}\n\nfunc main() {\n    queue := Queue{}\n    queue.Enqueue(1)\n    queue.Enqueue(2)\n    queue.Enqueue(3)\n\n    item, ok := queue.Dequeue()\n    if ok {\n        fmt.Println("Extrait :", item) // 1\n    }\n    fmt.Println("Premier dans la file :", queue.Front()) // 2\n}

Attention : l'opération Dequeue dans cette implémentation a une complexité O(n), car la suppression du premier élément décale toute la tranche. Pour du code de production, utilisez un tampon circulaire (ring buffer) ou une liste doublement chaînée (container/list).

3. Tri à bulles (Bubble Sort) en Go

Le tri à bulles est l'un des algorithmes les plus simples, mais inefficaces. Néanmoins, il est parfait pour l'apprentissage. Complexité : O(n²).

package main\n\nimport "fmt"\n\nfunc bubbleSort(arr []int) {\n    n := len(arr)\n    for i := 0; i < n-1; i++ {\n        swapped := false\n        for j := 0; j < n-i-1; j++ {\n            if arr[j] > arr[j+1] {\n                arr[j], arr[j+1] = arr[j+1], arr[j]\n                swapped = true\n            }\n        }\n        // Si aucun échange n'a eu lieu — le tableau est déjà trié\n        if !swap