Comment implémenter correctement une structure de données de file d'attente dans Go à l'aide d'un tableau circulaire ?-Golang-php.cn

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

Susan Sarandon

Libérer： 2024-11-29 06:36:10

original

202 Les gens l'ont consulté

How to Correctly Implement a Queue Data Structure in Go Using a Circular Array?

Comment implémenter une file d'attente dans Go ?

Contexte :

Dans Go, la bibliothèque standard n'a pas de conteneur de file d'attente . Pour implémenter une file d'attente, vous pouvez utiliser un tableau circulaire comme structure de données sous-jacente.

Implémentation initiale :

Le code fourni utilise un tableau circulaire avec les algorithmes suivants :

Insertion : Insérer Y dans la file d'attente X : X[R] <- Y; R <- (R 1) % M ; si R = F alors OVERFLOW.
Suppression : Supprimer Y de la file d'attente X : si F = R alors UNDERFLOW ; Y &Lt ;- X[F] ; F <- (F 1) % M.

Où F est l'avant, R est l'arrière et M est la longueur du tableau.

Code et incorrect Résultat :

Le code fourni implémente ces algorithmes, mais la sortie présente des résultats incorrects behavior:

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
    p.tail = (p.tail + 1) % p.len
    return p.head != p.tail
}

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())
    }
}

Copier après la connexion

Output:

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

11 true
12 true
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false
0 false

Copier après la connexion

Solution:

Pour remédier à ce problème, un champ supplémentaire est requis. Le code modifié intègre une vérification pour garantir que la position de la queue mise à jour ne coïncide pas avec la tête :

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())
    }
}

Copier après la connexion

Avec cette correction, le résultat est précis :

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

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

Copier après la connexion

Implémentation alternative à l'aide de Slices :

Dans les versions Go modernes, une implémentation plus simple est possible en utilisant slices :

package main

import (
    "fmt"
)

// Queue implements a queue using a slice.
type Queue []int

// Enqueue adds an element to the end of the queue.
func (q *Queue) Enqueue(x int) {
    *q = append(*q, x)
}

// Dequeue removes and returns the first element of the queue.
func (q *Queue) Dequeue() (int, bool) {
    if len(*q) == 0 {
        return 0, false
    }
    x := (*q)[0]
    *q = (*q)[1:]
    return x, true
}

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

    for i := 0; i < 12; i++ {
        x, _ := q.Dequeue()
        fmt.Println(x)
    }
}

Copier après la connexion

Cette implémentation exploite la croissance dynamique et la collecte des déchets des slices, ce qui la rend à la fois efficace et pratique.

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!