Deque in Kotlin
A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue but It has two ends, a front, and a rear. We can add or remove the items from the front and read end of a Deque data structure.
Methods of Deque interface
- addFirst() : Inserts the specified element at the beginning of the Deque.
- peekFirst() : Returns the first element of Deque, or null if the Deque is empty.
- getFirst() : It returns the first element of the Deque.
- removeFirst() : Returns and removes the first element of Deque.
- addLast() : Inserts the specified element at the end of the Deque.
- getLast() : It returns the last element of the Deque.
- peekLast() : Returns the last element of Deque, or null if the Deque is empty.
- removeLast() : Returns and removes the last element of Deque.
- size() : Returns the number of elements present in Deque.
- isDequeEmpty() : returns boolean True if the deque is empty otherwise false
Deque in Kotlin | Data Structures
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 backingList : MutableList<Any> = arrayListOf()
addFirst()
addFirst() function adds the element to list but at the first, to the left of an already existing element
fun addFirst(element:Any){
backingList.add(0,element)
}
getFirst()
getFirst() function fetches the first element also removes the first element from the deque. returns null if there are no elements
get first has below steps of operations:
- First things first, let’s check if it’s already empty. If it is empty we’ll have to deal with the underflow.
- The next step after that is to then capture the item we’re about to remove so we can return it to our user, we are targeting for first element
- Once we’ve captured the item we want, now remove the first element.
- The Last step is then to return the item we just deleted/removed.
fun getFirst():Any?{
if (backingList.isEmpty()){
return null
}
val value = backingList.first()
removeFirst()
return value
}
removeFirst()
removeFirst removes the first element from the Queue
fun removeFirst(){
if (backingList.isNotEmpty()) backingList.removeAt(0)
}
peekFirst()
peekFirst() fetches the first element from the deque using the first() function from the list. If the deque is empty then peekFirst() will return null. peekFirst() has no effect a Deque size
fun peekFirst(): Any?{
// using if else as expression
return backingList.firstOrNull()
}
addLast()
addLast() function will add the element at the rear end of the queue using add() function from the list
fun addLast(element:Any){
backingList.add(element)
}
getLast()
getLast() function will fetch the last element as well as removes it after making sure that Deque has an element to remove
fun getLast():Any?{
if (backingList.isEmpty()){
return null
}
val value = backingList.last()
removeLast()
return value
}
removeLast()
removeLast() removes the last method from the Deque. Before removing element we want to check whether the Dequ has an element to remove.
removeLast() function will not return any value, it just removes. Some people might write that removeLast() will fetch and removes the element
- First things first, let’s check if it’s already empty. If it is empty we’ll have to deal with the underflow.
- The next step after that is to then capture the item we’re about to remove so we can return it to our user, we are targeting for last element
- Once we’ve captured the item we want, now remove the last element.
- The last step is then to return the item we just deleted/removed.
fun removeLast(){
if (backingList.isNotEmpty()) backingList.removeAt(backingList.size - 1)
}
peekLast()
peekLast function fetches the last element from the rear end, this function returns null.
lastOrNull() function is used to get value
fun peekLast():Any?{
return backingList.lastOrNull()
}
size()
size() function returns the number of elements present in the Deque, if there are no elements then the function returns 0.
fun size():Int{
return backingList.size
}
isDequeEmpty()
isDequeEmpty() function verifies whether the Deque is empty or not, if the Deque is empty then the isDequeEmpty() function returns true, false in-case if there is any element in Deque.
This method internally uses the isEmpty() function from the list
fun isDequeEmpty():Boolean{
return backingList.isEmpty()
}
Complete example for deque in kotlin using list implementation
class Deque(){
var backingList : MutableList<Any> = arrayListOf()
fun addFirst(element:Any){
backingList.add(0,element)
}
fun getFirst():Any?{
if (backingList.isEmpty()){
return null
}
val value = backingList.first()
removeFirst()
return value
}
fun removeFirst(){
if (backingList.isNotEmpty()) backingList.removeAt(0)
}
fun peekFirst(): Any?{
// using if else as expression
return backingList.firstOrNull()
}
fun addLast(element:Any){
backingList.add(element)
}
fun getLast():Any?{
if (backingList.isEmpty()){
return null
}
val value = backingList.last()
removeLast()
return value
}
fun removeLast(){
if (backingList.isNotEmpty()) backingList.removeAt(backingList.size - 1)
}
fun peekLast():Any?{
return backingList.lastOrNull()
}
fun size():Int{
return backingList.size
}
fun isDequeEmpty():Boolean{
return backingList.isEmpty()
}
}
fun main(args: Array<String>) {
var deq = Deque()
println(deq.isDequeEmpty())
println(deq.addFirst("karthiq"))
println(deq.isDequeEmpty())
println(deq.addLast(false))
println(deq.getLast())
println(deq.size())
println(deq.peekFirst())
println(deq.peekLast())
deq.removeLast()
deq.removeFirst()
}
true
kotlin.Unit
false
kotlin.Unit
false
1
karthiq
karthiq