Let's build a Queue with golang
Tags: computerscience, go, programming, datastructures
Published: 2019-12-29 21:19:11

---
title: Let's build a Queue with golang
published: true
description: data structures queue implementation
tags: #computerscience #golang #programming #datastructures
---


# Queue

Golang is a great language because it is simple to learn and it's fast compare to other languages.

Here we will build a linear data structure called queue, 
Queues are FIFO (first in first out)

For example: a waiting row of people to pay it is a que because the person who comes first pays first and etc. 

There are different ways to build a queue, you have arrays, or linkedlists and even stacks. For this implementation I used a linkedlist.

Let's begin:

### Node

We need some way to create our nodes:

```go
package node

type Node struct {
	item int
	next *Node
}

// Init Node
func New(item int) *Node {
	return &Node{item, nil}
}

func (n *Node) Item() int {
	return n.item
}

func (n *Node) Next() *Node {
	return n.next
}

func (n *Node) SetItem(item int) int {
	n.item = item
	return item
}

func (n *Node) SetNext(nextNode *Node) *Node {
	n.next = nextNode
	return n.next
}

```
Methods implemented are:

* ***Item**: returns item from node
* ***Next***: return next element 
* ***SetItem***: sets item to current node
* ***SetNext***: sets next element 


### LinkedList 
1) First step is to create the linked list:

```go
 package linkedList

import (
	"fmt"
	"stackqueue/node"
	it "stackqueue/iterator"
)


type iterator struct {
	current *node.Node
}

func (it *iterator) Next() *node.Node {
	current := it.current
	it.current = it.current.Next()
	return current
}

func (it *iterator) HasNext() bool {
	if it.current == nil {
		return false
	}

	return true
}

type LinkedList struct {
	head     *node.Node
	current  *node.Node
	length   int
}

func (li *LinkedList) Iterator() it.IIterator {
	head := li.head
	return &iterator{head}
}


func New(head, current *node.Node) *LinkedList {
	return &LinkedList{nil, nil, 0}
}

func (li *LinkedList) Head() *node.Node {
	return li.head
}

// Prints elements from the list
func (li *LinkedList) Print() {
	head := li.head
	for head != nil {
		fmt.Printf("%v\n", head.Item())
		head = head.Next()
	}
}

// Inserts at front of the list
func (li *LinkedList) Insert(item int) *node.Node {
	newNode := node.New(item) // init node
	if li.head == nil {
		li.head = newNode
		li.current = newNode
		li.length++
		return newNode
	}

	newNode.SetNext(li.current)
	li.current = newNode
	li.head = newNode
	li.length = li.length + 1
	return newNode
}

// Removes an element from front of the list
func (li *LinkedList) RemoveFront() *node.Node {
	head := li.head
	if head != nil {
		nextNode := head.Next()
		li.head = nextNode
		head = nil
	}
	return nil
}
```

This go package implements the link list so we can use it on our Queue structure. 

Methods implemented are:

* ***New***: initializes the linkedlist
* ***Append***: appends a new item at the end to the list
* ***RemoveFront***: removes an element from the front of the list
* ***Head***: returns the front of the list

We need some testing and golang has useful tools to testing, 
to test a package we just need to create a file with the name of the file that you are testing and have _test at the end for instance: filename_test.

## LinkedList Testing 

