How to implement a simple queue properly?
- by Stephen Hsu
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?
