Comment implémenter correctement une file d'attente dans Go à l'aide d'un tableau circulaire ?

Comment implémenter une file d'attente dans Go

Cette question explore l'implémentation d'une file d'attente simple dans Go en utilisant un tableau circulaire comme données sous-jacentes structure. L'approche suit les algorithmes décrits dans « L'art de la programmation informatique ». Cependant, le code initial présenté a rencontré un problème avec une sortie incorrecte.

Comprendre l'écart

Le principal problème du code réside dans l'absence d'un mécanisme pour gérer le situation où la file d’attente est pleine. L'approche du réseau circulaire nécessite un moyen de déterminer quand il est à pleine capacité. Le code d'origine ne disposait pas de cette vérification, ce qui a entraîné une tentative d'écrasement des éléments au-delà de la fin du tableau.

Affinage de l'implémentation

Pour résoudre ce problème, une simple modification est introduit. La fonction Enqueue inclut désormais une condition pour vérifier si l'index de queue n'est pas égal à l'index de tête. S'ils sont égaux, la file d'attente est pleine et la fonction renvoie false. Sinon, il ajoute l'élément à la file d'attente, incrémente l'index de queue et renvoie vrai.

Code amélioré

Voici le code mis à jour :

package main

import (
    "fmt"
)

type Queue struct {
    len        int
    head, tail int
    q          []int
}

func New(n int) *Queue {
    return &Queue{n, 0, 0, make([]int, n)}
}

func (p *Queue) Enqueue(x int) bool {
    p.q[p.tail] = x
    ntail := (p.tail + 1) % p.len
    if ntail != p.head {
        p.tail = ntail
        return true
    }
    return false
}

func (p *Queue) Dequeue() (int, bool) {
    if p.head == p.tail {
        return 0, false
    }
    x := p.q[p.head]
    p.head = (p.head + 1) % p.len
    return x, true
}

func main() {
    q := New(10)
    for i := 1; i < 13; i++ {
        fmt.Println(i, q.Enqueue(i))
    }
    fmt.Println()
    for i := 1; i < 13; i++ {
        fmt.Println(q.Dequeue())
    }
}

Avec cette modification, le code gère correctement les éléments de mise en file d'attente et de retrait, ce qui donne le résultat attendu :

1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 true
11 true
12 true

11 true
12 true
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
10 true

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!