Advanced Queue Manipulations in Kotlin

Welcome back! As we continue our course on Advanced Data Structures - Stacks and Queues in Kotlin, we'll explore how to leverage queues to solve challenges common in technical interviews. Queues, with their orderly structure, are perfect for modeling sequential processes and managing streaming data effectively. In this lesson, we'll delve into two problems that highlight complex queue manipulations using Kotlin. Let's get started and unpack these intriguing challenges with examples that ensure a thorough understanding of the concepts at play.

Let's begin with queue interleaving. Imagine orchestrating a dance sequence where dancers from two groups must perform in an alternating pattern. Similarly, our task is to rearrange a list of elements such that, starting with an order like $a_1$, $a_2$, ..., $a_{n/2}$, $b_1$, $b_2$, ..., $b_{n/2}$, we end up with $a_1$, $b_1$, $a_2$, $b_2$, ..., $a_{n/2}$, $b_{n/2}$. This reflects real-life situations, like merging traffic from two lanes into one.

We'll employ two auxiliary queues, akin to two sub-lines in a dance sequence or lanes on a road, to maintain the sections of our original queue separately. We can interleave them efficiently without needing extra arrays by dequeuing elements orderly.

First, consider a list representing dancers (or elements). Divide this list into two groups, one for the first half (firstHalf) and the other for the second half (secondHalf). We can then alternate elements from each group to form a new interleaved list.

Here's the implementation:

val firstHalf = ArrayDeque<Int>()
val secondHalf = ArrayDeque<Int>()
val queue = ArrayDeque(listOf(1, 2, 3, 4, 5, 6)) // Example input

val n = queue.size
for (i in 0 until n / 2) {
    firstHalf.add(queue.removeFirst())
}

for (i in n / 2 until n) {
    secondHalf.add(queue.removeFirst())
}

while (firstHalf.isNotEmpty() || secondHalf.isNotEmpty()) {
    if (firstHalf.isNotEmpty()) {
        queue.add(firstHalf.removeFirst())
    }
    if (secondHalf.isNotEmpty()) {
        queue.add(secondHalf.removeFirst())
    }
}

println(queue) // Output would be the interleaved list

Visualize this as a dance coordinator calling out each group in turn, creating a new sequence. This approach elegantly uses ArrayDeque to solve the problem, efficiently managing memory.