Bagaimana untuk Melaksanakan Struktur Data Baris dengan Betul dalam Go Menggunakan Tatasusunan Pekeliling?

Bagaimana untuk melaksanakan baris gilir dalam Go?

Latar Belakang:

Dalam Go, perpustakaan standard tidak mempunyai bekas baris gilir . Untuk melaksanakan baris gilir, anda boleh menggunakan tatasusunan bulat sebagai struktur data asas.

Pelaksanaan Awal:

Kod yang disediakan menggunakan tatasusunan bulat dengan algoritma berikut:

• Sisipan: Sisipkan Y ke dalam baris gilir X: X[R] <- Y; R <- (R 1) % M; jika R = F maka LIMPAH.
• Pemadaman: Padamkan Y daripada baris gilir X: jika F = R maka UNDERFLOW; Y <- X[F]; F <- (F 1) % M.

Di mana F ialah hadapan, R ialah belakang, dan M ialah panjang tatasusunan.

Kod dan Salah Output:

Kod yang disediakan melaksanakan algoritma ini, tetapi output menunjukkan salah tingkah laku:

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

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

Penyelesaian:

Untuk membetulkan isu ini, medan tambahan diperlukan. Kod yang diubah suai menggabungkan semakan untuk memastikan kedudukan ekor yang dikemas kini tidak bertepatan dengan kepala:

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

Dengan pembetulan ini, output adalah tepat:

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

Pelaksanaan Alternatif Menggunakan Slices:

Dalam versi Go moden, pelaksanaan yang lebih mudah boleh dilakukan menggunakan 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)
    }
}

Pelaksanaan ini memanfaatkan pertumbuhan dinamik slices dan pengumpulan sampah, menjadikannya cekap dan praktikal.

Atas ialah kandungan terperinci Bagaimana untuk Melaksanakan Struktur Data Baris dengan Betul dalam Go Menggunakan Tatasusunan Pekeliling?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!