如何在Go中实现队列？

Question

当前的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 mainimport (    "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 mainimport (    "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

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

p.tail如果您已检查是否发生了故障，那么您所需要做的就是递减-或将递增的值放在本地临时文件中，然后p.tail仅在未发生故障时才将其移动到，这可能会更优雅。这样一来，否则Enqueue就不会排队新的价值，但本身队列（而没有溢出值）仍是语义完整和正确的未来运营。

Answer 2

在任何合理的go版本（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的评论：

这很简单，并且对所有其他情况都非常有效，除了关键代码（不需要分配（对垃圾回收器施加压力）是不受欢迎的）之外，有两点要注意，首先，它确实会在push时（尽管有效，而不是在每次调用时）重新分配底层数组。而pop不会释放任何空间，直到发生这种情况。这导致第二件事，如果（通常）队列包含指向某个对象的指针，那么最好将queue [0] = nil; queue = queue [1：]使队列立即停止引用指针。