Stack Data Structure Implementation in Kotlin

Author:

In this tutorial, we will write a Program to implement the Stack data structure using the Kotlin programming language. 

A stack is an ordered list in which insertion and deletion are done at one end, called a top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out (FILO) list.

Stack Implementation in Kotlin

Stack Concepts

  1. When an element is inserted in a stack, the concept is called a push.
  2. When an element is removed from the stack, the concept is called pop.
  3. Trying to pop out an empty stack is called underflow (treat as an Exception).
  4. Trying to push an element in a full stack is called overflow (treat as an Exception).

Main stack operations

Push Operation:
The process of putting a new data element onto the stack is known as a Push Operation.

Pop Operation:
Accessing the content while removing it from the stack, is known as a Pop Operation.

Let's Implement Stack to perform the below operations:
push()
pushAll()
pop()
peek()
isEmpty
isFull()
Here is the complete Kotlin program with output to implement the Stack:
import java.util.Arrays

class Stack<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)
    }

    constructor(elements: Array<E>) {
        this.elements = elements as Array<Any?>
        size += elements.size
    }

    fun push(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 pushAll(newElements: Array<E>) {
        val newSize = size + newElements.size
        if (elements.size < newSize) {
            // New sizing can be of any logic as per requirement
            val newArray = arrayOfNulls<Any>(newSize + minCapacityIncrement)
            System.arraycopy(elements, 0, newArray, 0, size)
            elements = newArray
        }
        System.arraycopy(newElements, 0, elements, size, newElements.size)
        size = newSize
    }

    fun pop(): E {
        if (size == 0) throw StackUnderflowException()
        val index = --size
        val obj = elements[index]
        elements[index] = null
        return obj as E
    }

    fun pop(count: Int) {
        if (size == 0 || size < count) throw StackUnderflowException()
        for (i in 0 until count) {
            elements[--size] = null
        }
    }

    fun peek() = try {
        elements[size - 1] as E
    } catch (e: IndexOutOfBoundsException) {
        throw StackUnderflowException();
    }

    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 StackUnderflowException : RuntimeException()

inline fun <reified T> stackOf(vararg elements: T) = Stack<T>(elements as Array<T>)

fun main(args: Array<String>) {
    val animals = Stack<String>(10)
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")

    animals.push("Lion")
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")

    animals.push("Tiger")
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")

    animals.push("Crocodile")
    animals.push("Cat")
    animals.push("Dog")
    animals.push("Cow")
    animals.push("Cangaroo")
    animals.push("Rat")
    animals.push("Bull")
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
    animals.push("Ox")
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
    animals.push("Zebra")
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")
    animals.pop()
    System.out.println("$animals - Empty? -- ${animals.isEmpty()}")

    println()
    val languages = Stack(arrayOf("Kotlin", "Java"))
    println("$languages - Empty? -- ${languages.isEmpty()}")
    languages.push("C")
    println("$languages - Empty? -- ${languages.isEmpty()}")
    languages.pop()
    println("$languages - Empty? -- ${languages.isEmpty()}")
    languages.pop()
    println("$languages - Empty? -- ${languages.isEmpty()}")
    languages.pop()
    println("$languages - Empty? -- ${languages.isEmpty()}")

    testPushAll()
    testPop()
    testStackOf()
}

fun testPushAll() {
    println()
    println("Testing pushAll")
    val numbers = Stack<Int>(10)
    numbers.pushAll(Array<Int>(100) { i -> i })
    println(numbers)
    numbers.pop()
    numbers.pushAll(arrayOf(1, 2, 12, 909))
    println(numbers)
}

fun testPop() {
    println()
    println("Testing pop count")
    val numbers = Stack<Int>(10)
    numbers.pushAll(Array<Int>(100) { i -> i })
    println(numbers)
    numbers.pop(20)
    numbers.pushAll(arrayOf(1, 2, 12, 909))
    println(numbers)
}

fun testStackOf() {
    val languages = stackOf("Kotlin", "Java")
    println(languages)
    languages.push("C")
    println(languages)
    languages.pop()
    println(languages)
}

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
[Lion, Tiger, Crocodile, Cat, Dog, Cow, Cangaroo, Rat, Bull, Ox] - Empty? -- false

[Kotlin, Java] - Empty? -- false
[Kotlin, Java, C] - Empty? -- false
[Kotlin, Java] - Empty? -- false
[Kotlin] - Empty? -- false
[] - Empty? -- true

Testing pushAll
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 1, 2, 12, 909]

Testing pop count
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 1, 2, 12, 909]
[Kotlin, Java]
[Kotlin, Java, C]
[Kotlin, Java]

Related Data Structures and Algorithms in Kotlin

Comments

Post a Comment

Leave Comment