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
}