如何在Go中实现队列？

Question

当前的Go库不提供队列容器.为了实现一个简单的队列,我使用circle数组作为底层数据结构.它遵循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 true 2 true 3 true 4 true 5 true 6 true 7 true 8 true 9 true 10 false 11 true 12 true

11真12真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())
    }   
}

Answer 1

在任何合理的版本中都不需要所有这些喧嚣(在1.x之后).切片可以实现一切.

queue := []int{}

添加到队列:

queue = append(queue, 6)

从队列中弹出:

el := queue[0]
queue = queue[1:]

这里的实现表明pop不需要花费很多时间(事实上这里它比push更短,因为我认为在队列增长时重新分配内存).

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的评论:

这很简单,除了关键代码之外的所有事情都非常有效,其中分配(垃圾收集器上的压力)是不合需要的.需要注意的是,首先它确实在推送时重新分配底层数组(虽然有效而不是每次调用)直到发生这种情况,pop才会释放任何空间.这导致了第二件事,如果(通常)队列包含指向某事物的指针,那么做队列[0] = nil是好的; queue = queue [1:]让队列立即停止引用指针.

Answer 2

当Enqueue失败时，您仍然会递增p.tail，因此下次它看起来不会失败 - 这解释了第一个循环中的单个false（并弄乱了第二个循环的所有内容）。原始算法的OVERFLOW意思是“放弃一切”，而不是“继续前进，就好像什么都没有发生一样”;-)。

您需要做的就是p.tail在检查发生故障时递减，或者将递增的值放入本地临时值中，并仅在未p.tail发生故障时才将其移动，这可能更优雅。这样，失败不会将新值排入队列，但队列本身（没有溢出值）在语义上仍然完整并且对于将来的操作是正确的。Enqueue