英文:
How to implement a queue in Go?
问题
当前的Go库没有提供队列容器。
为了实现一个简单的队列,我使用循环数组作为底层数据结构。
它遵循TAOCP中提到的算法:
将Y插入队列X:X[R] <- Y; R <- (R+1)%M; 如果R=F,则溢出。
从队列X中删除Y:如果F=R,则下溢;Y <- X[F]; F <- (F+1) % M。
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())
}
}
但是输出显然是错误的:
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个元素。
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())
}
}
英文:
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())
}
}
答案1
得分: 10
你在任何合理的Go版本(1.x之后)中都不需要这么麻烦。一切都可以通过slices来实现。
queue := []int{}
向队列中添加元素:
queue = append(queue, 6)
从队列中弹出元素:
el := queue[0]
queue = queue[1:]
下面是一个实现示例,显示弹出操作并不需要很长时间(实际上,这里比推入操作更短,因为在队列增长时,内存重新分配的原因)。
package main
import (
"fmt"
"time"
)
func main() {
n := 10000000
queue := []int{1, 2, 3}
start := time.Now()
for i := 0; i < n; i++ {
queue = append(queue, i)
}
elapsed := time.Since(start)
fmt.Println(elapsed)
start = time.Now()
for i := 0; i < n; i++ {
_ = queue[0]
queue = queue[1:]
}
elapsed = time.Since(start)
fmt.Println(elapsed)
fmt.Println(queue)
}
在我的机器上,输出结果为:
216.611664ms
13.441106ms
根据**@DaveC**的评论:
> 这很简单,对于除了关键代码之外的所有情况都非常有效,其中分配(对垃圾收集器的压力)是不可取的。需要注意的两件事,首先,它在推入操作时会不断重新分配底层数组(虽然高效且不是每次调用都会发生),而弹出操作在发生之前不会释放任何空间。这导致第二个问题,如果(通常情况下)队列包含指向某个东西的指针,那么最好执行queue[0] = nil; queue = queue[1:],以立即停止队列引用该指针。
英文:
You do not need all this hustle in any reasonable go version (after 1.x). Everything can be achieved with slices.
queue := []int{}
Add to a queue:
queue = append(queue, 6)
Pop from a queue:
el := queue[0]
queue = queue[1:]
Here is implementation that shows that pop does not take a lot of time (in fact here it is shorter than push because in my opinion of reallocation of memory when the queue is growing).
package main
import (
"fmt"
"time"
)
func main() {
n := 10000000
queue := []int{1, 2, 3}
start := time.Now()
for i := 0; i < n; i++ {
queue = append(queue, i)
}
elapsed := time.Since(start)
fmt.Println(elapsed)
start = time.Now()
for i := 0; i < n; i++ {
_ = queue[0]
queue = queue[1:]
}
elapsed = time.Since(start)
fmt.Println(elapsed)
fmt.Println(queue)
}
On my machine the numbers are:
216.611664ms
13.441106ms
From @DaveC's comment:
> This is simple and works very well for everything except critical code
> where allocations (pressure on the garbage collector) is
> undesirable.Two things to note, first it does keep re-allocating the
> underlying array on push (although efficiently and not on every call)
> and pop doesn't free any space until that happens. This leads to the
> second thing, if (as is common) the queue contains a pointer to
> something, then it's good to do queue[0] = nil; queue = queue[1:] to
> have the queue stop referencing the pointer right away.
答案2
得分: 4
一个带缓冲的通道可以作为一个很好的队列,尽管它在创建时有一个固定的最大队列长度。通道具有一个有用的特性,即出队操作是线程安全的(你的代码不是)。
英文:
A buffered channel makes a fine queue, though it has a fixed maximum queue length, chosen at creation time. A channel has the useful property that dequeues are threadsafe (your code isn't).
答案3
得分: 2
当Enqueue
失败时,你仍然在增加p.tail
,所以下一次它看起来不会失败 - 这解释了你第一个循环中的单个false
(并且对第二个循环造成了混乱)。原始算法中的OVERFLOW
意味着"放弃一切",而不是"继续进行,好像没有发生任何不好的事情";-)
你只需要在检查到失败时减少p.tail
的值 - 或者将增加的值放入一个本地临时变量中,只有在失败不发生时将其移动到p.tail
,这可能更优雅。这样,失败的Enqueue
不会将新值入队,但队列本身(不包括溢出的值)在语义上仍然完整且正确,可以用于未来的操作。
英文:
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.
答案4
得分: 2
确实没有叫做queue的包,但是vector或者list都可以作为很好的队列使用。还可以参考这个问题。
英文:
It's true that there's no package called queue, but either vector or list would make fine queues. Also see this question.
答案5
得分: 2
首先,您需要创建一个用于保存队列属性的Queue结构体。然后创建一个initQueue函数来初始化默认值,该函数还将从用户那里获取内存大小。创建一个函数来enqueue值,创建一个函数来dequeue值。创建一个显示函数来display队列值。
type Queue struct {
front int
rear int
size int
QArray []int
}
func (q *Queue) initQueue(size int) {
q.size = size
q.QArray = make([]int, q.size)
q.front = -1
q.rear = -1
}
func (q *Queue) enqueue(value int) {
if q.rear == q.size-1 {
fmt.Println("队列已满")
return
} else {
q.rear++
q.QArray[q.rear] = value
}
}
func (q *Queue) dequeue() int {
var x int = -1
if q.front == q.rear {
fmt.Println("队列为空!")
} else {
q.front++
x = q.QArray[q.front]
}
return x
}
英文:
> First you need to create a struct for Queue for holding queue properties. Then create a initQueue function to initialize default values, which will also take memory size from the user. Create a function to enqueue values, create function to dequeue values. Create a display function to display queues values.
type Queue struct {
front int
rear int
size int
QArray []int
}
func (q *Queue) initQueue(size int) {
q.size = size
q.QArray = make([]int, q.size)
q.front = -1
q.rear = -1
}
func (q *Queue) enqueue(value int) {
if q.rear == q.size-1 {
fmt.Println("Queue is Full")
return
} else {
q.rear++
q.QArray[q.rear] = value
}
}
func (q *Queue) dequeue() int {
var x int = -1
if q.front == q.rear {
fmt.Println("Queue is Empty!")
} else {
q.front++
x = q.QArray[q.front]
}
return x
}
答案6
得分: 0
我修改了原始实现,使其成为一个动态队列。即当队列填满时,它会分配一个更大的队列并将所有项目移动过去。
package main
import (
"fmt"
)
type Queue struct {
len uint
head, tail uint
q []int
}
func NextPowerOfTwo(v uint) uint {
if v == 0 {
return 1
}
v--
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
v++
return v
}
func NewQueue(n uint) *Queue {
n = NextPowerOfTwo(n)
if n < 4 {
n = 4
}
println("创建队列大小为", n)
return &Queue{n, 0, 0, make([]int, n)}
}
func (p *Queue) Resize() {
if p.head == (p.tail + 1) % p.len {
new_len := p.len * 2;
new_q := make([]int, new_len)
// 当前队列中有 (len - 1) 个项目
var i uint
for i = 0; i < p.len - 1; i++ {
n, _ := p.Dequeue()
new_q[i] = n
}
p.q = new_q
p.head, p.tail = 0, p.len - 1
p.len = new_len
println("队列大小调整为", p.len)
}
}
func (p *Queue) Enqueue(x int) {
p.Resize();
p.q[p.tail] = x
p.tail = (p.tail + 1) % p.len
}
func (p *Queue) Dequeue() (int, bool) {
if p.head == p.tail {
return -1, false
}
x := p.q[p.head]
p.head = (p.head + 1) % p.len
return x, true
}
func main() {
q := NewQueue(1)
for i := 1; i < 13; i++ {
q.Enqueue(2 * i + 1)
println("入队项目", i)
}
println("** 队列内容 **")
for i := 1; i < 13 + 1; i++ {
fmt.Println(q.Dequeue())
}
}
英文:
I modify the original implementation to make a dynamic queue. I.e. when the queue fills up it will allocate a larger queue and move all the items over.
package main
import (
"fmt"
)
type Queue struct {
len uint
head, tail uint
q []int
}
func NextPowerOfTwo(v uint) uint {
if v == 0 {
return 1
}
v--
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
v++
return v
}
func NewQueue(n uint) *Queue {
n = NextPowerOfTwo(n)
if n < 4 {
n = 4
}
println("create queue of", n)
return &Queue{n, 0, 0, make([]int, n)}
}
func (p *Queue) Resize() {
if p.head == (p.tail + 1) % p.len {
new_len := p.len * 2;
new_q := make([]int, new_len)
// currently there are (len - 1) items in the queue
var i uint
for i = 0; i < p.len - 1; i++ {
n, _ := p.Dequeue()
new_q[i] = n
}
p.q = new_q
p.head, p.tail = 0, p.len - 1
p.len = new_len
println("queue resized to ", p.len)
}
}
func (p *Queue) Enqueue(x int) {
p.Resize();
p.q[p.tail] = x
p.tail = (p.tail + 1) % p.len
}
func (p *Queue) Dequeue() (int, bool) {
if p.head == p.tail {
return -1, false
}
x := p.q[p.head]
p.head = (p.head + 1) % p.len
return x, true
}
func main() {
q := NewQueue(1)
for i := 1; i < 13; i++ {
q.Enqueue(2 * i + 1)
println("enqueued item ", i)
}
println("** queue content **")
for i := 1; i < 13 + 1; i++ {
fmt.Println(q.Dequeue())
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论