german9304

Posted on

# 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:

``````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

1) First step is to create the linked list:

`````` 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 {
current  *node.Node
length   int
}

func (li *LinkedList) Iterator() it.IIterator {
}

return &LinkedList{nil, nil, 0}
}

}

// Prints elements from the list
func (li *LinkedList) Print() {
for head != nil {
}
}

// 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.current = newNode
li.length++
return newNode
}

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

// Removes an element from front of the list
func (li *LinkedList) RemoveFront() *node.Node {
if 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.

`````` 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)

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 {
}

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()

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.

`````` package queue

import (
"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 {
}

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 {
}
// 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

``````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: