如何在Go中实现队列？

  • Z时代
  • 2024-01-10
  • 分类：问答

当前的Go库不提供队列容器。为了实现一个简单的队列，我使用圆形数组作为基础数据结构。它遵循TAOCP中提到的算法：

Insert Y into queue X: X[R]<-Y; R<-(R+1)%M; if R=F then OVERFLOW.
Delete Y from queue X: if F=R then UNDERFLOW; Y<-X[F]; F<-(F+1) % M.
F: Front, R: Rear, M: Array length.

以下是代码：

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

但是输出显然是错误的：

1是2是3是4是5是6是7是8是9是10是11是12是

11是12是0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误0错误

我认为我还需要一个领域来使代码正常工作。你有什么建议？

改进的代码有一个小的缺点：大小为n的数组只能包含n-1个元素。

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

回答：

当Enqueue失败时，您 仍在 增加p.tail，因此下一次它似乎不会失败-

这就解释了false第一个循环中的单曲（并弄乱了第二个循环中的所有内容）。原始算法说的OVERFLOW意思是“放弃一切”，而不是“只是继续前进，就好像什么都没发生一样”

；-)。

您需要做的就是p.tail如果已检查是否发生了故障，则递减-或将增加的值放在本地临时文件中，然后p.tail仅在 未

发生故障时才将其移动到，这可能会更优雅。这样一来，否则Enqueue就 不会 排队新的价值，但本身队列（而没有溢出值）仍是语义完整和正确的未来运营。

以上是 如何在Go中实现队列？ 的全部内容， 来源链接： utcz.com/qa/429196.html

回到顶部