Ringkasan, Priority Queue

Termasuk bagian Pemrograman Berorientasi Objek dalam perjalanan Kotlin di Coddy. Pelajaran 41 dari 57.

Tantangan

Sedang

Buat priority queue yang berfungsi untuk tipe apa pun yang memiliki prioritas. Prioritized (dengan priority) dan data class Job serta Ticket sudah disediakan.

TaskQueue<T : Prioritized> memiliki push(item), pop() dan peek(), yang menghapus atau mengembalikan item dengan prioritas tertinggi (item yang dimasukkan lebih dulu jika prioritasnya sama) atau null, size, items() (snapshot hanya-baca dengan urutan pop) dan drain(n), yang melakukan pop hingga n item dan mengembalikannya sebagai List<T>.
Fungsi generik countUrgent(queue, min) menerima queue dengan tipe apa pun yang memiliki prioritas dan mengembalikan jumlah item yang memiliki prioritas setidaknya sebesar nilai tersebut.

Code yang disediakan membaca perintah job build 3, ticket 17 5 ada, pop jobs, peek tickets, drain 2 (tickets) atau sizes, mencetak setiap balasan, lalu mencetak urgent: diikuti jumlah jobs dan tickets berprioritas tinggi yang masih berada dalam queue.

Tulis kodemu di TaskQueue.kt, Prioritized.kt, Job.kt dan Ticket.kt. Main.kt berisi code input/output yang disediakan dan tidak boleh diedit.

Coba sendiri

fun main() {
    // Kode input/output yang disediakan: biarkan apa adanya
    val input = generateSequence(::readLine).toList()
    val jobs = TaskQueue<Job>()
    val tickets = TaskQueue<Ticket>()
    for (cmd in input) {
        val p = cmd.split(" ")
        when (p[0]) {
            "job" -> jobs.push(Job(p[1], p[2].toInt()))
            "ticket" -> tickets.push(Ticket(p[1].toInt(), p[2].toInt(), p[3]))
            "pop" -> println("popped " + (if (p[1] == "jobs") jobs.pop() else tickets.pop()))
            "peek" -> println("next " + (if (p[1] == "jobs") jobs.peek() else tickets.peek()))
            "drain" -> println("drained " + tickets.drain(p[1].toInt()).map { it.customer })
            else -> println("jobs ${jobs.size}, tickets ${tickets.size}")
        }
    }
    println("urgent: ${countUrgent(jobs, 4) + countUrgent(tickets, 4)}")
}