Bagaimana untuk Melaksanakan Struktur Data Baris dengan Betul dalam Go Menggunakan Tatasusunan Pekeliling?-Golang-php.cn

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

Susan Sarandon

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

asal

201 orang telah melayarinya

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

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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!