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]
• Pemadaman: Padamkan Y daripada baris gilir X: jika F = R maka UNDERFLOW; Y

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 <pre class="brush:php;toolbar:false">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 <p>Dengan pembetulan ini, output adalah tepat:</p><pre class="brush:php;toolbar:false">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 <p>Pelaksanaan ini memanfaatkan pertumbuhan dinamik slices dan pengumpulan sampah, menjadikannya cekap dan praktikal.</p>

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!