Lesson 5
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
1class StackOfPlates {
2    private val stack = ArrayDeque<String>()
3
4    // Inserts a plate at the top of the stack 
5    fun addPlate(plate: String) {
6        stack.addLast(plate)  // Using addLast() to push onto stack
7    }
8
9    // Removes the top plate from the stack
10    fun removePlate(): String {
11        if (stack.isEmpty()) {
12            return "No plates left to remove!"
13        }
14        return stack.removeLast()  // Using removeLast() to pop from stack
15    }
16}
17
18// Create a stack of plates
19fun main() {
20    val plates = StackOfPlates()
21    plates.addPlate("Plate")  // Pushing a plate
22    plates.addPlate("Another Plate")  // Pushing another plate
23    // Let's remove a plate; it should be the last one we added.
24    println("Removed: ${plates.removePlate()}")  // Outputs: Removed: Another Plate
25}

In this implementation:

  1. We use ArrayDeque to store our plates
  2. addPlate() uses addLast() to push a plate onto the top of the stack
  3. removePlate() uses removeLast() to pop the top plate off the stack
  4. We check for empty stack to prevent errors
  5. The main function demonstrates how the last plate added is the first one removed (LIFO principle)
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
1class QueueOfPeople {
2    private val queue = ArrayDeque<String>()
3
4    // Add a person to the end of the queue
5    fun enqueuePerson(person: String) {
6        queue.addLast(person)  // Using addLast() to add to end of queue
7    }
8
9    // Remove the first person from the queue (who has been waiting the longest)
10    fun dequeuePerson(): String {
11        if (queue.isEmpty()) {
12            return "No people left to dequeue!"
13        }
14        return queue.removeFirst()  // Using removeFirst() to remove from front of queue
15    }
16}
17
18// Create a queue of people
19fun main() {
20    val people = QueueOfPeople()
21    people.enqueuePerson("Person 1")  // Person 1 enters the queue
22    people.enqueuePerson("Person 2")  // Person 2 arrives after Person 1
23    // Who's next in line? It must be Person 1!
24    println("Removed: ${people.dequeuePerson()}")  // Outputs: Removed: Person 1
25}

In this implementation:

  1. We use ArrayDeque to store our queue of people
  2. enqueuePerson() uses addLast() to add a person to the end of the queue
  3. dequeuePerson() uses removeFirst() to remove the person at the front of the queue
  4. We check for empty queue to prevent errors
  5. 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.

Stacks and Queues: When and Where to Use?

Stacks handle ordered data efficiently, much like your web browser's history. Queues, on the other hand, are optimal when the order of arrival is essential, such as in a store queue.

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.

Kotlin
1class TextEditor {
2    private val stack = ArrayDeque<String>()  // For undo operations
3    private val queue = ArrayDeque<String>()  // For print queue
4
5    // Make a change (e.g., edit text, insert image, change font)
6    fun makeChange(action: String) {
7        stack.addLast(action) // Add to the stack of actions
8    }
9
10    // Undo the most recent change
11    fun undoChange(): String {
12        if (stack.isEmpty()) {
13            return "No changes to undo!"
14        }
15        return stack.removeLast() // Remove the last action from the stack
16    }
17
18    // Add a document to the queue for printing
19    fun addToPrint(doc: String) {
20        queue.addLast(doc) // Add to the end of print queue
21    }
22
23    // Print the document that has been waiting the longest
24    fun printDoc(): String {
25        if (queue.isEmpty()) {
26            return "No documents in print queue!"
27        }
28        return queue.removeFirst() // Remove the first document from the queue
29    }
30}
31
32// Use our text editor!
33fun main() {
34    val editor = TextEditor()
35    editor.makeChange("Changed font size")  // Make a change
36    editor.makeChange("Inserted image")  // Make another change
37    // Let's undo a change. It should be the last change we made.
38    println("Undo: ${editor.undoChange()}")  // Undo: Inserted image
39
40    editor.addToPrint("Proposal.docx")  // Queue a document for printing
41    editor.addToPrint("Report.xlsx")  // Queue another document
42    // Let's print a document. It should be the document that has been waiting the longest.
43    println("Print: ${editor.printDoc()}")  // Print: Proposal.docx
44}

This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.

Lesson Summary

Great work! You have examined the mechanics of Stacks and Queues, both integral data structures. Remember to practice what you've learned. Happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.