"Coding Interview Guide" -- 猫狗队列

【题目】　　

宠物、狗和猫的类如下：
public class Pet
{
    private String type;
 
    public Pet(String type)
    {
        this.type = type;
    }
 
    public String getPetType()
    {
        return this.type;
    }
}
 
public class Dog extends Pet
{
    public Dog()
    {
        super("Dog");
    }
}
 
public class Cat extends Pet
{
    public Cat()
    {
        super("cat");
    }
}
 
实现一种猫狗队列的结构，要求如下：
(1) 用户可以调用add方法将Cat类或Dog类的实例放入队列中；
(2) 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
(3) 用户可以调用pollDog方法，将队列中Dog类的实例按照进队列的先后顺序依次弹出；
(4) 用户可以调用pollCat方法，将队列中Cat类的实例按照进队列的先后顺序依次弹出；
(5) 用户可以调用isEmpty方法，检查队列中是否还有Dog或Cat的实例；
(6) 用户可以调用isDogQueueEmpty方法，检查队列中是否有Dog类的实例；
(7) 用户可以调用isCatQueueEmpty方法，检查队列中是否有Cat类的实例。
             

【分析】

　　队列是一种只允许在一端插入，在另一端删除且不可访问除了队头元素外的其它元素的数据结构，插入的一端称为队尾，删除的一端称为队头，具有“先进先出”的特性，即先进队的元素也先出队。

　　猫狗队列的结构要求pollDog方法和pollCat方法可以分别将队列中的Dog类、Cat类实例按照进队的先后顺序依次弹出。如果将Dog类实例和Cat类实例放在一个队列中，则pollDog方法和pollCat方法无法实现，因为队列中的元素除了队头元素可以访问外，其它的元素是不可以访问的，所以队列中的元素只能依次弹出，而不能根据类型弹出，所以解决方法是把Cat类实例和Dog类实例分别放到两个不同的队列中。

　　猫狗队列的结构要求pollAll方法将猫狗队列中的元素按照进队的先后顺序依次弹出，但是因为我们选择用两个不同的队列分别存放Cat类实例和Dog类实例，那么怎么知道两个队列中元素在猫狗队列中的先后关系呢？解决方法是对于进队的每个Cat类实例和Dog类实例都打上一个时间戳，用于跟踪实例进猫狗队列的先后顺序，因此需要将Cat类实例和Dog类实例包装到一个对象中，该对象不仅包括Dog类或Cat类实例，还包括各自的时间戳。

　　import java.util.Queue;
　　import java.util.LinkedList;　　

  1 public class PetEnterQueue    // CatDogQueue中的元素类型
{
    private Pet pet;      //pet存储Cat或Dog类实例的引用
    private int count;         // Cat或Dog类实例对应的时间戳，用于记录进队的先后顺序

    public PetEnterQueue(Pet pet, int count)
    {
        this.pet = pet;
    this.count = count;
    }

    public Pet getPet()
    {
    return pet;
    }

    public int getCount()
    {
    return count;
    }

    public String getType()
    {
    return getPet().getPetType();
    }
}

public class CatDogQueue
{
    private Queue<PetEnterQueue> dogQ;     // dogQ存放Dog类实例
    private    Queue<PetEnterQueue> catQ;    // catQ存放Cat类实例
    private int count;            // 用来产生各实例的时间戳

    public CatDogQueue()
    {
    dogQ = new LinkedList<>();
    catQ = new LinkedList<>();
    count = 0;
    }

    public void add(Pet pet)
    {
        if(pet.getPetType().equals("Dog"))
    {
        dogQ.add(new PetEnterQueue(pet, count++));
    }
    else if(pet.getPetType().equals("Cat"))
    {
        catQ.add(new PetEnterQueue(pet, count++));
    }
    else
    {
        throw new RuntimeException("err, pet is not the instance of Cat or Dog class.");
    }
    }
    
    public Pet pollAll()
    {
        if(!isDogQueueEmpty() && !isCatQueueEmpty())
    {
        if(dogQ.peek().getCount() < catQ.peek().getCount())
        {
                return pollDog();
            }
            else
        {
        return pollCat();
            }
    }
    else if(!isDogQueueEmpty())
    {
            return pollDog();
    }
    else if(!isCatQueueEmpty())
    {
            return pollCat();
    }
    else
    {
            throw new RuntimeException("err, the CatDogQueue is empty.");
    }
    }

    public Dog pollDog()
    {
    if(!isDogQueueEmpty())
    {
            return (Dog)dogQ.poll().getPet();
    }
    else
    {
            throw new RuntimeException("err, dog queue is empty.");
    }
    }

    public Cat pollCat()
    {
        if(!isCatQueueEmpty())
    {
            return (Cat)catQ.poll().getPet();
    }
    else
    {
            throw new RuntimeException("err, cat queue is empty.");
    }
    }

    public boolean isEmpty()
    {
    return dogQ.isEmpty() && catQ.isEmpty();
    }

    public boolean isDogQueueEmpty()
    {
    return dogQ.isEmpty();
    }

    public boolean isCatQueueEmpty()
    {
    return catQ.isEmpty();
    }
}                

来源：左程云老师《程序员代码面试指南》