宠物、猫、狗的实现如下：
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();
}
}
