使用接口为任意类型创建队列

Question

As an exercise for learning Go I am writing a basic Queue data structure. I started learning about interfaces yesterday I thought it would be cool to try and use them for this exercise. What I am trying to accomplish is to have a Queue that can accept any type that implements this interface:

type Queuable interface {
  Next() *Queuable  // This is probably not right
}

Basically what I want is to be able to add any type that has a Next() method to my Queue. So what I tried was:

type Node struct {
    value interface{}
    next  *Queuable
}

// Next gets the next object
func (n *Node) Next() *Queuable {
    return n.next
}

// Job - A job for the queue
type Job struct {
    instruction string
    next        *Queuable
}

// Next gets the next object
func (j *Job) Next() *Queuable {
    return j.next
}

// Queue ...
type Queue struct {
    head *Queuable
    size int
}

And my methods looking like:

func (q *Queue) Enqueue(node *Queuable) {
    ...
}

// Dequeue - Remove a Queueable form the Queue
func (q *Queue) Dequeue() *Queuable {
  result := q.head
  q.head = q.head.Next()
  q.size--
  return result
}

I'm getting a ton of these errors (basically on any line with an assignment):

current.Next undefined (type *Queuable is pointer to interface, not interface)

So ultimately what I would like to do would be:

func main() {
  queue := NewQueue()  // Helper function not pictured
  job := &Job{"some instructions", nil}
  node := &Node{5, nil}
  queue.Enqueue(node)  // queue = [node]
  queue.Enqueue(job) // queue = [node, job]
  queue.Dequeue() // node
  queue.Dequeue() // job
}

Answer 1

Don't use pointer to an interface type, just the interface type.

Queuable is an interface type, so everywhere in your code where you used *Queuable, change it to Queuable. For example:

type Queuable interface {
    Next() Queuable
}

type Node struct {
    value interface{}
    next  Queuable
}

// Next gets the next object
func (n *Node) Next() Queuable {
    return n.next
}

...

In Go a value of interface type stores a pair: the concrete value assigned to the variable, and that value's type descriptor.

More about interface's internals: The Laws of Reflection #The representation of an interface

So you almost never need a pointer to interface. An interface contains a key-value pair where the key may be a pointer. The rare case when a pointer to interface makes sense is if you want to modify the value of a variable of interface type passed to another function.

In your example the type *Job implements Queuable because it has a method with receiver type *Job, and so everywhere where a value of Queuable is required, a value of *Job can be used (and an implicit interface value of type Queuable will be created and used).

Getting back to your example:

Your Queuable only defines a method to get the next element in the queue, but not one to enqueue it which will make this solution lose flexibility. A single Next() method only describes that it is "queued" but it is not (necessarily) "queuable".

To be queuable I would also add another method: SetNext(Queuable)

type Queuable interface {
    Next() Queuable
    SetNext(Queuable)
}

Its implementation on Node can be for example:

func (n *Node) SetNext(q Queuable) { n.next = q }

Try it on the <kbd>Go Playground</kbd>.

Also note that there is some code duplication in Node and Job, being the next field and Next() and SetNext() methods. We could create a base node implementation, e.g.:

type Base struct {
    next Queuable
}

func (b *Base) Next() Queuable     { return b.next }
func (b *Base) SetNext(q Queuable) { b.next = q }

And now you can embed this Base type in your concrete Node and Job implementations which will "inherit" the next field and Next() and SetNext() methods, so you don't have to define any of these on the Node and Job types.

This is the full implementation of Node and Job, nothing else is required:

type Node struct {
    *Base
    value interface{}
}

type Job struct {
    *Base
    instruction string
}

Try this on the <kbd>Go Playground</kbd>.