数据结构：猫狗队列

算法

版本：2
作者：陈小默
声明：禁止商用，禁止转载

发布于作业部落、CSDN博客

题目

宠物猫狗的类如下：

open class Pet(val type: String)
class Dog : Pet("dog")
class Cat : Pet("cat")

要求

不能对上述类进行任何修改。使用任意语言实现使用

• add：将Cat或者Dog类的实例放入队列
• poll：弹出最先加入的实例
• pollCat：弹出最先加入的Cat实例
• pollDog：弹出最先加入的Dog实例
• isEmpty：判断是否有Dog或者Cat的实例
• isDogEmpty：判断是够有Dog实例
• isCatEmpty：判断是否有Cat实例

思路

由于不能对上述类进行修改，我们可以自定义一个新类，在这个类中存放Cat或者Dog的实例，并且添加一个顺序标记。然后在实现时使用两个队列分别存放猫实例和狗实例。

实现

/**
 *  Copyright (C) <2016>  <陈小默>
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Created by 陈小默 on 11/06.
 */
open class Pet(val type: String)
class Dog : Pet("dog")
class Cat : Pet("cat")
class CatDogQueue(val max: Int) {
    class PetEnter(val pet: Pet, val count: Int)
    private val dogQ = Queue<PetEnter>(max)
    private val catQ = Queue<PetEnter>(max)
    private var count = 0
    val isEmpty: Boolean get() = dogQ.isEmpty && catQ.isEmpty
    val isDogQueueIsEmpty: Boolean get() = dogQ.isEmpty
    val isCatQueueIsEmpty: Boolean get() = catQ.isEmpty
    fun add(pet: Pet) {
        if (pet is Dog)
            dogQ.add(PetEnter(pet, count++))
        else catQ.add(PetEnter(pet, count++))
    }
    fun poll(): Pet {
        if (isEmpty)
            throw RuntimeException("queue is empty")
        if (isDogQueueIsEmpty)
            return catQ.poll().pet
        else if (isCatQueueIsEmpty)
            return dogQ.poll().pet
        else
            return if (dogQ.peek().count < catQ.peek().count) dogQ.poll().pet else catQ.poll().pet
    }
    fun pollCat(): Cat {
        if (catQ.isEmpty) throw RuntimeException("cat queue is empty")
        return catQ.poll().pet as Cat
    }
    fun pollDog(): Dog {
        if (dogQ.isEmpty) throw RuntimeException("dog queue is empty")
        return dogQ.poll().pet as Dog
    }
}