Implementing and Understanding Queues in Kotlin

Today, we will explore Queues in Kotlin. Queues in computer science are First-In, First-Out (FIFO) structures. Consider this example: you're at a theme park — the first person in line for the roller coaster gets on first. Today's lesson revolves around this straightforward yet powerful concept. So, let's dive in!

Let's explore the implementation of Queues in Kotlin using an IntArray and pointers for efficient operations. Here's how we can define the Queue:

class Queue(private val capacity: Int) {
    private val array: IntArray = IntArray(capacity)
    private var front: Int = 0
    private var rear: Int = -1
    private var size: Int = 0

    // Will return true if the Queue is full
    fun isFull(): Boolean {
        return size == capacity
    }

    // Will return true if the Queue is empty
    fun isEmpty(): Boolean {
        return size == 0
    }
}

In this implementation, the Queue class uses an IntArray to store elements. The front and rear pointers keep track of the first and last element positions, respectively. The capacity is stored as a property so it can be referenced throughout the class.

Enqueue, a fancy term, denotes adding an item to the queue — the item lines up at the rear. The enqueue() method checks if our queue has enough space before adding the item to the end of the queue.

fun enqueue(item: Int) {
    if (isFull()) return
    rear = (rear + 1) % capacity
    array[rear] = item
    size++
}

The enqueue() method uses the modulo operator to handle the circular nature of the queue.

Just as enqueue adds an element to our queue, dequeue removes it. It extracts the element at the queue's front, reducing its size. However, we encounter an underflow condition if there are no elements to remove.

fun dequeue(): Int? {
    if (isEmpty()) return null
    val item = array[front]
    front = (front + 1) % capacity
    size--
    return item
}

The dequeue() method checks for emptiness before removing and returning the first element.