猫狗队列

本题来自程序员代码面试指南

---

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

●　用户可以调用add方法将cat类或dog类的实例放入队列中；

●　用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；

●　用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；

●　用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；

●　用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；

●　用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；

●　用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例

这个题的用双队列实现，要解决的关键点是如何判断俩个队列的队头元素入队的先后。解决的方法是扩展宠物类，加上计数器（时间戳）来判断入队的先后（不能改变原来的类，我觉得这个题更加侧重的是面向对象扩展的思想）

public class DogCatQueue {
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue() {
        this.dogQ = new LinkedList<PetEnterQueue>();
        this.catQ = new LinkedList<PetEnterQueue>();
        this.count = 0;//计数器
    }

    /**
     * 添加操作
     * @param pet
     */
    public void add(Pet pet) {
        if (pet.getPetType().equals("dog")) {
            this.dogQ.add(new PetEnterQueue(pet, this.count++));
        } else if (pet.getPetType().equals("cat")) {
            this.catQ.add(new PetEnterQueue(pet, this.count++));
        } else {
            throw new RuntimeException("添加的既不是猫也不是狗");
        }
    }

    /**
     * 返回队头对象
     * @return
     */
    public Pet pollAll() {
        if (! this.dogQ.isEmpty() && ! this.catQ.isEmpty()) {
            if(this.dogQ.peek().getCount()  <  this.catQ.peek().getCount()) {
                return this.dogQ.poll().getPet();
            } else {
                return this.catQ.poll().getPet();


            }
        } else if (! this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else if (! this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("队列是空的");
        }
    }

    /**
     * 返回队头的狗
     * @return
     */
    public Dog pollDog() {
        if (! this.isDogQueueEmpty()) {
            return (Dog) this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("狗队列为空");
        }
    }

    public Cat pollCat() {
        if (! this.isCatQueueEmpty()) {
            return (Cat) this.catQ.poll().getPet();
        } else
            throw new RuntimeException("猫队列为空");
    }

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

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

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

public class Pet {
    private String type;

    public Pet(String type) {
        this.type = type;
    }

    public String getPetType() {
        return this.type;
    }
}

public class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}

public class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}

public class PetEnterQueue {
    private Pet pet;
    private long count;

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

    public Pet getPet() {
        return this.pet;
    }

    public long getCount() {
        return this.count;
    }

    public String getEnterPetType() {
        return this.pet.getPetType();
    }
}

最后附上github地址