Data Structures in Kotlin: Stack & Queue — [PartV]

Hi everyone, in this article we’re going to talk a little bit about how we can use the Stack and Queue data structures in Kotlin. So without further ado, let’s get started!

Stack — LIFO

Imagine that you want to organize the items in your refrigerator. As you insert one item after another, the first one gets pushed to the back. When you need to retrieve the first item you put in, you’ll have to take out all the others to get to it. This can be a good idea if you insert the items in descending order of expiration date. That’s the idea behind a Stack.

A stack is a data structure that follows the “last-in, first-out” (LIFO) principle. It is similar to a stack of physical objects, where you can add a new object to the top and remove the topmost object when needed.

In a Stack, the fundamental operations are:

• Push: Adds an element to the top of the stack.
• Pop: Removes the top element from the stack.
• Peek/Top: Returns the top element of the stack without removing it.

Characteristics

• Order: The order of insertion into the stack is not important unless intentional reverse order is desired, , such as in the refrigerator example.
• Limited Capacity: Stacks have a maximum capacity. If exceeded, it results in a stack overflow. It is essential to monitor the stack’s size to prevent this issue.
• Arrays: Stacks can be implemented using arrays, where elements are stored in consecutive memory locations. The top of the stack is represented by an index, and pushing or popping elements involves updating this index accordingly.
• Linked Lists: Stacks can also be implemented using linked lists, where each element is stored in a node containing both the value and a reference to the next node. The top of the stack is represented by the head of the linked list, and pushing or popping elements involves adding or removing nodes at the head.

Performance considerations:

• 🚀 Adding and Removing Elements: Stacks offer efficient performance by imposing constraints on adding and removing elements. Elements are always inserted and removed from the top, resulting in constant time complexity (O(1)) for both push and pop operations.
• 🔻 Limited Access and Search: Stacks do not allow access to random items within the stack since they follow the LIFO (Last-In-First-Out) principle. Therefore, operations such as searching or obtaining a specific item are inefficient.

Queue — FIFO

Imagine a ticket queue, where customers are served in the order they arrived. The first person to join the queue will be the first to receive service. This concept forms the foundation of the Queue data structure.

The queue data structure is an ordered collection of elements where the first element inserted is the first to be removed, following the First-In-First-Out (FIFO) principle.

• Front: It represents the element that has been in the queue for the longest time and will be the next one to be removed.
• Rear: Also known as the “tail”, it represents the most recent element added to the queue.

Let’s explore the operations that can be performed using a Queue:

• Enqueue(): The enqueue operation adds an element to the rear of the queue. It represents inserting a new element into the queue, making it the newest element. If the queue is empty, the newly added element also becomes the front element.

• Dequeue(): The dequeue operation removes the element from the front of the queue. It represents removing an element from the queue in the order in which they were added. After dequeuing an element, the subsequent element in line becomes the new front.

Characteristics

• Order: The order of insertion into the queue is important and maintained.
• Array-based implementations: Using arrays, a circular buffer can be employed to efficiently implement a Queue. This allows for constant time complexity for enqueue and dequeue operations.
• Linked list-based implementations: Using a linked list, the Queue can be implemented by maintaining a reference to both the front and rear elements. This allows for efficient insertion and removal at both ends of the linked list.
• Capacity: The capacity of a queue refers to the maximum number of elements it can hold. In many implementations of queues, there is no fixed size limit, allowing the queue to dynamically grow as elements are added. This means that the capacity of the queue can expand or shrink as needed. However, some implementations may offer capacity-restricted queues, where the maximum number of elements is predefined. In such cases, it is important to manage the capacity carefully to avoid exceeding the limit and encountering issues like overflow.

Performance considerations

• 🚀 Enqueue and Dequeue Operations: The enqueue and dequeue operations in a queue typically have a time complexity of O(1), meaning they take constant time regardless of the size of the queue.
• 🚀/🔻 Capacity and Memory Usage: Queues can dynamically resize themselves to accommodate elements, providing flexibility in capacity. Implementations like ArrayDeque or LinkedList in Kotlin can efficiently handle dynamic resizing. However, it’s important to consider memory usage, especially in capacity-restricted queues, as the memory allocation and deallocation can impact performance.
• 🔻 Access and Search: Queues do not allow arbitrary access to elements due to the FIFO (First-In-First-Out) principle. As a result, accessing or searching for elements in arbitrary positions within a queue is not its primary strength.

