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

So implementieren Sie eine Warteschlange in Go

Diese Frage untersucht die Implementierung einer einfachen Warteschlange in Go unter Verwendung eines kreisförmigen Arrays als zugrunde liegende Daten Struktur. Der Ansatz folgt den in „Die Kunst der Computerprogrammierung“ beschriebenen Algorithmen. Beim ursprünglich vorgestellten Code trat jedoch ein Problem mit falscher Ausgabe auf.

Verstehen der Diskrepanz

Das Hauptproblem des Codes liegt im Fehlen eines Mechanismus zur Handhabung Situation, in der die Warteschlange voll ist. Der Ansatz der kreisförmigen Anordnung erfordert eine Möglichkeit, festzustellen, wann die Kapazität erreicht ist. Dem Originalcode fehlte diese Prüfung, was zu einem Versuch führte, Elemente über das Ende des Arrays hinaus zu überschreiben.

Verfeinerung der Implementierung

Um dieses Problem zu beheben, ist eine einfache Änderung erforderlich wird eingeführt. Die Enqueue-Funktion enthält jetzt eine Bedingung, um zu überprüfen, ob der Tail-Index nicht mit dem Head-Index übereinstimmt. Wenn sie gleich sind, ist die Warteschlange voll und die Funktion gibt false zurück. Andernfalls wird das Element zur Warteschlange hinzugefügt, der Endindex erhöht und true zurückgegeben.

Verbesserter Code

Hier ist der aktualisierte Code:

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

Mit dieser Änderung verarbeitet der Code das Ein- und Ausreihen von Elementen korrekt, was zum erwarteten Ergebnis führt Ausgabe:

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

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