Implement Stack in Kotlin

First of all, what's Stack? Stack is as the name suggests a way of storing data where data that came in last goes out first (LAST IN FIRST OUT). In other words, a stack data structure is like a pile of books where the first book you can take is the one on top which was placed last as shown in the below illustration

Now that we have some idea of how Stack data structure works lets dive into implementation.

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

interface Stack<T> {
    fun push(value: T)
    fun peek(): T
    fun pop(): T
    fun isEmpty(): Boolean
}

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

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

A short explanation of the code above in real pile of books analogy. StackNode is the single book in the stack. It knows itself (value) and the next book in the stack above it (next). The next book is nullable because there might be a case when there is only one book in the stack and there is no book above it in the stack.

Now, we need to implement our actual Stack implementation in the StackImpl class below

class StackImpl<T>: Stack<T> {
    private var head: StackNode<T>? = null

    override fun push(value: T) {
        val node = StackNode(value)
        node.next = head
        head = node
    }
    override fun peek(): T {
        return head?.value ?: throw NoSuchElementException()
    }
    override fun pop(): T {
        val value = head?.value ?: throw NoSuchElementException()
        head = head?.next
        return value
    }
    override fun isEmpty(): Boolean {
        return head == null
    }
}

In StackImpl class to be able to handle our stack in the most efficient way we need a single variable of StackNode, head. The head represents the item on top of the stack. We do not have to know anything about what is next item as StackNode already has a reference to the next item in the stack.

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