DS Implementing a Queue in Kotlin

Section 3.12 Implementing a Queue in Kotlin

It is again appropriate to create a new class for the implementation of the abstract data type queue. As before, we will use the power and simplicity of a list to build the internal representation of the queue.

🔗

We need to decide which end of the list to use as the tail and which to use as the head. The implementation shown in Listing 3.12.1 assumes that the tail is at position 0 in the list. This allows us to use the add function on lists to add new elements to the tail of the queue. The remove operation can be used to remove the head element (the last element of the list). Recall that this also means that enqueue will be $O(n)$ and dequeue will be $O(1)\text{.}$

🔗

Listing 3.12.1. Implementation of a Queue

🔗

class ListQueue<T> : QueueADT<T> {

    /*
     * The tail of the queue is at the beginning
     * of the list; the head is the last item
     */
    private val items = mutableListOf<T>()

    /*
     * Returns true if there are no items in the queue;
     * false otherwise.
     */
    override fun isEmpty(): Boolean {
        return items.isEmpty()
    }

    /*
    * Add an item to the tail of the queue
    */
    override fun enqueue(item: T) {
        items.add(0, item)
    }

    /*
     * Remove the item at the head of the queue and return it.
     * If the queue is empty, throws an exception.
     */
    override fun dequeue(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Queue is empty.")
        }
        return items.removeLast()
    }

    /*
     * Return the item at the head of the queue, but do not remove it.
     * If the queue is empty, throws an exception.
     */
    override fun peek(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Queue is empty.")
        }
        return items[items.count() - 1]
    }

    /*
     * Returns the number of items in the queue.
     */
    override fun size(): Int {
        return items.count()
    }

    /*
     * Convert to string as an array from tail to head
     */
    override fun toString(): String {
        return items.toString()
    }
}

Listing 3.12.2 shows the ListQueue class in action as we perform the sequence of operations from Section 3.11.

🔗

Listing 3.12.2. Example Queue Operations

🔗

interface QueueADT<T> {
    // Returns true if there are no items in the queue;
    // false otherwise.
    fun isEmpty(): Boolean

// Add an item to the tail of the queue
    fun enqueue(item: T)

// Remove the item at the head of the queue and return it.
    fun dequeue(): T

// Return the item at the head of the queue, but do not remove it.
    // If the queue is empty, throws an exception.
    fun peek(): T

// Returns the number of items in the queue.
    fun size(): Int
}
        class ListQueue<T> : QueueADT<T> {

/*
     * The tail of the queue is at the beginning
     * of the list; the head is the last item
     */
    private val items = mutableListOf<T>()

/*
     * Returns true if there are no items in the queue;
     * false otherwise.
     */
    override fun isEmpty(): Boolean {
        return items.isEmpty()
    }

/*
    * Add an item to the tail of the queue
    */
    override fun enqueue(item: T) {
        items.add(0, item)
    }

/*
     * Remove the item at the head of the queue and return it.
     * If the queue is empty, throws an exception.
     */
    override fun dequeue(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Queue is empty.")
        }
        return items.removeLast()
    }

/*
     * Return the item at the head of the queue, but do not remove it.
     * If the queue is empty, throws an exception.
     */
    override fun peek(): T {
        if (isEmpty()) {
            throw NoSuchElementException("Queue is empty.")
        }
        return items[items.count() - 1]
    }

/*
     * Returns the number of items in the queue.
     */
    override fun size(): Int {
        return items.count()
    }

/*
     * Convert to string as an array from tail to head
     */
    override fun toString(): String {
        return items.toString()
    }
}
        ^^^^fun main() {
    val q = ListQueue<Int>()
    println("isEmpty returns ${q.isEmpty()}")

q.enqueue(4)
    q.enqueue(27)
    println("Queue is now: $q")

q.enqueue(1066)
    println("After another enqueue, size is ${q.size()}")
    println("isEmpty now returns ${q.isEmpty()}")

q.enqueue(4711)

println("After another enqueue, queue is $q")

var head = q.dequeue()
    println("Dequeue - head was: $head")
    head = q.dequeue()
    println("Dequeue again - head was: $head")

println("Queue is now: $q")
    println("Size is now: ${q.size()}")
}

Exercises Self Check

1.

Suppose you have the following series of queue operations.

🔗

val q = new Queue<>()
q.enqueue("hello")
q.enqueue("dog")
q.enqueue("cat")
q.dequeue()

What items are left on the queue (from head to tail)?

🔗

"hello", "dog"
Remember the first thing added to the queue is the first thing removed. FIFO
"dog", "cat"
Yes, first in first out means that "hello" is gone
"hello", "cat"
Queues and stacks are both data structures where you can only access the first and the last items.
"hello", "dog", "cat"
Ooops, maybe you missed the dequeue call at the end?

🔗

You have attempted of activities on this page.

🔗

Prev Top Next