Queues are particularly efficient when handling scenarios that require maintaining the order of arrival, such as task scheduling or message processing.

Let’s take a look at how we can implement this in Kotlin.

Usage in Kotlin

As I mentioned earlier, both stacks and queues can be implemented easily using arrays or linked lists. There is also a Java-based class for this data structure. Let’s take a look at each of these implementations.

Stack Class

In Kotlin, it is indeed possible to use the Stack class from the Java Framework's collection to create a Stack. However, it is considered legacy code, and it is not highly recommended to use it. The reason for this is that there are other more flexible data structures available now that offer better performance and additional functionalities.

If you want to learn more details about what is wrong with the Stack class, I recommend reading this article.

Queue and Deque Interfaces

In Kotlin, essentially all the classes that we can use to implement both Stack and Queue extend two interfaces: Queue and Deque. Let’s discuss each of them and gain a better understanding of this hierarchy.

• Queue: The Queue interface, from the java.util package, extends the Collection interface and provides methods for inserting, removing, and examining the element at the front of the queue. Typically, a Queue orders elements in a FIFO (First-In-First-Out) manner, but there are exceptions, such as the PriorityQueue, which we will discuss later. Classes that implement Queue interface include LinkedList, ArrayDeque, PriorityQueue, among others.
• Deque: The Deque interface represents a double-ended queue data structure, where it is possible to insert and remove elements from both the front and the back of the queue. This allows for the Last-In-First-Out (LIFO) operation of a stack and the First-In-First-Out (FIFO) operation of a traditional queue. The Deque interface extends the Queue interface and, therefore, inherits all the methods from the Queue interface, while also providing additional methods for insertion and removal at both ends of the queue. Classes that extend Deque include LinkedList, ArrayDeque, and ConcurrentLinkedDeque.

Now that we understand the purpose of these two interfaces, let’s discuss the most common classes that implement them and that we can use to create both queues and stacks in Kotlin.

ArrayDeque

The ArrayDeque class, part of java.util, extends the Deque interface, making it a versatile data structure with support for operations on both ends. Let’s take a look at some of its characteristics.

Characteristics

• No Capacity Restrictions: ArrayDeque does not have any capacity restrictions and can dynamically resize itself as needed. This flexibility allows it to efficiently handle varying amounts of data without the need for manual resizing or reallocation.
• Not Thread-Safe: It’s important to note that ArrayDeque is not thread-safe. It is not designed to handle concurrent access by multiple threads without external synchronization. If multiple threads access the data simultaneously, it can result in inconsistent behavior. Therefore, proper synchronization mechanisms should be implemented when using ArrayDeque in concurrent environments.
• Non-Nullable Elements: ArrayDeque does not allow null values to be stored. This helps ensure data integrity and avoids potential issues related to null references.
• Stack usage: When the intention is to use the stack structure, ArrayDeque is a superior choice compared to the Stack class.
• Queue usage: When the intention is to use the queue structure, ArrayDeque outperforms LinkedList in terms of speed.

Performance considerations

• 🚀 Efficient Majority of Operations: ArrayDeque provides efficient performance for the majority of its operations, running in constant time complexity (O(1)). This means that most operations execute quickly and consistently, regardless of the size of the ArrayDeque. These operations include: insertion/removal at the front and back, access to the first/last element, size determination, and empty check.
• 🔻 Linear Time Complexity Exceptions: Certain operations in ArrayDeque, like removing specific objects, removing first or last occurrences, checking for element existence, iterating over elements, and bulk operations, have linear time complexity. These operations can have performance implications, particularly with large ArrayDeque sizes or frequent use.
• 🔻 Fail-Fast Iterators and Concurrent Modification: The iterators returned by the iterator() method of these classes are designed to be fail-fast. It means that if the deque is modified in any way (except through the iterator’s own remove() method) after the iterator is created, the iterator will throw a ConcurrentModificationException. This mechanism ensures that concurrent modifications to the deque are detected promptly.

You may notice that there is an ArrayDeque in the Java collection and another in the Kotlin collection. Both serve a similar purpose, but in Kotlin, this class extends the MutableList interface and provides efficient get/set operations by index. The choice between them will depend more on whether you are programming in Java or Kotlin.

Let’s see some examples of implementations in Kotlin.

1- Using ArrayDeque (java.utils) as a Stack:

val stack = java.util.ArrayDeque<Int>()

// Push elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)

// Accessing the top element
val topElement = stack.peek()
println(topElement) // Output: 30

