04_猫狗队列

简介: 04_猫狗队列

猫狗队列

【题目】

宠物、狗和猫的类如下:

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类的实例。

注意:

  1. cat队列只放cat实例,dog队列只放dog实例,再用一个总队列放所有的实例。
    错误原因:cat、dog以及总队列的更新问题
  2. 用哈希表,key表示一个cat实例或dog实例,value表示这个实例进队列的次序。
    错误原因:不能支持一个实例多次进队列的功能需求,因为哈希表的key只能对应一个value值。
  3. 将用户原有的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;
            }
        }
    }
}

本题在牛客网上也有对应的原题,可找到!!!!

相关文章
|
6月前
|
人工智能 测试技术 Windows
技术心得:威威猫系列之吃鸡腿
技术心得:威威猫系列之吃鸡腿
35 0
|
C++
c++游戏——狗的人生
c++游戏——狗的人生
89 0
|
编译器 C语言 C++
缺省参数!C++教你如何成为一名优秀的舔狗
缺省参数!C++教你如何成为一名优秀的舔狗
缺省参数!C++教你如何成为一名优秀的舔狗
|
机器学习/深度学习 API 数据处理
基于Paddlex超简单的猫狗分类
基于Paddlex超简单的猫狗分类
295 0
基于Paddlex超简单的猫狗分类
|
弹性计算 安全 Linux
二胡的狗屋
我是一个我的世界游戏爱好者
127 0
二胡的狗屋
主人含泪杀病狗
主人含泪杀病狗
161 0
主人含泪杀病狗
程序人生 - 狗可以看到紫外线吗?
程序人生 - 狗可以看到紫外线吗?
135 0
|
人工智能 黑灰产治理
这些动物,你认识几个呢?
对于16届全国大学生智能车中的智能视觉组中的动物集合进行识别测试。
这些动物,你认识几个呢?
|
机器学习/深度学习 Python 算法框架/工具
小狗分类器,你家的狗子是个什么狗?
小狗分类器可以做什么? 通过这个分类器,你只需要上传照片,就可以得到小狗的品种,以及更多的信息。 这就是所谓的「机器学习」,让机器自己去“学习”。我们今天要做的这个分类任务,是一个“监督学习”的过程。
1039 0