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:
Data Structures
- Linked Lists
- Binary Search Tree
- queue
- stack
golang
Latest comments (0)