   ## 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). 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 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 the 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)
• 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]
• The Queue of airplanes 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 a 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 the 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 a parameter, which means we can pass a 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){
}``````

### 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 are 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 are no elements in Queue.

We have to use Nullable types when there is a chance that the value could be null, also normal types will not accept null as a 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) ``````fun peek():Any?{
if (this.isEmpty()){
return null
} else {
return items
}
}``````

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

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

fun peek():Any?{
return items
}
}

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

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

The 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 the basic requirements of Queue when we implement with arrays.

I was thinking, where to implement the logic of shifting elements in the 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 a 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 a few basic requirements, or point we got to remember.

• First, we have to have a 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 the user or not. I do not think the 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 a dynamic object like List or set
• If we want a 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 a 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
• The 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 the 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 to 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 the index of the first(oldest) element, it always points to an index of the oldest element in the array
• rear : rear variable always points to the 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++
}

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

The output of the Queue implemented with an array.

``````Adding: 4
1
removed: 4
0
1