I have been learning Go, and I was doing a BFS puzzle with it. The queue implementation I decided on is:
//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
}
I have 2 questions:
Is this a good implementation? Documentation on queues in go is sparse, and in general there are some old posts about vectors, and a list seems to have too much overhead (not that it matters for my case, but I'm trying to do it the best way possible).
Why does the call to an object (in this case the struct pointer F *frontier) have to be a pointer? It seems like the way the syntax works that it should be a default for a pointer, not explicit (i.e. why would you ever not want to use a pointer in these instances?)
MODIFIED CIRCULAR VERSION:
//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
}
It looks like your implementation will work, but it will end up being a bit inefficient. At the beginning, queue is a slice with capacity 1000. That means that the underlying array can hold 1000 elements. Every time you call pop, you're moving the beginning of the queue one element further down that array, thus reducing the capacity by 1. Eventually, the capacity will be insufficient to hold a new element when you call push, even though there may not be many (or any) elements in the queue. That will cause a new array to be allocated when append is called. No matter what the pattern of push and pop calls is, the array will be repeatedly reallocated, even if it never holds anywhere near 1000 elements. I would suggest using a linked list for this, either the one in the list package or one of your own design.
The receiver needs to be a pointer if the function will modify the receiver's value or if the receiver object is used in other places and the value must be shared. Otherwise, it doesn't need to be a pointer. You may want to make the receiver a pointer anyway if the value is large so that it doesn't have to be copied. (The receiver behaves like any other function parameter and the same considerations apply.)