A Comprehensive Guide to Kotlin Stack Data Structure

A stack is a linear data structure that adheres to the Last-In-First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. This concept is similar to a physical stack of objects, where items are both added and removed from the top.

What is a Stack Data Structure?

A stack data structure is a fundamental concept in computer science and programming. It is a linear data structure where elements are added and removed from only one end, known as the top of the stack. This behavior makes stacks an excellent choice for various scenarios, such as parsing expressions, evaluating postfix notation, and implementing recursive algorithms.

Key Characteristics of a Stack

LIFO Principle: The last element added to the stack will be the first one to be removed. This is known as Last-In-First-Out (LIFO).
Top of the Stack: The top element is the most recently added element. All stack operations occur at this point.

Operations on a Stack

Push Operation

The push operation adds a new element to the top of the stack. In Kotlin, this can be achieved using the fun push method.

1
2
3
4
5
6
7
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }
}

Pop Operation

The pop operation removes the top element from the stack. If the stack is empty, it may return null or throw an exception, depending on the implementation. Here's how you can implement the fun pop method:

1
2
3
4
5
6
7
8
9
10
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }
}

Peek Operation

The peek operation returns the top element without removing it from the stack. This is useful when you need to examine the top element without modifying the stack.

1
2
3
4
5
6
7
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun peek(): T? {
        return elements.lastOrNull()
    }
}

Implementing a Stack in Kotlin

In Kotlin, you can implement a stack using various approaches, including leveraging Kotlin's collections or using Java's built-in Stack class. Here's a concise guide on how to implement a stack using these methods.

To create a stack in Kotlin, you can use either the built-in Stack class from Java or Kotlin's MutableList.

Using a MutableList

Using a MutableList, you can perform stack operations such as push and pop. Here's how you can do it:

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
fun main() {
    val stack = mutableListOf<Int>()

    // Push operation
    fun push(item: Int) {
        stack.add(item)
    }

    // Pop operation
    fun pop(): Int? {
        if (stack.isNotEmpty()) {
            return stack.removeAt(stack.size - 1)
        }
        return null
    }

    // Using the stack
    push(1)
    push(2)
    push(3)
    println(stack)  // Output: [1, 2, 3]

    println(pop())  // Output: 3
    println(stack)  // Output: [1, 2]
}

Using the Built-in Stack Class

Kotlin can also use the built-in Stack class from Java. Here's an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Stack

fun main() {
    val stack = Stack<Int>()

    // Push operation
    stack.push(1)
    stack.push(2)
    stack.push(3)
    println(stack)  // Output: [1, 2, 3]

    // Pop operation
    println(stack.pop())  // Output: 3
    println(stack)  // Output: [1, 2]
}

Custom Implementations

You can create a custom stack class to have more control over the stack's behavior.

Custom Stack Class

Here's how you can create a custom stack class with an internal Kotlin list:

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
class CustomStack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    fun isEmpty(): Boolean {
        return elements.isEmpty()
    }

    fun size(): Int {
        return elements.size
    }
}

fun main() {
    val stack = CustomStack<Int>()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    println(stack.peek())  // Output: 3
    println(stack.pop())   // Output: 3
    println(stack.size())  // Output: 2
}

Using Extension Methods

You can also add stack-like functionality to an existing Kotlin collection using extension methods:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun <T> MutableList<T>.push(item: T) {
    this.add(item)
}

fun <T> MutableList<T>.pop(): T? {
    if (this.isNotEmpty()) {
        return this.removeAt(this.size - 1)
    }
    return null
}

fun main() {
    val stack = mutableListOf<Int>()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    println(stack)  // Output: [1, 2, 3]

    println(stack.pop())  // Output: 3
    println(stack)  // Output: [1, 2]
}

Using Typealias

To make your code more readable, you can use a typealias:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typealias Stack<T> = MutableList<T>

fun <T> Stack<T>.push(item: T) {
    this.add(item)
}

fun <T> Stack<T>.pop(): T? {
    if (this.isNotEmpty()) {
        return this.removeAt(this.size - 1)
    }
    return null
}

fun main() {
    val stack: Stack<Int> = mutableListOf()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    println(stack)  // Output: [1, 2, 3]

    println(stack.pop())  // Output: 3
    println(stack)  // Output: [1, 2]
}

By following these approaches, you can implement a stack in Kotlin that suits your specific needs. You can efficiently manage your stack operations by using a MutableList, Java's Stack class, a custom implementation, or extension methods.

Stack Operations and Performance

