栈和队列（4）--猫狗队列

宠物、狗和猫的类如下： 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(String type) { super("cat"); } }

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

用户可以调用add方法将cat类或者dog类的实例放入队列中；用户可以调用pollAll方法，将队列中所有的实例按照队列的先后顺序依次弹出；用户可以调用pollDog方法，将队列中dog类的实例按照队列的先后顺序依次弹出；用户可以调用pollCat方法，将队列中cat类的实例按照队列的先后顺序依次弹出；用户可以调用isEmpty方法，检查队列中是否还有dog和cat的实例；用户可以调用isDogEmpty方法，检查队列中是否还有do的实例；用户可以调用isCatEmpty方法，检查队列中是否还有cat的实例。 误区： cat队列只放cat实例，dog队列只放dog实例，再用一个总队列放所有的实例。 原因--cat、dog以及总队列的更新问题。 用哈希表，key表示一个cat实例或者dog实例，value表示这个实例进队列序的次序。 原因--不能支持一个实例多次进队列的功能需求，因为哈希表的key只能对应一个value的值。 思考： 将不同的实例盖上时间戳，在加入实例时，盖上时间戳，生成PetEnterQueue类的实例，然后放入dogQ或者cat!Q。 只想弹出dog类的实例时，从dogQ里不断弹出就行。想俺诗经顺序弹出实例时，比较这两个队列头的时间戳，谁早弹谁。 实现代码： package algorithm_4; public class Pet { private String type; public Pet(String type) { this.type = type; } public String getPetType(){ return this.type; } } package algorithm_4; import algorithm_4.Pet;; public class Dog extends Pet { public Dog() { super("dog"); } } package algorithm_4; public class Cat extends Pet { public Cat() { super("cat"); } } package algorithm_4; 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 getEnterPetTye(){ return this.pet.getPetType(); } } package algorithm_4; import java.util.LinkedList; import java.util.Queue; 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; } 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("err, not dog or cat"); } } 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("err, queue is empty!"); } } public Dog pollDog(){ if(!this.isDogQueueEmpty()){ return (Dog) this.dogQ.poll().getPet(); } else{ throw new RuntimeException("Dog queue is empty!"); } } public Cat pollCat(){ if(!this.isCatQueueEmpty()){ return (Cat) this.catQ.poll().getPet(); } else{ throw new RuntimeException("Cat queue is empty!"); } } public boolean isEmpty(){ return this.dogQ.isEmpty() && this.catQ.isEmpty(); } public boolean isDogQueueEmpty(){ return this.dogQ.isEmpty() ; } public boolean isCatQueueEmpty(){ return this.catQ.isEmpty() ; } }