Queue in Kotlin | Data Structure

A queue is a simple data structure that allows elements to be inserted from one end, called the rear (also called tail), and deleted from the other end, called the front (also called head).

queue-data-structure-kotlin

In order to understand queue in kotlin, consider a group of people climbing a ladder, the person to climb first will be the first one to get down, which is similar to a queue of line, where the first person to get in the queue is the first one to get out of it.

So, a queue is a linear data structure, A very important point is that a queue deletes only the oldest added element.

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is called FIFO, first-in first-out. It is also known as first-come first-served.

Queues are a very prevalent model for data flow in real life. Consider an office with 30 computers networked with a single printer. When somebody wants to print, their print tasks “get in line? with all the other printing tasks that are waiting. The first task in is the next to be completed. If you are last in line, you must wait for all the other tasks to print ahead of you.

Methods in Queue :

It is an abstract data type, which means that we can create our own function in the Queue, but mostly the queues will contain below functions.

  • enqueue() : add (store) an item to the queue.
  • dequeue() : remove (access) an item from the queue.
  • peek() : Gets the element at the front of the queue without removing it
  • size : Get number of elements in the Queue
  • isEmpty() : Checks if the queue is empty
  • You can add more functions if you need as the Queue is just an abstract/concept

Usage of Queues :

  • When your ticket is in the waiting list. (Mostly railways and buses)
  • CPU task scheduling
  • When you call a service center and told to wait(when all support people are busy), your call enters a queue. etc [end of thinking capacity]
  • Queue of air planes waiting for landing instructions

Queue implementation using list in Kotlin

We will be using a MutableList to create the Queue data structure, we are using the MutableList make the Queue to grow dynamically.

We would be accepting a MutableList parameter in Primary constructor, so based on this we will be creating a Queue. If you like to have more than one constructor, you can create secondary constructors.


var items:MutableList<Any> = list		

isEmpty()

In queue implementation, we are going to create an function called isEmpty(), this method will check whether given Queue is empty or not.

Empty means there is no elements present in the Queue, so we would be returning the Boolean value from this function.


fun isEmpty():Boolean = items.isEmpty()		

size()

size() method helps user to retrieve the number of elements present in the Queue. If there is no element then the size will be 0(zero).

For fetching the size, we can use the count() function from the List, The size function returns an Integer value representing the number of elements


fun size():Int = items.count()		

enqueue(element:Any)

enqueue() function accepts Any as parameter, which means we can pass value to the enqueue() function in the Queue.

enqueue() function will add the given element to the Queue using the add() function from the list, this function will not return any value which means return type is Unit

When we add an element to the Queue, the element will be added at the end.

when we do not mention any return type, then by default the return type becomes Unit type in kotlin

fun enqueue(element:Any){
	items.add(element)
}		

dequeue()

dequeue() function will remove element which got inserted at the first, dequeue() function will not accept any parameter.

We have to check whether there are elements in Queue to remove, if elements present we can remove the elements using removeAt(0) function from the list(0 points to the first element index).

If there is no elements to remove then we have to return null. The return type of the dequeue() function is Nullable type Any?, because we return null if there is no elements in Queue.

We have to use Nullable types when there is chance that the value could be null, also normal types will not accept null as value.

fun dequeue():Any?{
	if (this.isEmpty()){
		return null
	} else {
		return items.removeAt(0)
	}
}		

peek()

peek() function will fetch the element which is in the front end of the Queue, in other words peek() gets the elements which next to be chopped/removed ( while writing this I was thinking about the chickens at the Shop waiting to be chopped).

You can have a check whether the Queue has any elements or not, if not return null, so the return type would be ______ (have a guess) peek-in-queue-kotlin


fun peek():Any?{
	if (this.isEmpty()){
		return null
	} else {
		return items[0]
	}
}	

Complete program for implementation of Queue using list in kotlin


class Queue (list:MutableList<Any>){

    var items:MutableList<Any> = list

    fun isEmpty():Boolean = items.isEmpty()

    fun size():Int = items.count()

    override  fun toString() = items.toString()

    fun enqueue(element:Any){
        items.add(element)
    }

    fun dequeue():Any?{
        if (this.isEmpty()){
            return null
        } else {
            return items.removeAt(0)
        }
    }

    fun peek():Any?{
        return items[0]
    }
}

fun main(args: Array<String>) {
    var a = Queue(mutableListOf("karthiq",2,3,"four"))

    //add 7 to Queue
    println(a.enqueue(7))
    println(a)//prints all elements
    //remove from Queue
    println(a.dequeue())
    println(a)//prints all elements present
    // fetch what is first element
    println(a.peek())
    println(a)
    // print the number of elements
    println(a.size())
    // check whether Queue is empty
    println(a.isEmpty())
}		

Output of the Queue Operations


[karthiq, 2, 3, four, 7]
karthiq
[2, 3, four, 7]
2
[2, 3, four, 7]
4
false

Queue implementation using Arrays in Kotlin | Re-sizable Queue

Before Proceeding to programs lets understand basic requirements of Queue when we implement with arrays.

I was thinking, where to implement the logic of shifting elements in array when we remove an elements

I was thinking above point, some years back I learned how ArrayList is implemented using arraysI(in java). While implementing the Queue I was able to recall it bits and pieces but I did not get very clear picture to implement Queue.

