猫狗队列

宠物、猫、狗的实现如下：

public class Pet{  
    private String type;  
    public Pet(String type){  
        this.type = type;  
    }  
    public String getPetType(){  
        return this.type;  
    }  
}  
public class Dog extends Pets{  
    public Dog(){  
        super("Dog");  
    }  
}  
public class Cat extends Pet{  
    public Cat(){  
        super("Cat");  
    }  
}  

实现一种猫狗队列的结构，要求如下：

用户可以调用add方法将cat类或者dog类的实例放入队列中；
用户可以调用pollAll方法，将队列中所有的实例按照队列的先后顺序依次弹出；
用户可以调用pollDog方法，将队列中dog类的实例按照队列的先后顺序依次弹出；
用户可以调用pollCat方法，将队列中cat类的实例按照队列的先后顺序依次弹出；
用户可以调用isEmpty方法，检查队列中是否还有dog和cat的实例；
用户可以调用isDogEmpty方法，检查队列中是否还有do的实例；
用户可以调用isCatEmpty方法，检查队列中是否还有cat的实例。
解法一：
如果只用一个队列的话，考虑到猫狗混在在一起，而有时候又需要从队列中间弹出数据（比如头尾都是狗而中间是猫，需要弹出猫），所以现成的队列和栈均不能使用，而哈希表在这道题目中也不适合，唯一适合的是LinkedList。在LinkedList中删除数据不需要移动更多数据，这一点要优于ArrayList。

public class Solution {
    LinkedList<Pet> list = new LinkedList<>();
    public void add(Pet pet) {
        list.add(pet);
    }

    public Pet pollAll() {
        if(list.isEmpty()) {
            throw new RuntimeException("Queue is empty!")
        }
        return list.get(0);
    }

    public Dog pollDog() {
        for(int i = 0; i < list.size();) {
            Pet current = list.get(i);
            if(current.getType().equals("Dog")) {
                list.remove(i);
                return (Dog)current;
            }
            i++;
        }
        return null;
    }

    public Cat pollCat() {
        for(int i = 0; i < list.size();) {
            Pet current = list.get(i);
            if(current.getType().equals("Cat")) {
                list.remove(i);
                return (Cat) current;
            }
            i++;
        }
        return null;
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public boolean isDogEmpty() {
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).getType().equals("Dog")) {
                return false;
            }
        }
        return true;
    }

    public boolean isCatEmpty() {
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i).getType().equals("Cat")) {
                return false;
            }
        }
        return true;
    }
}

但是这种方法仅add、pollAll和isEmpty性能较好，pollCat、pollDog、isDogEmpty和isCatEmpty均需要遍历数组，性能较差。

解法二：
若要提高效率，则只能将Cat和Dog分开存储在两个队列中，但是若直接存的话无法保证总体的顺序。一种策略是改写Cat和Dog类增加计数器，但是这种策略很不推荐，因为不能擅自改变用户的类结构。于是我们可以采用另一种策略，使用包装类将原来的类进行包装。

新的包装类如下：

public class MyPet {
    private Pet pet;
    private int count;
    public MyPet(Pet pet, int count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return pet;
    }

    public void setPet(Pet pet) {
        this.pet = pet;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }
}

于是，我们可以构建两个队列分别存放猫和狗的包装类，包装类中的count相当于时间戳，记录了输入的先后顺序。这样pollCat、pollDog、isDogEmpty和isCatEmpty均得到了优化。代码原理较简单便不一一解释，直接放代码。

public class Solution {
    Queue<MyPet> catQueue = new LinkedList<>();
    Queue<MyPet> dogQueue = new LinkedList<>();
    int count = 0;
    public void add(Pet pet) {
        count++;
       if(pet.getType().equals("Cat")) {
           catQueue.add(new MyPet(pet, count));
       }
       else if(pet.getType().equals("Dog")){
         dogQueue.add(new MyPet(pet, count));
       }
       else {
           throw new RuntimeException("invalid input");
       }
    }

    public Pet pollAll() {
        if(!catQueue.isEmpty() && !dogQueue.isEmpty()) {
            if(catQueue.peek().getCount() < dogQueue.peek().getCount()) {
                return catQueue.poll().getPet();
            }
            else {
                return dogQueue.poll().getPet();
            }
        }
        else if(!catQueue.isEmpty()) {
            return catQueue.poll().getPet();
        }
        else if(!dogQueue.isEmpty()) {
            return dogQueue.poll().getPet();
        }
        else {
            throw new RuntimeException("Queue is Empty!");
        }
    }

    public Dog pollDog() {
        if(dogQueue.isEmpty()) {
            throw new RuntimeException("Queue is Empty!");
        }
        return (Dog) dogQueue.poll().getPet();
    }

    public Cat pollCat() {
        if(dogQueue.isEmpty()) {
            throw new RuntimeException("Queue is Empty!");
        }
        return (Cat) catQueue.poll().getPet();
    }

    public boolean isEmpty() {
        return catQueue.isEmpty() && dogQueue.isEmpty();
    }

    public boolean isDogEmpty() {
        return dogQueue.isEmpty();
    }

    public boolean isCatEmpty() {
        return catQueue.isEmpty();
    }
}