如何在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 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())
    }   
}

- Stephen Hsu

---

现在你不需要这个链接：https://dev59.com/EE7Sa4cB1Zd3GeqP3XDm#31127526 - Salvador Dali

Answer 1

在任何合理的Go版本（1.x之后），您不需要进行所有这些麻烦。一切都可以通过切片来实现。

queue := []int{}

向队列添加元素：

queue = append(queue, 6)

从队列中取出元素：

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

---

这里是一个实现示例，证明pop操作并不需要很长时间（事实上，我认为当队列增长时重新分配内存可能会使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:]以立即停止队列引用指针。

- Salvador Dali

Answer 2

一个缓冲通道可以作为一个很好的队列使用，但是它有一个固定的最大队列长度，这个长度在创建时确定。通道具有一个有用的特性，即出队操作是线程安全的（你的代码不是）。

- Jeff Allen

Answer 3

首先，您需要创建一个结构体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("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
}

- code philosopher

---

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

Answer 4

当Enqueue失败时，您仍然会增加p.tail，因此下一次它将不会失败-- 这就解释了您第一个循环中的单个false（并且对第二个循环产生了混乱）。原始算法说OVERFLOW意思是“放弃所有”，而不是“继续进行，好像没有发生任何异常”;-)。

您需要做的就是在检查到失败时减少p.tail -- 或者将增加的值放入本地临时变量中，仅在未发生故障时将其移动到p.tail，这可能更加优雅。通过这种方式，失败的Enqueue不会将新值入队，但队列本身（不包括那个溢出的值）仍然在语义上完整且正确，可以用于未来的操作。

- Alex Martelli

Answer 5

确实没有叫做queue的包，但是vector或者list都可以很好地用作队列。另外，可以参考这个问题。

- Evan Shaw

---

向量可能不太好，因为从开头插入或删除元素需要移动所有元素，这非常低效。 - newacct

@newacct 谢谢，你说得完全正确。在这种情况下，列表肯定更好，但向量仍然可以使用而不需要修改 - 只是效率不太高。 - Evan Shaw

Answer 6

我修改了原始实现，使其成为一个动态队列。也就是说，当队列填满时，它会分配一个更大的队列并将所有项目移动过去。

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())
    }
}

- grokus