Cat dog queue

【 subject 】

Pets 、 The categories of dogs and cats are as follows ：

Implementation of a dog and cat queue structure , Requirements are as follows ：

● Users can call add Methods will cat Class or dog Class to queue ;

● Users can call pollAll Method , Pop up all instances in the queue in the order of entering the queue ;

● Users can call pollDog Method , Queue up dog The instances of the class pop up in the order of entering the queue ;

● Users can call pollCat Method , Queue up cat The instances of the class pop up in the order of entering the queue ;

● Users can call isEmpty Method , Check if there are any in the queue dog or cat Example ;

● Users can call isDogEmpty Method , Check if there are any in the queue dog Class ;

● Users can call isCatEmpty Method , Check if there are any in the queue cat Class .

【 Ideas 】

This question examines the ability to implement special data structures and the ability to design algorithms for special functions .

This is an open type interview question , I hope the readers can have their own realization , Here are a few common design mistakes ：

● cat Queue only cat example ,dog Queue only dog example , And then use a general queue to put all the instances . The reason for the error ：cat、dog And the update of the general queue .

● Using hash table ,key It means a cat Example or dog example ,value Indicates the order in which this instance is queued . The reason for the error ： It cannot support the function requirement that an instance is queued multiple times , Because the hash table key There's only one value value .

● The user's original cat or dog Class rewriting , Add a count item to indicate the time when an instance enters the queue . The reason for the error ： You cannot change the user's class structure without authorization .

This topic implements the method of stamping different instances , But you can't change the user's own class , So define a new class , For the specific implementation, please refer to the following PetEnterQueue class .

【 Code 】

Pet

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: Pet * @Description:  Pets  * @author:  Cowherd Conan  * @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:  Dog  * @author:  Cowherd Conan  * @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:  cat  * @author:  Cowherd Conan  * @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:  Cowherd Conan  * @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:  Cat dog queue  * @author:  Cowherd Conan  * @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;    }    // take Cat Class or Dog Class to queue     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(" error , The pet type is neither cat nor dog ");        }    }    // All instances in the queue pop up in the order of entering the queue     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(" error , The queue is empty ！");        }    }    // In line Dog The instances of the class pop up in the order of entering the queue     public Dog pollDog(){        if(!dogQ.isEmpty()){            return (Dog)dogQ.poll().getPet();        }else{            throw new RuntimeException(" error , The queue is empty ！");        }    }    // In line Cat The instances of the class pop up in the order of entering the queue     public Cat pollCat(){        if(!catQ.isEmpty()){            return (Cat)catQ.poll().getPet();        }else{            throw new RuntimeException(" error , The queue is empty ！");        }    }    // Check if there are any in the queue Dog or Cat Example     public boolean isEmpty(){        return dogQ.isEmpty()&&catQ.isEmpty();    }    // Check if there are any in the queue Dog Class     public boolean isDogEmpty(){        return dogQ.isEmpty();    }    // Check if there are any in the queue Cat Class     public boolean isCatEmpty(){        return catQ.isEmpty();    }}

Test class

package pers.keafmd.accumulate.codeinterviewguide.catdogqueue;/** * Keafmd * * @ClassName: QueueTest * @Description:  test  * @author:  Cowherd Conan  * @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()); // Report errors     }}

The test results ：

dog1cat1dog2truefalsefalsecat2Exception in thread "main" java.lang.RuntimeException:  error , The queue is empty ！	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

Get it done ！