Exploring Stacks with Kotlin

Greetings! Today, we're exploring Stacks, a crucial data structure in computer science. A stack can be likened to a pile of plates: you add a plate to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle is fundamental to understanding stacks. This lesson will guide you through the stack data structure, its operations, and its applications. Let's get started!

To create a stack, we can use a MutableList in Kotlin. For the Push operation, we use add(), which inserts an element at the end of the list. For the Pop operation, there's the removeAt() function that removes the last element, simulating the removal of the 'top' element in a stack. Here's how it looks:

fun main() {
    val stack = mutableListOf<String>() // A new empty stack

    // Push operations
    stack.add("John")
    stack.add("Mary")
    stack.add("Steve")

    stack.removeAt(stack.size - 1) // Pop operation removes 'Steve'
    println(stack) // Outputs: [John, Mary]
}

In the example provided, we add 'John', 'Mary', and 'Steve' to the stack and then remove 'Steve' from it.

Stack operations go beyond merely add and removeAt. For example, to verify if a stack is empty, we can use the isEmpty() method. If it returns true, the stack is empty. Conversely, if it returns false, the stack is not empty. To peek at the top element of the stack without popping it, we use indexing with stack.last().

Here's an example:

fun main() {
    val stack = mutableListOf<String>()
    stack.add("Steve")
    stack.add("Sam")
    
    println(stack.last()) // Outputs: 'Sam'

    println(stack.isEmpty()) // Outputs: false
    stack.removeAt(stack.size - 1) // Remove 'Sam'
    stack.removeAt(stack.size - 1) // Remove 'Steve'
    println(stack.isEmpty()) // Outputs: true
}

In this example, 'Sam' is added and then the topmost stack element, which is 'Sam', is peeked.

Practical applications of stacks are plentiful. Here is one of them — reversing a string.

We will push all characters into a stack and then pop them out to get a reversed string!

fun reverseString(input: String): String {
    val stack = mutableListOf<Char>()

    for (c in input) {
        stack.add(c)
    }

    val reversedString = StringBuilder()
    while (stack.isNotEmpty()) {
        reversedString.append(stack.removeAt(stack.size - 1))
    }

    return reversedString.toString()
}

fun main() {
    println(reverseString("HELLO")) // Outputs: OLLEH
}