In this lab, you will implement a recursive queue.

Submission

In general, any labs we do will not have required submissions. However, you are encouraged to complete them for your own practice and understanding.

Goals

The purpose of this lab is to get practice working with data structures that are inherently recursive.

Getting started

For this lab, you’ll start with a simple skeleton of a recursive queue, given below. Copy it to a folder on your computer or COURSES drive on the lab computer.

class RecursiveQueue<T> {

    // The state of the recursive queue is based on the front, rear,
    // and inside portions.
    
    // Completely empty: front and rear are both null.
    // One element: in front; rear is null.
    // Two elements: in front and rear, inside is null.
    // More than two: in front and rear, and the rest inside.

    var front: T? = null
    var rear: T? = null
    var inside: RecursiveQueue<T>? = null

    // Add the given value to the queue.
    fun enqueue(value: T) {
        // TODO
    }

    // Print out the state of the queue, in order from front to rear.
    override fun toString(): String {
        // TODO
        return ""
    }
}

fun main() {
    // Create a new RecursiveQueue to hold integers
    val q = RecursiveQueue<Int>()

    // Add 10 to the end of the queue, and inspect the state
    q.enqueue(10)
    println("Front: ${q.front}")
    println("Inside is null? ${q.inside == null}")
    println("Rear: ${q.rear}")
    
    // TODO: add more checks

}

Part A: enqueue

First, implement the enqueue function. If you get stuck, try identifying the base case(s) and how to implement it/them. Then, think about how it behaves when the list has many elements.

As you work, fill in main to call enqueue and inspect the state of the queue. The beginning of this is done for you.

Part B: toString

Now, implement toString, which should build a string representing the contents of the queue. Add some code to main to test your function!

Want more to do?

If you finish early, or want to play later, try out implementing dequeue to remove an element from the front of the queue. Make sure to test your code as you go!