Implement Queue in Kotlin

First of all, what is Queue? Queue is as the name suggests, like in real life whoever came in first should go first (FIRST IN FIRST OUT). Whatever values we push to the Queue should be popped in the order they have been pushed as visualized below:

Now that we have clarified the concept, let's code it out in Kotlin.

First of all, we need to define our Queue interface below

interface Queue<T> {
    fun add(value: T)
    fun peek(): T
    fun remove(): T
    fun isEmpty(): Boolean
}

Before we proceed with the implementation of the Queue interface lets define a single entity in the queue with the class below.

data class QueueNode<T>(val value: T, var next: QueueNode<T>? = null)

A short explanation of the code above in real human queue analogy. QueueNode is the single person in the queue. He knows himself (value) and the next person in the queue behind him (next). The next person is nullable because there might be a case when there is only one person in the queue and there is no next person behind him in the queue.

Now, we need to implement our actual Queue implementation in the QueueImpl class below

class QueueImpl<T>: Queue<T> {
    private var head: QueueNode<T>? = null
    private var tail: QueueNode<T>? = null

    /*
        First, a node(QueueNode) is created and assigned to the end(tail) of the queue.
        Second, we make the newly created node tail. It's logical for new node to be in the end of the queue
    */
    override fun add(value: T) {
        val node = QueueNode(value)
        tail?.next = node
        tail = node
        if (head == null) head = tail
    }

    override fun peek(): T {
        return head?.value ?: throw NoSuchElementException()
    }

    /*
        First, we get the first(head) person in the queue
        Second, we make next person as first(head) person in the queue
        Third, head of the queue is returned
    */
    override fun remove(): T {
        val value = head?.value ?: throw NoSuchElementException()
        head = head?.next
        if (head == null) {
            tail = null
        }
        return value
    }

    override fun isEmpty(): Boolean {
        return head == null
    }
}

In QueueImpl class to be able to handle our queue in the most efficient way we need two variables of QueueNode, head and tail. The head represents the first person in the queue and tail represents the last person in the queue. That is actually what we need to manage the queue. We do not have to know anything about what is in between head and tail as QueueNode already has a reference to the next person in the queue.

That's all! Hope the above explanation of the implementation of the Queue data structure was helpful. If it was helpful don't forget to 👍