interface Queue<T> {
    fun isEmpty(): Boolean
    fun enqueue(item: T)
    fun dequeue(): T
}

class ListQueue<T> : Queue<T> {

    // The underlying data type we'll use is a mutable list
    private val items: MutableList<T> = mutableListOf()

    // We need to add to the rear and remove from the front,
    // so we'll track both front and rear indices
    private var front: Int = -1 // -1 means empty
    private var rear: Int = -1 // -1 means empty

    override fun isEmpty(): Boolean {
        return front == -1 // could just as easily use the rear
    }

    override fun enqueue(item: T) {
        // If the queue is empty, we have a valid front index now
        if (isEmpty()) {
            front = 0
        }

        // Increment the rear index, then add the item
        // at the new rear position
        rear++
        if (items.count() > rear) { // Question: Why do this check?
            items[rear] = item
        } else {
            items.add(item)
        }
    }

    override fun toString(): String {
        return items.subList(front, rear+1).toString()
    }
}

fun main() {
    val q = ListQueue<Int>()

    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)

    println(q)

    q.dequeue()
    q.enqueue(6)
    q.dequeue()

    println(q)
}