Wie implementiert man eine Warteschlangendatenstruktur in Go mithilfe eines kreisförmigen Arrays korrekt?-Golang-php.cn

Wie implementiert man eine Warteschlangendatenstruktur in Go mithilfe eines kreisförmigen Arrays korrekt?

Susan Sarandon

Freigeben： 2024-11-29 06:36:10

Original

208 Leute haben es durchsucht

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

Wie implementiert man eine Warteschlange in Go?

Hintergrund:

In Go fehlt der Standardbibliothek ein Warteschlangencontainer . Um eine Warteschlange zu implementieren, können Sie ein kreisförmiges Array als zugrunde liegende Datenstruktur verwenden.

Erste Implementierung:

Der bereitgestellte Code verwendet ein kreisförmiges Array mit den folgenden Algorithmen:

Einfügung: Y in Warteschlange X einfügen: X[R] <- Y; R <- (R 1) % M; wenn R = F, dann ÜBERLAUF.
Löschen: Y aus Warteschlange X löschen: wenn F = R, dann UNDERFLOW; Y <- X[F]; F <- (F 1) % M.

Wobei F die Vorderseite, R die Rückseite und M die Array-Länge ist.

Code und falsch Ausgabe:

Der bereitgestellte Code implementiert diese Algorithmen, aber die Ausgabe ist falsch Verhalten:

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

Nach dem Login kopieren

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

Nach dem Login kopieren

Lösung:

Um dieses Problem zu beheben, ist ein zusätzliches Feld erforderlich. Der geänderte Code enthält eine Prüfung, um sicherzustellen, dass die aktualisierte Schwanzposition nicht mit der des Kopfes übereinstimmt:

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

Nach dem Login kopieren

Mit dieser Korrektur ist die Ausgabe korrekt:

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

Nach dem Login kopieren

Alternative Implementierung mithilfe von Slices:

In modernen Go-Versionen ist eine einfachere Implementierung mithilfe von möglich 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)
    }
}

Nach dem Login kopieren

Diese Implementierung nutzt das dynamische Wachstum und die Speicherbereinigung von Slices und macht es sowohl effizient als auch praktisch.

Das obige ist der detaillierte Inhalt vonWie implementiert man eine Warteschlangendatenstruktur in Go mithilfe eines kreisförmigen Arrays korrekt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!