Understanding the operations and performance of a stack is crucial for implementing efficient algorithms and data structures. This section delves into the time and space complexity of stack operations and explores essential stack operations in detail.

Time and Space Complexity

Push Operation

The push operation adds an element to the top of the stack. In a stack, the top element is always the most recently added element.

Time Complexity: O(1) - This operation is constant time as it only involves adding an element to the end of a list.
Space Complexity: O(1) - Each push operation uses a constant amount of space.

1
2
3
4
5
6
7
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }
}

Pop Operation

The pop operation removes and returns the top element from the stack. After a pop operation, the next element becomes the new top of the stack.

Time Complexity: O(1) - This operation is constant time since it only involves removing the last element from the list.
Space Complexity: O(1) - Each pop operation uses a constant amount of space.

1
2
3
4
5
6
7
8
9
10
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }
}

Essential Operations

Peek Operation

The peek operation allows you to look at the top element of the stack without removing it. This is useful when you need to access the top element but do not want to modify the stack.

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
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    fun isEmpty(): Boolean {
        return elements.isEmpty()
    }

    fun size(): Int {
        return elements.size
    }
}

Count Property

The count property returns the number of elements in the stack. It is useful for implementing the isEmpty property, which checks if the stack is empty.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    val count: Int
        get() = elements.size

    val isEmpty: Boolean
        get() = elements.isEmpty()
}

Pop Method

The pop method can be implemented to return the top element instead of removing it, providing more flexibility in how the stack is used.

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
class Stack<T> {
    private val elements: MutableList<T> = mutableListOf()

    fun push(item: T) {
        elements.add(item)
    }

    fun pop(): T? {
        if (elements.isEmpty()) {
            return null
        }
        return elements.removeAt(elements.size - 1)
    }

    fun popWithoutRemove(): T? {
        return elements.lastOrNull()
    }

    fun peek(): T? {
        return elements.lastOrNull()
    }

    val count: Int
        get() = elements.size

    val isEmpty: Boolean
        get() = elements.isEmpty()
}

Real-World Applications and Challenges

Stacks are incredibly versatile and can be applied to solve numerous real-world problems. This section explores two common challenges: reversing a linked list and validating parentheses, both of which demonstrate the utility of stacks.

Reverse a LinkedList

Reversing a linked list is a common problem that can be efficiently solved using a stack. The idea is to push all the nodes of the linked list onto a stack and then pop them off, resulting in a reversed order.

Problem Description

Given a linked list, print the nodes in reverse order without using recursion.

Implementation

Here’s how you can implement this in Kotlin:

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
class ListNode(val value: Int) {
    var next: ListNode? = null
}

fun reverseLinkedList(head: ListNode?) {
    val stack = mutableListOf<ListNode>()
    var currentNode = head

    // Push all nodes onto the stack
    while (currentNode != null) {
        stack.add(currentNode)
        currentNode = currentNode.next
    }

    // Pop all nodes and print them
    while (stack.isNotEmpty()) {
        val node = stack.removeAt(stack.size - 1)
        println(node.value)
    }
}

fun main() {
    // Create a sample linked list: 1 -> 2 -> 3 -> null
    val head = ListNode(1).apply {
        next = ListNode(2).apply {
            next = ListNode(3)
        }
    }

    // Print the linked list in reverse order
    reverseLinkedList(head)
}

Explanation

Push Nodes onto the Stack: Traverse the linked list and push each node onto the stack.
Pop Nodes from the Stack: Pop nodes from the stack and print their values. This prints the nodes in reverse order.

The Parentheses Validation Problem

The parentheses validation problem is another classic example where a stack can be used to ensure balanced parentheses in a string.

Problem Description

Check for balanced parentheses in a given string and return true if the parentheses are balanced.

Implementation

Here's how you can implement parentheses validation in Kotlin:

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
fun isValidParentheses(s: String): Boolean {
    val stack = mutableListOf<Char>()

    for (char in s) {
        when (char) {
            '(', '{', '[' -> stack.add(char)
            ')', '}', ']' -> {
                if (stack.isEmpty()) return false
                val top = stack.removeAt(stack.size - 1)
                if (!isMatchingPair(top, char)) return false
            }
        }
    }

    return stack.isEmpty()
}

fun isMatchingPair(open: Char, close: Char): Boolean {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']')
}

fun main() {
    val input = "{[()]}"
    println(isValidParentheses(input))  // Output: true
}

Explanation

