如何在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 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是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 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

当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 mainimport (&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "time")func main() {&nbsp; &nbsp; n := 10000000&nbsp; &nbsp; queue := []int{1, 2, 3}&nbsp; &nbsp; start := time.Now()&nbsp; &nbsp; for i := 0; i < n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; queue = append(queue, i)&nbsp; &nbsp; }&nbsp; &nbsp; elapsed := time.Since(start)&nbsp; &nbsp; fmt.Println(elapsed)&nbsp; &nbsp; start = time.Now()&nbsp; &nbsp; for i := 0; i < n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; _ = queue[0]&nbsp; &nbsp; &nbsp; &nbsp; queue = queue[1:]&nbsp; &nbsp; }&nbsp; &nbsp; elapsed = time.Since(start)&nbsp; &nbsp; fmt.Println(elapsed)&nbsp; &nbsp; fmt.Println(queue)}在我的机器上，数字为：216.611664ms13.441106ms来自@DaveC的评论：这很简单，并且对所有其他情况都非常有效，除了关键代码（不需要分配（对垃圾回收器施加压力）是不受欢迎的）之外，有两点要注意，首先，它确实会在push时（尽管有效，而不是在每次调用时）重新分配底层数组。而pop不会释放任何空间，直到发生这种情况。这导致第二件事，如果（通常）队列包含指向某个对象的指针，那么最好将queue [0] = nil; queue = queue [1：]使队列立即停止引用指针。