In this source code example, we will write a code to implement the Deque data structure using the Kotlin programming language.
A double-ended queue or deque has the feature of adding and removing elements from either end.
Deque Implementation in Kotlin
Let's Implement Deque to perform the below operations:
enqueueFront()
enqueueRear()
dequeueFront()
dequeueRear()
front()
rear()
isEmpty()
isFull()
Here is the complete code to implement Deque in Kotlin:
import java.util.Arrays
class Deque<E> {
private val minCapacityIncrement = 12
private var elements: Array<Any?>
private var size = 0
constructor() {
this.elements = arrayOf()
}
constructor(initialCapacity: Int) {
this.elements = arrayOfNulls(initialCapacity)
}
fun enqueueFront(element: E) {
if (size == elements.size) {
val newArray = arrayOfNulls<Any>(size + if (size < minCapacityIncrement / 2)
minCapacityIncrement
else
size shr 1)
System.arraycopy(elements, 0, newArray, 1, size)
elements = newArray
} else {
System.arraycopy(elements, 0, elements, 1, size)
}
elements[0] = element
size++
}
fun enqueueRear(element: E) {
if (size == elements.size) {
val newArray = arrayOfNulls<Any>(size + if (size < minCapacityIncrement / 2)
minCapacityIncrement
else
size shr 1)
System.arraycopy(elements, 0, newArray, 0, size)
elements = newArray
}
elements[size++] = element
}
fun dequeueFront(): E {
if (size == 0) throw DequeUnderflowException()
val oldVal = elements[0]
elements[0] = null
System.arraycopy(elements, 1, elements, 0, --size)
return oldVal as E
}
fun dequeueRear(): E {
if (size == 0) throw DequeUnderflowException()
val oldVal = elements[--size]
elements[size] = null
return oldVal as E
}
fun front() = try {
elements[0] as E
} catch (e: IndexOutOfBoundsException) {
throw DequeUnderflowException();
}
fun rear() = try {
elements[size - 1] as E
} catch (e: IndexOutOfBoundsException) {
throw DequeUnderflowException();
}
fun isEmpty() = size == 0
fun isFull() = size == elements.size
override fun toString(): String {
if (size == 0) return "[]"
val length = size - 1
val builder = StringBuilder(size * 16)
builder.append('[')
for (i in 0 until length) {
builder.append(elements[i])
builder.append(", ")
}
builder.append(elements[length])
builder.append(']')
return builder.toString()
}
}
class DequeUnderflowException : RuntimeException()
fun main(args: Array<String>) {
val animals = Deque<String>(10)
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.enqueueRear("Lion")
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.enqueueRear("Tiger")
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.enqueueRear("Crocodile")
animals.enqueueRear("Cat")
animals.enqueueRear("Dog")
animals.enqueueRear("Cow")
animals.enqueueRear("Cangaroo")
animals.enqueueRear("Rat")
animals.enqueueRear("Bull")
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.enqueueRear("Ox")
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.enqueueRear("Zebra")
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.dequeueFront()
System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
animals.dequeueFront()
println("Animals - $animals")
animals.dequeueRear()
println("Animals - $animals")
animals.enqueueFront("Zebra")
println("Animals - $animals")
animals.enqueueRear("Tiger")
println("Animals - $animals")
animals.enqueueFront("Octopus")
println("Animals - $animals")
}
Output:
[] - Empty? -- true
[Lion] - Empty? -- false
[Lion, Tiger] - Empty? -- false
[Lion, Tiger, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull] - Empty? -- false
[Lion, Tiger, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox] - Empty? -- false
[Lion, Tiger, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox, Zebra] - Empty? -- false
[Tiger, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox, Zebra] - Empty? -- false
Animals - [Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox, Zebra]
Animals - [Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox]
Animals - [Zebra, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox]
Animals - [Zebra, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox, Tiger]
Animals - [Octopus, Zebra, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox, Tiger]
Comments
Post a Comment