Queues

• Queues and stacks
• Ring Buffer
  • Implementation notes
  • Resources

Queues and stacks

Ring Buffer

The ring buffer is a queue abstract data type that's implemented using a fixed size array. This makes it performant with additions and deletions from a runtime and memory standpoint.

The following is an implementation of it in Kotlin.

/**
 * RingBuffer uses a fixed length array to implement a queue, where,
 * - [tail] Items are added to the tail
 * - [head] Items are removed from the head
 * - [capacity] Keeps track of how many items are currently in the queue
 */
class RingBuffer<T>(val maxSize: Int = 10) {
    val array = mutableListOf<T?>().apply {
        for (index in 0 until maxSize) {
            add(null)
        }
    }

    // Head - remove from the head (read index)
    var head = 0

    // Tail - add to the tail (write index)
    var tail = 0

    // How many items are currently in the queue
    var capacity = 0

    fun clear() {
        head = 0
        tail = 0
    }

    fun enqueue(item: T): RingBuffer<T> {
        // Check if there's space before attempting to add the item
        if (capacity == maxSize) throw OverflowException(
            "Can't add $item, queue is full")

        array[tail] = item
        // Loop around to the start of the array if there's a need for it
        tail = (tail + 1) % maxSize
        capacity++

        return this
    }

    fun dequeue(): T? {
        // Check if queue is empty before attempting to remove the item
        if (capacity == 0) throw UnderflowException(
            "Queue is empty, can't dequeue()")

        val result = array[head]
        // Loop around to the start of the array if there's a need for it
        head = (head + 1) % maxSize
        capacity--

        return result
    }

    fun peek(): T? = array[head]

    /**
     * - Ordinarily, T > H ([isNormal]).
     * - However, when the queue loops over, then T < H ([isFlipped]).
     */
    fun isNormal(): Boolean {
        return tail > head
    }

    fun isFlipped(): Boolean {
        return tail < head
    }

    override fun toString(): String = StringBuilder().apply {
        this.append(contents().joinToString(", ", "{", "}").yellow())
        this.append(" [capacity=$capacity, H=$head, T=$tail]".blue())
    }.toString()

    fun contents(): MutableList<T?> {
        return mutableListOf<T?>().apply {
            var itemCount = capacity
            var readIndex = head
            while (itemCount > 0) {
                add(array[readIndex])
                readIndex = (readIndex + 1) % maxSize
                itemCount--
            }
        }
    }

}

class OverflowException(msg: String) : RuntimeException(msg)
class UnderflowException(msg: String) : RuntimeException(msg)

Implementation notes

• Since the array is re-used for insertions and deletions, it becomes important to be able to track the usage or capacity of the array (as items are added and removed). This capacity is used to determine whether the array is full or empty, and is used to iterate thru the elements of the array if needed.
• In order to cycle around the array, the head and tail indices are updated such that when they hit the "end" of the array, they "flip" over. This means that when head reaches maxSize + 1, it just goes to 0. This can be achieved easily by using the % operator. tail = (tail+1) % maxSize is the equivalent of if (tail == maxSize) tail = 0.
• In order to get all the elements out of the array (as a list) the capacity and the head (or read index) is used in order to get all the elements out as we would expect (which isn't necessarily how they are laid out in the array).

Resources

• Deep dive tutorial into ring buffers