背景：
Go 中，标准库缺少队列容器。要实现队列，您可以使用循环数组作为底层数据结构。
初始实现：
提供的代码使用具有以下算法的循环数组：
其中F为前，R为后，M为数组长度。
代码与错误输出：
提供的代码实现了这些算法，但输出显示不正确行为：
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
解决方案：
要纠正此问题，需要一个附加字段。修改后的代码合并了一项检查，以确保更新后的尾部位置与头部不重合：
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())
}
}通过此更正，输出是准确的：
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
使用切片的替代实现：
在现代 Go 版本中，可以使用更简单的实现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)
}
}此实现利用了切片的动态增长和垃圾回收，使其既高效又实用。
以上是如何在Go中使用循环数组正确实现队列数据结构？的详细内容。更多信息请关注PHP中文网其他相关文章！
