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 enqueue on the end and dequeue from the front,
    // so we'll track both head and tail indices
    private var head: Int = -1 // -1 means empty
    private var tail: Int = -1 // -1 means empty

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

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

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

    override fun toString(): String {
        return items.subList(head, tail+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)
}