Java教程

算法-12猫狗队列

本文主要是介绍算法-12猫狗队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

实现一种猫狗队列的结构,要求如下: 1. 用户可以调用 add 方法将 cat 或者 dog 放入队列中 2. 用户可以调用 pollAll 方法将队列中的 cat 和 dog 按照进队列的先后顺序依次弹出 3. 用户可以调用 pollDog 方法将队列中的 dog 按照进队列的先后顺序依次弹出 4. 用户可以调用 pollCat 方法将队列中的 cat 按照进队列的先后顺序依次弹出 5. 用户可以调用 isEmpty 方法检查队列中是否还有 dog 或 cat 6. 用户可以调用 isDogEmpty 方法检查队列中是否还有 dog 7. 用户可以调用 isCatEmpty 方法检查队列中是否还有 cat

输入描述:

第一行输入一个整数 n 表示 用户的操作总次数。

以下 n行 每行表示用户的一次操作

每行的第一个参数为一个字符串 s,若 s = “add”, 则后面接着有 “cat x”(表示猫)或者“dog x”(表示狗),其中的 x 表示猫狗的编号。

输出描述:

对于每个操作:

若为 “add”,则不需要输出。

以下仅列举几个代表操作,其它类似的操作输出同理。

若为 “pollAll”,则将队列中的 cat 和 dog 按照进队列的先后顺序依次弹出。(FIFO),格式见样例。

若为 "isEmpty",则检查队列中是否还有 dog 或 cat, 为空则输出 “yes”, 否则输出 “no”。

示例1

输入:
11
add cat 1
add dog 2
pollAll
isEmpty
add cat 5
isDogEmpty
pollCat
add dog 10
add cat 199
pollDog
pollAll

输出:
cat 1
dog 2
yes
yes
cat 5
dog 10
cat 199

思路

用两个队列来分别存放猫狗元素,再通过count的大小来判断入整个队列的次序;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// 题目中给定的类
class Pet{
    private String type;
    private int x;
 
    public Pet (String type,int x){
        this.type = type;
        this.x = x;
    }
 
    public String getPetType(){
        return this.type;
    }
 
    public int getX(){
        return this.x;
    }
}

class Dog extends Pet{
    public Dog(int x) {
        super("dog", x);
    }
}
 
class Cat extends Pet{
    public Cat(int x){
        super("cat", x);
    }
}

// 可以为不同的实例盖上时间戳的新的类
class PetEnterQueue{
    private Pet pet;
    private long count;
    
    public PetEnterQueue(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }
    
    public Pet getPet() {
        return pet;
    }
 
    public long getCount() {
        return count;
    }
    
    public String getEnterPetType(){
        return this.pet.getPetType();
    }
}
// 猫狗队列
class DogCatQueue{
    
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;
    
    public DogCatQueue(){
        this.dogQ = new LinkedList<>();
        this.catQ = new LinkedList<>();
        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("error, not dog&nbs***bsp;cat");
        }
    }
    // 注意弹出的不能是自己定义的PetEnterQueue
    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("error,queue is empty");
        }
    }
    
    public Dog pollDog(){
        if(!dogQ.isEmpty()){
            return (Dog)this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("Dog queue is empty");
        }
    }
    
    public Cat pollCat(){
        if(!catQ.isEmpty()){
            return (Cat)this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("Cat queue is empty");
        }
    }
    
    public boolean isEmpty(){
        return this.catQ.isEmpty() && this.dogQ.isEmpty();
    }
    
    public boolean isDogQueueEmpty(){
        return this.dogQ.isEmpty();
    }
    
    public boolean isCatQueueEmpty(){
        return this.catQ.isEmpty();
    }
    
}

public class Main{
    public static void main(String[] args) throws IOException  {
        DogCatQueue dogCatQueue = new DogCatQueue();
        
        Pet pet = null;
        StringBuilder res = new StringBuilder();
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            String op = sc.next();
            switch(op){
                case "add":
                    String who = sc.next();
                    int num = sc.nextInt();
                    if(who.equals("cat")){
                        dogCatQueue.add(new Cat(num));
                    }else if(who.equals("dog")){
                        dogCatQueue.add(new Dog(num));
                    }else{
                        throw new RuntimeException("Invalid add.");
                    }
                    break;
                case "pollAll":
                    while(!dogCatQueue.isEmpty()){
                        pet = dogCatQueue.pollAll();
                        // 用链式append没有警告!!
                        // 类型和分数中间记得加上空格
                        res.append(pet.getPetType()).append(" ").append(pet.getX()).append('\n');
                    }
                    break;
                case "pollDog":
                    while(!dogCatQueue.isDogQueueEmpty()){
                        pet = dogCatQueue.pollDog();
                        res.append("dog").append(" ").append(pet.getX()).append('\n');
                    }
                    break;
                case "pollCat":
                    while(!dogCatQueue.isCatQueueEmpty()){
                        pet = dogCatQueue.pollCat();
                        res.append("cat").append(" ").append(pet.getX()).append('\n');
                    }
                    break;
                case "isEmpty":
                    if(!dogCatQueue.isEmpty()){
                        res.append("no").append('\n');
                    }else{
                        res.append("yes").append('\n');
                    }
                    break;
                case "isDogEmpty":
                    if(!dogCatQueue.isDogQueueEmpty()){
                        res.append("no").append('\n');
                    }else{
                        res.append("yes").append('\n');
                    }
                    break;
                case "isCatEmpty":
                    if(!dogCatQueue.isCatQueueEmpty()){
                        res.append("no").append('\n');
                    }else{
                        res.append("yes").append('\n');
                    }
                    break;
            }
        }
        // 最后的输出只能由一个回车,所以是System.out.println(res.substring(0,res.length()-1));或者下面这个
        System.out.print(res);
    }
}

 

这篇关于算法-12猫狗队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!