README.md

This week’s question:

Implement a circular queue. If you haven’t used that before, a circular queue is a data structure in which the operations are performed based on the “First In First Out” principle, and the last position is connected back to the first position to make a circle.

go.mod

module fifo-question

go 1.13

require github.com/stretchr/testify v1.5.1

go.sum

github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
github.com/stretchr/testify v1.5.1 h1:nOGnQDM7FYENwehXlg/kFVnos3rEvtKTjRvOWSzb6H4=
github.com/stretchr/testify v1.5.1/go.mod h1:5W2xD1RspED5o8YsWQXVCued0rvSQ+mT+I5cxcmMvtA=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/yaml.v2 v2.2.2 h1:ZCJp+EgiOT7lHqUV2J862kp8Qj64Jo6az82+3Td9dZw=
gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=

main.go

package main

import (
	"fmt"
	"os"
	"strconv"
)

func main() {
	// First argument is number of iterations through the queue
	iterations, err := strconv.Atoi(os.Args[1])
	if err != nil {
		panic(err)
	}

	// Remaining arguments are enqueued into the circular queue
	queue := NewCircularQueue()
	for _, a := range os.Args[2:] {
		queue.Enqueue(a)
	}

	for i := 0; i < iterations; i++ {
		if queue.TryMoveNext() {
			item, err := queue.Current()
			if err != nil {
				panic(err)
			}
			fmt.Printf("%s\n", item)
		}
	}
}

queue.go

package main

import "errors"

type item struct {
	value string
	next *item
}

// CircularQueue is an implementation of a circular queue
type CircularQueue struct {
	next *item
	head *item
	end *item
}
 
// NewCircularQueue creates a new circular queue
func NewCircularQueue() *CircularQueue {
	return &CircularQueue{}
}

// Enqueue adds a value to the queue
func (q *CircularQueue) Enqueue(value string) {
	new := &item{
		value: value,
	}

	if q.end == nil {
		q.end = new
	} else {
		q.end.next = new
		q.end = q.end.next
	}

	if q.head == nil {
		q.head = q.end
	}
}

// TryMoveNext attempts to move current to the next item
func (q *CircularQueue) TryMoveNext() bool {
	if q.end == nil {
		return false
	}

	if q.next == nil {
		q.next = q.head
		return true
	} 
	
	q.next = q.next.next
	if q.next == nil {
		q.next = q.head
	}

	return true
}

// Current returns the current item
func (q *CircularQueue) Current() (string, error) {
	if q.next == nil {
		return "", errors.New("failed to get current item")
	}

	return q.next.value, nil
}

queue_test.go

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func Test_Enqueue_SingleItem(t *testing.T) {
	queue := NewCircularQueue()
	assert.NotNil(t, queue)

	queue.Enqueue("test")

	ok := queue.TryMoveNext()
	assert.True(t, ok)

	item, err := queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "test", item)

	ok = queue.TryMoveNext()
	assert.True(t, ok)

	item, err = queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "test", item)
}

func Test_Enqueue_MultipleItems(t *testing.T) {
	queue := NewCircularQueue()
	assert.NotNil(t, queue)

	queue.Enqueue("one")
	queue.Enqueue("two")
	queue.Enqueue("three")

	ok := queue.TryMoveNext()
	assert.True(t, ok)

	item, err := queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "one", item)

	ok = queue.TryMoveNext()
	assert.True(t, ok)

	item, err = queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "two", item)

	ok = queue.TryMoveNext()
	assert.True(t, ok)

	item, err = queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "three", item)

	ok = queue.TryMoveNext()
	assert.True(t, ok)

	item, err = queue.Current()
	assert.Nil(t, err)
	assert.EqualValues(t, "one", item)
}

func Test_TryMoveNextBeforeEnqueue(t *testing.T) {
	queue := NewCircularQueue()
	assert.NotNil(t, queue)

	ok := queue.TryMoveNext()
	assert.False(t, ok)

}
func Test_CurrentBeforeEnqueue(t *testing.T) {
	queue := NewCircularQueue()
	assert.NotNil(t, queue)

	_, err := queue.Current()
	assert.NotNil(t, err)
}