如何在Go中实现队列？ [英] How to implement a queue in Go?
问题描述
当前的Go库不提供队列容器。
为了实现一个简单的队列，我使用圆阵列作为基础数据结构。
它遵循TAOCP中提到的算法：
将Y插入队列X：X [R] <-Y; R< ;-( R + 1）％M;如果R = F，则溢出。
从队列X中删除Y：如果F = R，则UNDERFLOW; Y'LT; -X [F]; F < - （F + 1）％M
F：前，R：后，M：数组长度。
以下是代码：
<$ p $ （b
$
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 {
pq [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：= pq [p.head]
p.head =（p.head + 1）％p.len
return x，true
}
func main（）{
q：= New （10）
for i：= 1;我< 13; i ++ {
fmt.Println（i，q.Enqueue（i））
}
fmt.Println（）
for i：= 1;我< 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 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
我想我需要一个字段使代码正常工作。
您有什么建议？
改进后的代码有一个小缺点：一个大小为n的数组只能包含n-1个元素。
包裹主要
进口（
fmt
）
类型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 {
pq [p.tail] = x
ntail：=（p.tail + 1）％p.len
ok：= false
如果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：= pq [p.head]
p.head = （p.head + 1）％p.len
return x，true
}
func main（）{
q：= New（10）
代表i：= 1;我< 13; i ++ {
fmt.Println（i，q.Enqueue（i））
}
fmt.Println（）
for i：= 1;我< 13; i ++ {
fmt.Println（q.Dequeue（））
}
}
p.tail ，所以下次它看起来不会失败 - 这就解释了第一个循环中的单个 false 第二个）。原始的算法是 OVERFLOW ，意思是放弃所有东西，而不是只要继续下去，就好像没有任何不良事件发生一样; - ）。 如果您检查了发生的故障，或者将增加后的值放入本地临时文件并移动它，您只需减少 p.tail 到 p.tail ，只有当 时，才会更优雅。这样，失败的 Enqueue 不会排列新值，但是队列本身（没有溢出值）仍然在语义上保持完好并且正确未来的行动。
The current Go library doesn't provide the queue container. To implement a simple queue, I use circle array as the underlying data structure. It follows algorithms mentioned in 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.
Following is the code:
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())
}
}
But the output is obviously wrong:
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
I think I need one more field to make the code work properly. What do you suggest?
The improved code has a small shortcoming: an array of size n can contain only n-1 elements.
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())
}
}
When Enqueue fails, you're still incrementing p.tail, so next time it will appear not to fail -- that explains the single false in your first loop (and messes everything up for the second one). The original algorithm says OVERFLOW meaning "give everything up", not "just keep going as if nothing untowards happened";-).
All you need to do is decrement p.tail if you've checked that failure's occurring -- or put the incremented value in a local temporary and move it to p.tail only if failure is not occurring, that may be more elegant. This way, the failing Enqueue does not enqueue the new value, but the queue itself (without that overflowing value) is still semantically intact and correct for future operations.
这篇关于如何在Go中实现队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