// Popping elements from the stack
val poppedElement = stack.pop()
println(poppedElement) // Output: 30

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

// Print the remaining elements in the stack
println(stack) // Output: [20, 10]

2- Using ArrayDeque (kotlin) as a Stack:

// Create an empty ArrayDeque
val stack = ArrayDeque<Int>()

// Push elements onto the stack
stack.addFirst(10)
stack.addFirst(20)
stack.addFirst(30)

// Accessing the top element
val topElement = stack.first()
println(topElement) // Output: 30

// Popping elements from the stack
val poppedElement = stack.removeFirst()
println(poppedElement) // Output: 30

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

// Print the remaining elements in the stack
println(stack) // Output: [20, 10]

3. Using ArrayDeque as a Queue:

// Create an empty ArrayDeque
val queue = ArrayDeque<Int>()

// Enqueue elements into the queue
queue.addLast(10)
queue.addLast(20)
queue.addLast(30)

// Accessing the front element
val frontElement = queue.first()
println(frontElement) // Output: 10

// Dequeue elements from the queue
val dequeuedElement = queue.removeFirst()
println(dequeuedElement) // Output: 10

// Check if the queue is empty
val isEmpty = queue.isEmpty()
println(isEmpty) // Output: false

// Print the remaining elements in the queue
println(queue) // Output: [20, 30]

LinkedList

LinkedList is another option for implementing both a queue and a stack in Kotlin.

For a stack, LinkedList can simulate the Last-In-First-Out (LIFO) behavior by adding and removing elements at the head of the list. When we add a new element, it becomes the new “top” of the stack, and when we remove an element, we take it from the “top” of the stack.

For a queue, LinkedList can represent the First-In-First-Out (FIFO) behavior by utilizing its implementation of the Deque interface.

Let’s see some practical examples in Kotlin:

1- Using LinkedList as a Stack

val stack = LinkedList<Int>()

// Push elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)

// Accessing the top element
val topElement = stack.peek()
println(topElement) // Output: 30

// Popping elements from the stack
val poppedElement = stack.pop()
println(poppedElement) // Output: 30

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

// Print the remaining elements in the stack
println(stack) // Output: [20, 10]

2- Using LinkedList as a Queue

// Create an empty LinkedList
val queue = LinkedList<Int>()

// Enqueue elements into the queue
queue.addLast(10)
queue.addLast(20)
queue.addLast(30)

// Accessing the front element
val frontElement = queue.peek()
println(frontElement) // Output: 10

// Dequeue elements from the queue
val dequeuedElement = queue.removeFirst()
println(dequeuedElement) // Output: 10

// Check if the queue is empty
val isEmpty = queue.isEmpty()
println(isEmpty) // Output: false

// Print the remaining elements in the queue
println(queue) // Output: [20, 30]

PriorityQueue

A PriorityQueue class in Kotlin is a special type of queue where elements are ordered based on their priority. It ensures that the element with the highest priority is always at the front of the queue and will be the first one to be removed. In this way, PriorityQueue helps to efficiently manage elements with different levels of importance or urgency.

Characteristics

• Ordering: Elements in the PriorityQueue are ordered based on their natural ordering or a custom-defined ordering. This means that elements with higher priority (as defined by the natural ordering or Comparator) are placed closer to the front of the queue.
• Null elements not allowed: PriorityQueue does not permit null elements. Attempting to add a null element will result in an exception.
• Unbounded size: The PriorityQueue is unbounded, meaning it can grow dynamically as elements are added. It can hold any number of elements, limited only by the available memory.
• Retrieval operations: PriorityQueues provide methods to retrieve elements at the front of the queue without removing them. These methods include peek, element, and size.
• Not Thread-Safe: It’s important to note that PriorityQueue is not synchronized, meaning it is not designed to handle concurrent access from multiple threads. To ensure thread safety, it’s recommended to use a thread-safe class for concurrent access.
• Type Constraint: PriorityQueue requires elements to be comparable. This means that non-comparable objects cannot be inserted directly into a PriorityQueue. Attempting to do so may result in a ClassCastException.
• Arbitrary Tie-Breaking: If multiple elements have the same priority, the head of the queue (the element to be dequeued next) is chosen arbitrarily. This means that the order in which elements with the same priority are dequeued is not guaranteed.
• Unordered Traversal: The Iterator and Spliterator provided by PriorityQueue do not guarantee a specific order when traversing the elements. If ordered traversal is required, an alternative approach, such as using Arrays.sort(pq.toArray()), should be considered.