Push Open Parentheses: Push each open parenthesis ((, {, [) onto the stack.
Match Close Parentheses: For each closing parenthesis (), }, ]), check if the stack is not empty and the top of the stack matches the corresponding opening parenthesis. If not, return false.
Final Check: After processing all characters, ensure the stack is empty to confirm all parentheses were matched.

Advanced Topics in Data Structure

In this section, we will explore advanced stack implementations using ArrayDeque and LinkedList in Kotlin. These classes offer flexibility and performance benefits, making them suitable for various scenarios where a stack or queue is required.

ArrayDeque and LinkedList Implementations

ArrayDeque Implementation

Kotlin 1.3.70 introduced the kotlin.collections.ArrayDeque class, which can function as both a queue and a stack. It is similar to Java's java.util.Deque.

The ArrayDeque class provides efficient operations for stack-like behavior. Here's how you can use ArrayDeque to implement a stack in Kotlin:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fun main() {
    val stack = ArrayDeque<Int>()

    // Push operation
    stack.addLast(1)
    stack.addLast(2)
    stack.addLast(3)
    println(stack)  // Output: [1, 2, 3]

    // Pop operation
    println(stack.removeLast())  // Output: 3
    println(stack)  // Output: [1, 2]

    // Peek operation
    println(stack.last())  // Output: 2

    // Check if the stack is empty
    println(stack.isEmpty())  // Output: false
}

LinkedList Implementation

The LinkedList class can also be used to implement a stack in Kotlin. This class is part of the Java standard library and provides a doubly linked list implementation.

Here's how you can implement a stack using the LinkedList class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.LinkedList

fun main() {
    val stack = LinkedList<Int>()

    // Push operation
    stack.push(1)
    stack.push(2)
    stack.push(3)
    println(stack)  // Output: [3, 2, 1]

    // Pop operation
    println(stack.pop())  // Output: 3
    println(stack)  // Output: [2, 1]

    // Peek operation
    println(stack.peek())  // Output: 2

    // Check if the stack is empty
    println(stack.isEmpty())  // Output: false
}

Comparison of ArrayDeque and LinkedList

ArrayDeque:

◦ Performance: Generally faster for stack operations due to contiguous memory allocation.

◦ Usage: Suitable for scenarios requiring both stack and queue operations.

◦ Space Complexity: May use more space due to dynamic resizing.
LinkedList:

◦ Performance: Slightly slower for random access but efficient for insertions and deletions.

◦ Usage: Ideal for scenarios where frequent insertions and deletions occur.

◦ Space Complexity: Uses more memory due to the overhead of storing node references.

Both ArrayDeque and LinkedList provide robust options for implementing stacks in Kotlin. The choice between them depends on your specific needs:

Use ArrayDeque for performance-sensitive applications that require both stack and queue operations.
Use LinkedList for applications with frequent insertions and deletions.

Conclusion

In conclusion, stacks are a vital linear data structure following the Last-In-First-Out (LIFO) principle, essential for various programming and computer science applications. Implementing stacks in Kotlin can be done using built-in classes like Stack, ArrayDeque, or custom implementations using MutableList.

By choosing the right implementation and adhering to best practices, you can efficiently solve problems like expression parsing, postfix notation evaluation, and recursive algorithm implementation.

Mastering stack operations in Kotlin will significantly enhance your ability to tackle complex programming challenges but building impactful apps requires more experience.

Kotlin Stack: Implementing and Using Stacks Effectively

Mihir Patel

Got a Figma? Or just a shower 🚿 thought?

About the Author

Mihir Patel

Read More

Kotlin Stack: Implementing and Using Stacks Effectively

Mihir Patel

Got a Figma? Or just a shower 🚿 thought?

About the Author

Mihir Patel

Read More

What is a Stack Data Structure?

Key Characteristics of a Stack

Operations on a Stack

Push Operation

Pop Operation

Peek Operation

Implementing a Stack in Kotlin

Using a MutableList

Using the Built-in Stack Class

Custom Implementations

Custom Stack Class

Using Extension Methods

Using Typealias

Stack Operations and Performance

Time and Space Complexity

Push Operation

Pop Operation

Essential Operations

Peek Operation

Count Property

Pop Method

Further Reading

Real-World Applications and Challenges

Reverse a LinkedList

Problem Description

Implementation

Explanation

The Parentheses Validation Problem

Problem Description

Implementation

Explanation

Advanced Topics in Data Structure

ArrayDeque and LinkedList Implementations

ArrayDeque Implementation

LinkedList Implementation

Comparison of ArrayDeque and LinkedList

Conclusion