Yes, I did convert the java example into Kotlin, but I did understand it and I am going to explain my understanding of the Queue implementation using Arrays.

Let's skip the bullshit
Below are few basic requirements, or point we got to remember.

  • First we have to have variable to track the front, rear, currentSize, capacity and queueArr( array Object to store values)
  • We have created the variable, now we have to think whether to show these variable to user or not. I do not think user has anything to do with these variables, so make them private
  • After variable we have to think about, whether we want a grow-able(dynamic) Queue or Fixed size Queue (Queue which accept elements based on capacity). Why this question occurred to me is, Array is not dynamic object like List or set
  • If we want Growable Queue then What is the Growth logic. Most of the people will say use growth logic as currentSize *2 , Some intelligent people will say use the currentSize * 1.5
    • If Logic is currentSize * 2 growth will be like, considering 6 as base capacity. Growth is 6, 12, 24, 48, 96, ...
    • if Logic is currentSize * 1.5 growth will be like 6, 9, 13, 19,... goes on
    • How you can decide the logic is, based on the memory size you want to allocate. For example, if you have 1,00,000 (one lakh) elements in array, if you use *2 then next moment you will be allocating memory for 2,00,000 (two lakh) elements, but if you use *1.5 the memory allocation is for 1,50,000 (one lakh fifty thousand) elements
  • Final one is, when you want to shift the array elements. What I mean is,
    Strategy 1 : when you dequeue() an element from the Queue, the first place will not have any value, so now, do you want to shift all element so that full array is occupied

    Or

    Strategy 2 : are we going to have a tracker to keep the track of first element, so that while copying the old array to new array we would be copying only from this point. I will be using Strategy 2
  • You got to decide, what all are the methods you want to expose

Variables :

We have 5 variables in our Queue

  • capacity : base capacity, based this capacity we will be used create the array. In simple terms, it is nothing but base array size
  • queueArr : The array that we are creating using the capacity, this array is nothing but our Queue, this holds all the values when the array is full we will create new array(with more capacity) and we move all the elements from this array
  • front : front is nothing but index of the first(oldest) element, it always points to index of the oldest element in the array
  • rear : rear variable always points to index of the last added element, this will new element's index
  • currentSize : Current size is nothing but the total number of elements in the array

private val capacity = 6
private var queueArr: IntArray = IntArray(this.capacity)
private var front = 0
private var rear = -1
private var currentSize = 0		

The complete example of Queue implemented using arrays in Kotlin



class DynamicQueueArray {
    private val capacity = 6
    private var queueArr: IntArray = IntArray(this.capacity)
    private var front = 0
    private var rear = -1
    private var currentSize = 0


    fun enqueue(item: Int) {

        if (isQueueFull()) {
            println("Queue is full, increase capacity...")
            increaseCapacity()
        }
        rear++
        if (rear >= queueArr.size && currentSize !== queueArr.size) {
            rear = 0
        }
        queueArr[rear] = item
        currentSize++
        println("Adding: $item")
    }

    fun dequeue() {
        if (isQueueEmpty()) {
            // you can raise an exception if you want
            println("Underflow ! Unable to remove element from Queue")
        } else {
            front++
            if (front > queueArr.size - 1) {
                System.out.println("removed: " + queueArr[front - 1])
                front = 0
            } else {
                System.out.println("removed: " + queueArr[front - 1])
            }
            currentSize--
        }
    }
    fun peek():Int? {
        if (isQueueEmpty()) {
            // you can raise an exception if you want
            println("Underflow ! Unable to remove element from Queue")
            return null
        } else {
            return queueArr[front]
        }
    }

    fun size():Int {
        return currentSize
    }

    private fun isQueueFull(): Boolean {
        var status = false
        if (currentSize === queueArr.size) {
            status = true
        }
        return status
    }

    fun isQueueEmpty(): Boolean {
        var status = false
        if (currentSize === 0) {
            status = true
        }
        return status
    }

    private fun increaseCapacity() {

        //create new array with double size as the current one.
        val newCapacity = this.queueArr.size * 2
        val newArr = IntArray(newCapacity)
        //copy elements to new array, copy from rear to front
        var tmpFront = front
        var index = -1
        while (true) {
            newArr[++index] = this.queueArr[tmpFront]
            tmpFront++
            if (tmpFront == this.queueArr.size) {
                tmpFront = 0
            }
            if (currentSize === index + 1) {
                break
            }
        }
        //make new array as queue
        this.queueArr = newArr
        System.out.println("New array capacity: " + this.queueArr.size)
        //reset front & rear values
        this.front = 0
        this.rear = index
    }
}

fun main(args: Array<String>) {
    val queue = DynamicQueueArray()
    queue.enqueue(4)
    println(queue.size())
    queue.dequeue()
    println(queue.size())
    queue.enqueue(56)
    println(queue.size())
    queue.enqueue(67)
    println(queue.size())
    println(queue.dequeue())
    println(queue.size())
    println(queue.peek())
    println(queue.size())
    println(queue.isQueueEmpty())
}

Output of Queue implemented with array.


Adding: 4
1
removed: 4
0
Adding: 56
1
Adding: 67
2
removed: 56
kotlin.Unit
1
67
1
false		

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group