猫狗队列
【题目】
宠物、狗和猫的类如下:
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"); } }
实现一种狗猫队列的结构,要求如下:
- 用户可以调用add方法将cat类或dog类的实例放入队列中;
- 用户可以调用pollAll方法,将队列中所有的实例按照进队列的先后顺序依次弹出;
- 用户可以调用pollDog方法,将队列中dog类的实例按照进队列的先后顺序依次弹出;
- 用户可以调用isEmpty方法,检查队列中是否还有dog或cat的实例;
- 用户可以调用isDogEmpty方法,检查队列中是否有dog类的实例;
- 用户可以调用isCatEmpty方法,检查队列中是否有Cat类的实例。
注意:
- cat队列只放cat实例,dog队列只放dog实例,再用一个总队列放所有的实例。
错误原因:cat、dog以及总队列的更新问题 - 用哈希表,key表示一个cat实例或dog实例,value表示这个实例进队列的次序。
错误原因:不能支持一个实例多次进队列的功能需求,因为哈希表的key只能对应一个value值。 - 将用户原有的cat或dog类改写,加一个计数项来表示某一个实例进队列的时间。
错误原因:不能擅自改变用户的类结构。
参考代码如下:
import java.util.Queue; import java.util.LinkedList; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; // 如何解决不能修改封装的类 /** * 1. 在实际情况下,对于封装好的类往往不能修改其中的代码,如何对其增加属性呢?即对其进行再封装 * 2. 在本题中,有两个类,它们有沟通的父类,为了对两个类一起封装,采用了封装其共同父类的方法。 */ class Pet { private String type; private int id; public Pet(String type, int id) { this.type = type; this.id = id; } public String getPetType() { return this.type; } public int getId() { return this.id; } } class Cat extends Pet { public Cat(int id) { super("cat", id); } } class Dog extends Pet { public Dog(int id) { super("dog", id); } } // 创建一个类, 用于收容上述两个类 class PetEnter { // 增加一个变量,记录数量,作为时间戳 private Pet pet; private long count; public PetEnter(Pet pet, long count) { this.pet = pet; this.count = count; } public Pet getPet() { return this.pet; } public long getCount() { return this.count; } public String getPetEnterType() { return this.pet.getPetType(); } } // 使用两个队列存放不同的类 /** * 1.为了存放不同的两个类,一种办法是放到一个队列中,操作的时候,每一次都要出队,包括弹出队列,判断队列中的每一个类是否为空,时间复杂度较高 * 2.使用"空间换时间"的思想,将两个类的对立队列封装好,使用时间戳的方式记录其进入队列的顺序,这样既可以操作总的序列,也可以单独操作不同的类 */ class DogCatQueue { private Queue<PetEnter> catQueue; private Queue<PetEnter> dogQueue; private long count; // 时间戳 public DogCatQueue() { this.catQueue = new LinkedList<>(); this.dogQueue = new LinkedList<>(); this.count = 0; } // 用户调用add方法可以将cat或者dog放入队列中 public void add(Pet pet) { //按照类型放入动物队列中 if (pet.getPetType().equals("dog")) { this.dogQueue.add(new PetEnter(pet, this.count++)); } else if (pet.getPetType().equals("cat")) { this.catQueue.add(new PetEnter(pet, this.count++)); } else { throw new RuntimeException("error no thus class"); } } public Pet pollAll() { if (!this.catQueue.isEmpty() && !this.dogQueue.isEmpty()) { if (this.catQueue.peek().getCount() < this.dogQueue.peek().getCount()) { return this.catQueue.poll().getPet(); } else { return this.dogQueue.poll().getPet(); } //否则就是其中一个为空 } else if (!this.catQueue.isEmpty()) { //狗空了,猫没有空 return this.catQueue.poll().getPet(); } else if (!this.dogQueue.isEmpty()) { //猫空了, 狗没有空 return this.dogQueue.poll().getPet(); } else { return null; } } public Pet pollDog() { if (!this.dogQueue.isEmpty()) { return this.dogQueue.poll().getPet(); } return null; } public Pet pollCat() { if (!this.catQueue.isEmpty()) { return this.catQueue.poll().getPet(); } return null; } // 判断队列是否为空 public boolean isEmpty() { if (this.dogQueue.isEmpty() && this.catQueue.isEmpty()) { return true; } return false; } // 判断狗队列是否为空 public boolean isDogEmpty() { if (this.dogQueue.isEmpty()) { return true; } return false; } // 判断猫队列是否为空 public boolean isCatEmpty() { if (this.catQueue.isEmpty()) { return true; } return false; } public static void main(String[] args) throws IOException { DogCatQueue dogCatQueue = new DogCatQueue(); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(reader.readLine()); // 保存结果的数组 for (int i = 0; i < N; ++i) { StringBuilder result = new StringBuilder(); String[] strArr = reader.readLine().split(" "); String option = strArr[0]; switch (option) { case "add": String type = strArr[1]; if (type.equals("dog")) { int id = Integer.parseInt(strArr[2]); dogCatQueue.add(new Pet("dog", id)); } else if (type.equals("cat")) { int id = Integer.parseInt(strArr[2]); dogCatQueue.add(new Pet("cat", id)); } break; case "pollAll": while (!dogCatQueue.isEmpty()) { Pet pet = dogCatQueue.pollAll(); result.append(pet.getPetType()).append(" ").append(pet.getId()).append("\n"); } System.out.print(result); break; case "pollDog": while (!dogCatQueue.isDogEmpty()) { Pet pet = dogCatQueue.pollDog(); result.append(pet.getPetType()).append(" ").append(pet.getId()).append("\n"); } System.out.print(result); break; case "pollCat": while (!dogCatQueue.isCatEmpty()) { Pet pet = dogCatQueue.pollCat(); result.append(pet.getPetType()).append(" ").append(pet.getId()).append("\n"); } System.out.print(result); break; case "isDogEmpty": System.out.println(dogCatQueue.isDogEmpty() ? "yes" : "no"); break; case "isCatEmpty": System.out.println(dogCatQueue.isCatEmpty() ? "yes" : "no"); break; case "isEmpty": System.out.println(dogCatQueue.isEmpty() ? "yes" : "no"); break; } } } }
本题在牛客网上也有对应的原题,可找到!!!!