Let's build a Queue with golang

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

LinkedList

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

 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.

 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

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:

german9304 / datastructures-go

Data Structures

• Linked Lists
• Binary Search Tree
• queue
• stack

golang

View on GitHub