```go
 package linkedList

import (
	// "log"
	"fmt"
	"testing"
	it "stackqueue/iterator"
)

func TestInsert(t *testing.T) {
	expectedRoot := 10
	li := New(nil, nil)
	li.Insert(34)
	li.Insert(44)
	li.Insert(10)

	item := li.Head().Item()
	if item != expectedRoot {
		t.Errorf("got %v , expected %v \n", item, expectedRoot)
	}
}

func TestAppend(t *testing.T) {
	li := New(nil, nil)
	li.Append(32)
	li.Append(50)
	li.Append(100)

	head := func() int {
		return li.Head().Item()
	}

	if head() != 32 {
		t.Errorf("got %v, expected %v  \n", head(), 32)
	}

	li.RemoveFront()

	if head() != 50 {
		t.Errorf("got %v, expected %v  \n", head(), 50)
	}

	fmt.Println("iterator append")
	var iter it.IIterator = li.Iterator()
	for iter.HasNext() {
		fmt.Printf("%v\n", iter.Next().Item())
	}
	fmt.Println("iterator append")
}

func TestRemoveFront(t *testing.T) {
	numbers := []int{1, 2, 3, 4, 5, 6}
	li2 := New(nil, nil)

	if li2.RemoveFront() != nil {
		t.Errorf("should be nil")
	}


	li := New(nil, nil)
	for _, number := range numbers {
		li.Insert(number)
	}
	li.RemoveFront()

	// New Head 
	if got := li.Head().Item(); got != 5 {
		t.Errorf("got %v , expected %v \n", got, 5)
	}
	var iter it.IIterator = li.Iterator()
	for iter.HasNext() {
		fmt.Printf("%v\n", iter.Next().Item())
	}
}


func ExamplePrint() {
	numbers := []int{1, 2, 3, 4, 5, 6}
	li := New(nil, nil)
	for _, number := range numbers {
		li.Insert(number)
	}
	li.Print()
	// output:
	// 6
	// 5
	// 4 
	// 3
	// 2
	// 1
}

```

## Queue

Now that we have the linkedList we can implement the queue.

```go
 package queue

import (
	"stackqueue/linkedList"
	"stackqueue/node"
	it "stackqueue/iterator"
)


type IQueue interface {
	Enqueue(item int) *node.Node
	Dequeue() *node.Node
	Peek() *node.Node
	Iterator() it.IIterator
}

type Queue struct {
	li *linkedList.LinkedList
}


func New() *Queue {
	list := linkedList.New(nil, nil)
	return &Queue{list}
}

func (q *Queue) Iterator()  it.IIterator {
	return q.li.Iterator()
}

// Top of the list
func (q *Queue) Peek() *node.Node {
	return q.li.Head()
}
// Enqueues element
func (q *Queue) Enqueue(item int) *node.Node {
	newNode := q.li.Append(item)
	return newNode
}

// Dequeue element
func (q *Queue) Dequeue() *node.Node {
	removedNode := q.li.RemoveFront()
	return removedNode
}
```

Methods implemented are:

* ***New***: initializes the queue
* ***Enqueue***: appends an element to the front
* ***Dequeue***: removes the first element from the list 
* ***Peek***: returns first element from the list  

## Queue Testing 

```go
package queue

import (
	"testing"
	"fmt"
)

// Queue test
func TestQueue(t *testing.T) {
	var queue IQueue = New()
	queue.Enqueue(32)
	queue.Enqueue(40)
	queue.Enqueue(100)

	peek := queue.Peek().Item()
	if peek != 32 {
		t.Errorf("got %v expected \n", peek)
	}

	iter := queue.Iterator()
	for iter.HasNext() {
		fmt.Printf("item %v \n", iter.Next().Item())
	}
}

func TestDequeue(t *testing.T) {
	var queue IQueue = New()
	queue.Enqueue(32)
	queue.Enqueue(40)
	queue.Enqueue(100)
	queue.Enqueue(2)

	queue.Dequeue()

	fmt.Println("iterator Dequeue")
	iter := queue.Iterator()
	for iter.HasNext() {
		fmt.Printf("item %v \n", iter.Next().Item())
	}
	fmt.Println("iterator Dequeue")

	peek := queue.Peek()
	if peek.Item() != 40 {
		t.Errorf("wrong dequeue")
	}
	queue.Dequeue()

	peek = queue.Peek()
	if peek.Item() != 100 {
		t.Errorf("wrong dequeue")
	}
}
```

Queues are a great and fundamental data structures to learn. Fundamentals are good to learn and have a better ida of it. 


Thank you for reading the post, I will implement the stack and give a better explanation of what is a linked list on my next posts. 

Let me know what you think, thank you again!. 

source code:
{% github https://github.com/german9304/datastructures-go %}