La bibliothèque de go actuelle ne fournit pas le conteneur de la file d'attente. Pour mettre en œuvre une simple file d'attente, j'utilise une matrice de cercle comme structure de données sous-jacente. Il suit des algorithmes mentionnés dans le TAOCP:
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
ok := false
if ntail != p.head {
p.tail = ntail
ok = true
}
return ok
}
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())
}
}
6 Réponses :
Lorsque Tout ce que vous avez à faire est de décrémenter Enqueue échoue, vous êtes toujours incrémentation p.tail , alors il apparaît la prochaine fois qu'il ne semblera pas échouer - cela explique Le célibataire faux dans votre première boucle (et tout gâche pour le second). L'algorithme d'origine indique débordement signifiant "donner tout ce que vous" donnez ", non" continue de continuer comme si rien n'est arrivé "; -).
p.tail si vous avez vérifié que l'échec se produisait - ou mettez la valeur incrémentée dans une locale temporaire et déplacez-la à p.tail < / Code> Seulement si l'échec est pas survenant, qui peut être plus élégant. De cette façon, l'échec Enqueue est pas Enqueue la nouvelle valeur, mais la file d'attente elle-même (sans cette valeur débordante) est toujours sémantiquement intacte et correcte pour les opérations futures.
Il est vrai qu'il n'y a pas de package appelé file d'attente, mais vecteur ou
le vecteur n'est probablement pas bon, car l'insertion ou l'élimination des choses depuis le début implique de déplacer tous les éléments, ce qui est terriblement inefficace
@newacct merci, vous avez absolument raison. La liste serait certainement meilleure dans ce cas, mais le vecteur fonctionnerait toujours sans modification - juste pas très efficacement.
Je modifie la mise en œuvre initiale pour faire une file d'attente dynamique. C'est à dire. Lorsque la file d'attente se remplit, il allouera une file d'attente plus grande et déplacera tous les éléments.
package main
import (
"fmt"
)
type Queue struct {
len uint
head, tail uint
q []int
}
func NextPowerOfTwo(v uint) uint {
if v == 0 {
return 1
}
v--
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
v++
return v
}
func NewQueue(n uint) *Queue {
n = NextPowerOfTwo(n)
if n < 4 {
n = 4
}
println("create queue of", n)
return &Queue{n, 0, 0, make([]int, n)}
}
func (p *Queue) Resize() {
if p.head == (p.tail + 1) % p.len {
new_len := p.len * 2;
new_q := make([]int, new_len)
// currently there are (len - 1) items in the queue
var i uint
for i = 0; i < p.len - 1; i++ {
n, _ := p.Dequeue()
new_q[i] = n
}
p.q = new_q
p.head, p.tail = 0, p.len - 1
p.len = new_len
println("queue resized to ", p.len)
}
}
func (p *Queue) Enqueue(x int) {
p.Resize();
p.q[p.tail] = x
p.tail = (p.tail + 1) % p.len
}
func (p *Queue) Dequeue() (int, bool) {
if p.head == p.tail {
return -1, false
}
x := p.q[p.head]
p.head = (p.head + 1) % p.len
return x, true
}
func main() {
q := NewQueue(1)
for i := 1; i < 13; i++ {
q.Enqueue(2 * i + 1)
println("enqueued item ", i)
}
println("** queue content **")
for i := 1; i < 13 + 1; i++ {
fmt.Println(q.Dequeue())
}
}
Un canal tamponné fait une fine file d'attente, même s'il a une longueur de file d'attente maximale fixe, choisie au moment de la création. Un canal a la propriété utile qui desquelles sont threadsafe (votre code n'est pas).
Vous n'avez pas besoin de toute cette hâte dans une version de Go raisonnable (après 1.x). Tout peut être réalisé avec tranches .
Voici la mise en œuvre qui montre que la pop ne prend pas beaucoup de temps (en fait ici, il est plus court que poussant parce que, à mon avis de réaffectation de la mémoire lorsque la file d'attente est en croissance). sur ma machine Les chiffres sont: de @davec Le commentaire: Ceci est simple et fonctionne très bien pour tout sauf code critique
où les allocations (pression sur le collecteur des ordures) est
indésirable.two choses à noter, d'abord, il continue à réaffecter le
Array sous-jacent sur la poussée (bien que efficacement et non sur chaque appel)
et Pop ne libère aucun espace avant cela ne se passe. Cela conduit à la
deuxième chose, si (comme c'est commun) la file d'attente contient un pointeur à
quelque chose, alors il est bon de faire la queue [0] = nil; Queue = file d'attente [1:] à
Demandez à la file d'attente de référencer le pointeur immédiatement.
file d'attente: = [] int {} Queue = APPEND (File d'attente, 6)
Maintenant, vous n'avez pas besoin d'une de ces informations: Stackoverflow.com/a/31127526/1090562