Kotlin Data Structures: Understanding Stacks and Queues

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

ArrayDeque in Kotlin

ArrayDeque (Double-Ended Queue) is a versatile data structure that combines the features of both Stack and Queue. It provides efficient methods for adding and removing elements from both ends of the collection: Stack Operations: addLast() : Adds an element to the end (top of stack) removeLast() : Removes and returns the last element (top of stack) Queue Operations: addLast() : Adds an element to the end of queue removeFirst() : Removes and returns the first element Additional useful methods include: isEmpty() : Checks if the collection is empty size : Returns the number of elements first() : Views the first element without removing it last() : Views the last element without removing it

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. Kotlin uses ArrayList to create a stack, with add() used for push, and removeAt(size - 1) used for pop . A Stack adheres to the "Last In, First Out" or LIFO principle. Let's explore this using a pile of plates: Kotlin class StackOfPlates {private val stack = ArrayDeque<String>() // Inserts a plate at the top of the stack fun addPlate(plate: String) {stack.addLast(plate) // Using addLast() to push onto stack} // Removes the top plate from the stack fun removePlate(): String {if (stack.isEmpty()) {return "No plates left to remove!"} return stack.removeLast() // Using removeLast() to pop from stack}} // Create a stack of plates fun main() {val plates = StackOfPlates() plates.addPlate("Plate") // Pushing a plate plates.addPlate("Another Plate") // Pushing another plate // Let's remove a plate; it should be the last one we added. println("Removed: ${plates.removePlate()}") // Outputs: Removed: Another Plate} In this implementation: We use ArrayDeque to store our plates addPlate() uses addLast() to push a plate onto the top of the stack removePlate() uses removeLast() to pop the top plate off the stack We check for empty stack to prevent errors The main function demonstrates how the last plate added is the first one removed (LIFO principle)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. In Kotlin, ArrayDeque provides efficient implementation of queues with addLast() for enqueue and removeFirst() for dequeue operations.

Let's examine this through a queue of people:

Kotlin

class QueueOfPeople {
    private val queue = ArrayDeque<String>()

    // Add a person to the end of the queue
    fun enqueuePerson(person: String) {
        queue.addLast(person)  // Using addLast() to add to end of queue
    }

    // Remove the first person from the queue (who has been waiting the longest)
    fun dequeuePerson(): String {
        if (queue.isEmpty()) {
            return "No people left to dequeue!"
        }
        return queue.removeFirst()  // Using removeFirst() to remove from front of queue
    }
}

// Create a queue of people
fun main() {
    val people = QueueOfPeople()
    people.enqueuePerson("Person 1")  // Person 1 enters the queue
    people.enqueuePerson("Person 2")  // Person 2 arrives after Person 1
    // Who's next in line? It must be Person 1!
    println("Removed: ${people.dequeuePerson()}")  // Outputs: Removed: Person 1
}

class QueueOfPeople {
    private val queue = ArrayDeque<String>()

    // Add a person to the end of the queue
    fun enqueuePerson(person: String) {
        queue.addLast(person)  // Using addLast() to add to end of queue
    }

    // Remove the first person from the queue (who has been waiting the longest)
    fun dequeuePerson(): String {
        if (queue.isEmpty()) {
            return "No people left to dequeue!"
        }
        return queue.removeFirst()  // Using removeFirst() to remove from front of queue
    }
}

// Create a queue of people
fun main() {
    val people = QueueOfPeople()
    people.enqueuePerson("Person 1")  // Person 1 enters the queue
    people.enqueuePerson("Person 2")  // Person 2 arrives after Person 1
    // Who's next in line? It must be Person 1!
    println("Removed: ${people.dequeuePerson()}")  // Outputs: Removed: Person 1
}

In this implementation:

We use ArrayDeque to store our queue of people
enqueuePerson() uses addLast() to add a person to the end of the queue
dequeuePerson() uses removeFirst() to remove the person at the front of the queue
We check for empty queue to prevent errors
The main function demonstrates how the first person added (Person 1) is the first one removed (FIFO principle)

The ArrayDeque implementation provides efficient O(1) operations for both adding and removing elements, making it an excellent choice for queue operations.

Mastering Stack and Queue Operations With a Class

Let's depict the two structures in a text editor that features an Undo mechanism (a Stack) and a Print Queue.