Ôn tập: Hàng đợi ưu tiên

Thuộc phần Lập trình hướng đối tượng trong hành trình Kotlin của Coddy. Bài học 41 trên 57.

Thử thách

Trung bình

Hãy xây dựng một hàng đợi ưu tiên hoạt động với mọi kiểu có mức ưu tiên. Prioritized (có priority) và các lớp dữ liệu Job và Ticket đã được cung cấp.

TaskQueue<T : Prioritized> có push(item), pop() và peek(), dùng để xóa hoặc trả về phần tử có mức ưu tiên cao nhất (phần tử được đưa vào trước nếu có mức ưu tiên bằng nhau) hoặc null, size, items() (ảnh chụp chỉ đọc theo thứ tự lấy ra) và drain(n), lấy ra tối đa n phần tử rồi trả về chúng dưới dạng List<T>.
Hàm tổng quát countUrgent(queue, min) nhận một hàng đợi chứa kiểu bất kỳ có mức ưu tiên và trả về số phần tử có mức ưu tiên ít nhất bằng mức đó.

Code được cung cấp đọc các lệnh job build 3, ticket 17 5 ada, pop jobs, peek tickets, drain 2 (tickets) hoặc sizes, in từng phản hồi và cuối cùng in urgent: cùng với số công việc và vé khẩn cấp vẫn còn trong hàng đợi.

Code của bạn nằm trong TaskQueue.kt, Prioritized.kt, Job.kt và Ticket.kt. Main.kt chứa code đầu vào/đầu ra được cung cấp và bạn không thể chỉnh sửa tệp này.

Tự làm thử

fun main() {
    // Đoạn code đầu vào/đầu ra đã có sẵn: giữ nguyên
    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)}")
}