go - Go中的结构队列

Question

我一直在学习围棋，我正在用它做一个 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. 为什么调用一个对象(在本例中是结构指针 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 的 slice 。这意味着底层数组可以容纳 1000 个元素。每次调用 pop 时，都会将队列的开头元素向下移动一个元素，从而将容量减少 1。最终，当您使用时，容量将不足以容纳新元素调用 push，即使队列中可能没有很多(或任何)元素。这将导致在调用 append 时分配一个新数组。无论 push 和 pop 调用的模式是什么，数组都将被重复重新分配，即使它永远不会容纳接近 1000 个元素。我建议为此使用链表，可以是 list 包中的链表，也可以是您自己设计的链表。

2. 如果函数将修改接收者的值，或者如果接收者对象在其他地方使用并且必须共享该值，则接收者需要是一个指针。否则，它不需要是一个指针。如果值很大，您可能希望使接收器成为一个指针，这样就不必复制它。 (接收器的行为与任何其他函数参数一样，并且适用相同的注意事项。)