Go中的结构队列

Question

我一直在学习Go，我用它做了一个BFS游戏。我决定的队列实现是：

//define the queue for our BFS algo as frontier.
type frontier struct {
    queue []*graphNode
}

func (F *frontier) buildFrontier() {
    F.queue = make([]*graphNode, 0, 1000)
}

func (F *frontier) pop() (g *graphNode) {
    if F.isEmpty() {
        panic("pop on empty queue!")
    }
    temp := F.queue[0]
    F.queue = F.queue[1:]
    return temp
}

func (F *frontier) push(g *graphNode) {
    F.queue = append(F.queue, g)
}

func (F *frontier) isEmpty() bool {
    return len(F.queue) == 0
}

我有两个问题：

1. 这是一个很好的实施吗？go中关于队列的文档是稀疏的，而且通常有一些关于向量的旧帖子，而且列表似乎有太多的开销(这对我的情况并不重要，但我正在尝试以最好的方式完成它)。
2. 为什么对对象的调用(在本例中是struct指针F *frontier)必须是指针？语法的工作方式似乎是指针的默认值，而不是显式的(也就是说，为什么您不想在这些实例中使用指针？)

修改后的循环版本：

//define the queue for our BFS algo as frontier.
type frontier struct {
    queue                []*graphNode
    size, head, capacity int
}

func (F *frontier) buildFrontier() {
    F.capacity = 1
    F.queue = make([]*graphNode, F.capacity)
    F.size = 0
    F.head = 0
}

func (F *frontier) pop() (g *graphNode) {
    if F.isEmpty() {
        panic("pop on empty queue!")
    }
    F.size = (F.size - 1)
    temp := F.queue[F.head]
    F.head = (F.head + 1) % F.capacity
    return temp
}

func (F *frontier) push(g *graphNode) {
    if F.isFull() {
        newSlice := make([]*graphNode, F.capacity*2)
        copy(newSlice, F.queue)
        F.queue = newSlice
        F.capacity *= 2
    }
    F.queue[(F.head+F.size)%F.capacity] = g
    F.size = (F.size + 1)
}

func (F *frontier) isEmpty() bool {
    return F.size == 0
}
func (F *frontier) isFull() bool {
    return F.size == F.capacity
}

Answer 1

1. 看起来你的实现会起作用，但最终会有一点效率低下。最初，queue是一个容量为1000的片。这意味着基础数组可以容纳1000个元素。每次调用pop时，都会将队列的开头--一个元素进一步向下移动--从而使容量减少1。最终，当调用push时，容量将不足以容纳一个新元素，即使队列中可能没有很多(或任何)元素。这将导致在调用append时分配一个新数组。无论push和pop调用的模式是什么，数组都将被反复重新分配，即使它从未包含接近1000个元素的任何位置。我建议为此使用一个链接列表，无论是在list包中还是在您自己的设计中。
2. 如果函数将修改接收器的值，或者接收器对象在其他地方使用，并且必须共享该值，则接收器需要是一个指针。否则，它不需要是一个指针。如果该值很大，您可能希望使接收方成为指针，这样就不必复制它。(接收方的行为与任何其他函数参数相同，适用相同的注意事项。)