猫狗队列

【题目】

宠物、狗和猫的类如下：

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

● 用户可以调用add方法将cat类或dog类的实例放入队列中；

● 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；

● 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；

● 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；

● 用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；

● 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；

● 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

【思路】

本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。

本题为开放类型的面试题，希望读者能有自己的实现，在这里列出几种常见的设计错误：

● cat队列只放cat实例，dog队列只放dog实例，再用一个总队列放所有的实例。错误原因：cat、dog以及总队列的更新问题。

● 用哈希表，key表示一个cat实例或dog实例，value表示这个实例进队列的次序。错误原因：不能支持一个实例多次进队列的功能需求，因为哈希表的key只能对应一个value值。

● 将用户原有的cat或dog类改写，加一个计数项来表示某一个实例进队列的时间。错误原因：不能擅自改变用户的类结构。

本题实现将不同的实例盖上时间戳的方法，但是又不能改变用户本身的类，所以定义一个新的类，具体实现请参看如下的PetEnterQueue类。

【代码】

Pet

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: Pet * @Description: 宠物 * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:45 */public class Pet {    private String type;    public Pet(String type) {        this.type = type;    }    public String getType() {        return type;    }    public void setType(String type) {        this.type = type;    }}

Dog

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: Dog * @Description: 狗 * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:29 */public class Dog extends Pet{    public Dog(String type) {        super(type);    }}

Cat

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: Cat * @Description: 猫 * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:31 */public class Cat extends Pet{    public Cat(String type) {        super(type);    }}

PetEnterQueue

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: PetEnterQueue * @Description: * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:33 */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 pet;    }    public void setPet(Pet pet) {        this.pet = pet;    }    public long getCount() {        return count;    }    public void setCount(long count) {        this.count = count;    }}

CatDogQueue

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;import java.util.LinkedList;import java.util.Queue;/** * Keafmd * * @ClassName: CatDogQueue * @Description: 猫狗队列 * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:44 */public class CatDogQueue {    private Queue<PetEnterQueue> dogQ;    private Queue<PetEnterQueue> catQ;    private long count;    public CatDogQueue() {        this.dogQ = new LinkedList<>();        this.catQ = new LinkedList<>();        this.count = 0;    }    //将Cat类或Dog类的实例放入队列中    public void add(Pet pet){        if(pet.getType().contains("dog")){            dogQ.add(new PetEnterQueue(pet,this.count++));        }else if(pet.getType().contains("cat")){            catQ.add(new PetEnterQueue(pet,this.count++));        }else{            throw new RuntimeException("错误，宠物类型既不是猫也不是狗");        }    }    //队列中所有的实例按照进队列的先后顺序依次弹出    public Pet pollAll(){        if(!dogQ.isEmpty()&&!catQ.isEmpty()){            if(dogQ.peek().getCount()<catQ.peek().getCount()){                return dogQ.poll().getPet();            }else{                return catQ.poll().getPet();            }        }else if(!catQ.isEmpty()){            return catQ.poll().getPet();        }else if(!dogQ.isEmpty()){            return dogQ.poll().getPet();        }else{            throw new RuntimeException("错误，队列是空的！");        }    }    //队列中Dog类的实例按照进队列的先后顺序依次弹出    public Dog pollDog(){        if(!dogQ.isEmpty()){            return (Dog)dogQ.poll().getPet();        }else{            throw new RuntimeException("错误，队列是空的！");        }    }    //队列中Cat类的实例按照进队列的先后顺序依次弹出    public Cat pollCat(){        if(!catQ.isEmpty()){            return (Cat)catQ.poll().getPet();        }else{            throw new RuntimeException("错误，队列是空的！");        }    }    //检查队列中是否还有Dog或Cat的实例    public boolean isEmpty(){        return dogQ.isEmpty()&&catQ.isEmpty();    }    //检查队列中是否有Dog类的实例    public boolean isDogEmpty(){        return dogQ.isEmpty();    }    //检查队列中是否有Cat类的实例    public boolean isCatEmpty(){        return catQ.isEmpty();    }}

测试类

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: QueueTest * @Description: 测试 * @author: 牛哄哄的柯南 * @date: 2022-06-22 19:04 */public class QueueTest {    public static void main(String[] args) {        CatDogQueue queue = new CatDogQueue();        Dog dog1 = new Dog("dog1");        Dog dog2 = new Dog("dog2");        Cat cat1 = new Cat("cat1");        Cat cat2 = new Cat("cat2");        Cat cat3 = new Cat("cat3");        queue.add(dog1);        queue.add(cat1);        queue.add(cat2);        queue.add(cat3);        queue.add(dog2);        System.out.println(queue.pollAll().getType()); //dog1        System.out.println(queue.pollAll().getType()); //cat1        System.out.println(queue.pollDog().getType()); //dog2        System.out.println(queue.isDogEmpty()); //true        System.out.println(queue.isCatEmpty()); //false        System.out.println(queue.isEmpty()); //false        System.out.println(queue.pollAll().getType()); //cat2        System.out.println(queue.pollDog().getType()); //报错    }}

测试效果：

dog1cat1dog2truefalsefalsecat2Exception in thread "main" java.lang.RuntimeException: 错误，队列是空的！	at pers.keafmd.accumulate.codeinterviewguide.catdogqueue.CatDogQueue.pollDog(CatDogQueue.java:58)	at pers.keafmd.accumulate.codeinterviewguide.catdogqueue.QueueTest.main(QueueTest.java:32)Process finished with exit code 1

搞定！