Performance considerations

• 🚀 Efficient Enqueuing and Dequeuing: Enqueuing and dequeuing operations have a time complexity of O(log(n)), ensuring efficient performance even for large queues.
• 🚀 Constant Time Retrieval: The retrieval methods (peek, element, and size) have a constant time complexity. This means that accessing the element at the head of the queue, checking the size, or retrieving the first element can be done in constant time, regardless of the size of the priority queue.
• 🔻 Linear Time Complexity for Remove and Contains: The remove(Object) and contains(Object) methods have a linear time complexity. This means that removing or checking for the presence of a specific object in the priority queue may take longer for larger queues.

Let’s see an example:

class Task(val name: String, val priority: Int)

// Create a PriorityQueue of tasks with custom priority ordering
val taskQueue = PriorityQueue<Task> { task1, task2 ->
  task1.priority - task2.priority
}

// Add tasks to the priority queue
taskQueue.offer(Task("Task with priority 2", 2))
taskQueue.offer(Task("Task with priority 3", 3))
taskQueue.offer(Task("Task with priority 1", 1))

// Process tasks based on priority
//The poll() method retrieves and removes the highest-priority element from the priority queue.
while (!taskQueue.isEmpty()) {
  val task = taskQueue.poll()
  println("Task: ${task?.name}")
}

//Output:
//Task: Task with priority 1
//Task: Task with priority 2
//Task: Task with priority 3

In this example, we create a PriorityQueue of Task objects, where each task has a name and a priority. We define a custom ordering for the tasks based on their priority using a lambda expression.

The lambda expression { task1, task2 -> task1.priority - task2.priority } specifies how the tasks should be ordered. It takes two Task objects (task1 and task2) and compares their priorities (task1.priority and task2.priority). By subtracting task2.priority from task1.priority, the lambda expression determines the ordering based on the difference in priorities. If the result is negative, it means task1 has higher priority. If the result is positive, it means task2 has higher priority. If the result is zero, it means both tasks have the same priority.

A real-world example where PriorityQueue is beneficial is in task scheduling or job prioritization systems. It allows tasks to be processed in order of their priority, ensuring that high-priority tasks are completed first. This is particularly useful in scenarios where timely execution of critical tasks is crucial, optimizing system performance and ensuring important tasks receive appropriate attention.

Custom implementations

In addition to LinkedList, ArrayDeque, and PriorityQueue, you can also implement the Stack and Queue data structures in Kotlin using other approaches. Two common options are using Lists and creating custom classes.

1- Using Lists

• To simulate a Stack, you can use the List interface and its methods like add() to push elements onto the stack, and removeAt() to pop elements from the stack. Example:

    val stack = mutableListOf<Int>()
    stack.add(1) // Push element onto the stack
    stack.add(2) // Push element onto the stack
    stack.add(3) // Push element onto the stack

    val topElement = stack.removeAt(stack.size - 1) // Pop element from the stack
    println(topElement) //Output: 3

• To simulate a Queue, you can also use the List interface and its methods like add() to enqueue elements, and removeAt() or removeFirst() to dequeue elements. Example:

    val queue = mutableListOf<String>()

    queue.add("A") // Enqueue element
    queue.add("B") // Enqueue element
    queue.add("C") // Enqueue element

    val frontElement = queue.removeAt(0) // Dequeue element
    println(frontElement) //Output: A

2- Creating custom classes

Another option is to create your own custom classes that represent the Stack and Queue data structures. You can define the specific behavior and operations according to your needs. Example:

class Stack<T> {
    private val elements = mutableListOf<T>()

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

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

val stack = Stack<Int>()
stack.push(1)
stack.push(2)
stack.push(3)

val topElement = stack.pop()
println(topElement) //Output: 3

Similarly, you can create a custom class for Queue with enqueue and dequeue operations implemented according to the desired behavior.

These approaches provide flexibility to implement the Stack and Queue data structures in Kotlin based on your specific requirements.

And that’s it! I hope this article has helped you in some way.

References

Stack | Android Developers

[Really good article about data strcutures and respective performance] https://medium.com/coderbyte/data-structures-and-their-impact-on-performance-86ab8c8cb006

What's Wrong With Stack in Java and Kotlin?

ArrayDeque - Kotlin Programming Language

Queue | Android Developers

PriorityQueue | Android Developers

Deque | Android Developers

Stack & Queue with (Singly) Linked List