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:

Kotlin
Copy to clipboard
1fun main() {
2    val stack = mutableListOf<String>() // A new empty stack
3
4    // Push operations
5    stack.add("John")
6    stack.add("Mary")
7    stack.add("Steve")
8
9    stack.removeAt(stack.size - 1) // Pop operation removes 'Steve'
10    println(stack) // Outputs: [John, Mary]
11}

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:

Kotlin
Copy to clipboard
1fun main() {
2    val stack = mutableListOf<String>()
3    stack.add("Steve")
4    stack.add("Sam")
5    
6    println(stack.last()) // Outputs: 'Sam'
7
8    println(stack.isEmpty()) // Outputs: false
9    stack.removeAt(stack.size - 1) // Remove 'Sam'
10    stack.removeAt(stack.size - 1) // Remove 'Steve'
11    println(stack.isEmpty()) // Outputs: true
12}

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!

Kotlin
Copy to clipboard
1fun reverseString(input: String): String {
2    val stack = mutableListOf<Char>()
3
4    for (c in input) {
5        stack.add(c)
6    }
7
8    val reversedString = StringBuilder()
9    while (stack.isNotEmpty()) {
10        reversedString.append(stack.removeAt(stack.size - 1))
11    }
12
13    return reversedString.toString()
14}
15
16fun main() {
17    println(reverseString("HELLO")) // Outputs: OLLEH
18}

A stack can be utilized to verify if parentheses in an expression are well-matched, i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]" are well-matched, while in strings "([]()", ")()[]{}", "([)]", and "[{})" they are not.

Let's break down the solution into simple steps:

We start by creating a map that maps each closing bracket to its corresponding opening bracket and an empty stack. Then, we iterate over each character paren in the string parenString:

• If paren is an opening bracket, it gets appended to the stack.
• If paren is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.
• If neither of the above conditions is met, we return false.

Finally, if the stack is empty (all opening brackets had matching closing brackets), we return true. If there are some unmatched opening brackets left, we return false.

Kotlin
Copy to clipboard
1fun isParenBalanced(parenString: String): Boolean {
2    val stack = mutableListOf<Char>()
3    val openingParen = mapOf(')' to '(', ']' to '[', '}' to '{')
4
5    for (paren in parenString) {
6        if (openingParen.containsValue(paren)) {
7            // We met an opening parenthesis, just putting it on the stack
8            stack.add(paren)
9        } else if (openingParen.containsKey(paren)) {
10            // We met a closing parenthesis
11            if (stack.isEmpty() || stack.removeAt(stack.size - 1) != openingParen[paren]) {
12                return false
13            }
14        }
15    }
16
17    return stack.isEmpty()
18}
19
20fun main() {
21    println(isParenBalanced("(())")) // Outputs: true
22    println(isParenBalanced("({[)}")) // Outputs: false
23}

Congratulations! You've learned about the stack data structure, its operations, and its applications in a programming context using Kotlin. Stack concepts are essential building blocks in computer science and programming. Next, dive into practice exercises to reinforce your understanding of stacks!