美文网首页程序员代码面试
【算法题】猫狗队列

【算法题】猫狗队列

作者: 埋没随百草 | 来源:发表于2018-12-02 23:21 被阅读0次

    实现一种猫狗队列的结构,要求如下:

    • 用户可以调用add方法将cat类或者dog类的实例放入队列中;
    • 用户可以调用pollAll方法,将队列中所有的实例按照队列的先后顺序依次弹出;
    • 用户可以调用pollDog方法,将队列中dog类的实例按照队列的先后顺序依次弹出;
    • 用户可以调用pollCat方法,将队列中cat类的实例按照队列的先后顺序依次弹出;
    • 用户可以调用isEmpty方法,检查队列中是否还有dog和cat的实例;
    • 用户可以调用isDogEmpty方法,检查队列中是否还有do的实例;
    • 用户可以调用isCatEmpty方法,检查队列中是否还有cat的实例。

    解题思路

    设计一个PetEntity类,用于保存Pet对象以及入队列的序号。同时使用两个栈分别用于存储Cat和Dog。add时把Cat和Dog分别添加到对应的队列,poll时检查入队列序号,序号小的先出队列。

    实现代码

    import java.util.Queue;
    
    public class CatDogQueue {
        private Queue<PetEntity> catQueue;
        private Queue<PetEntity> dogQueue;
        private long seq;
    
        public CatDogQueue(Queue<PetEntity> catQueue, Queue<PetEntity> dogQueue, long seq) {
            this.catQueue = catQueue;
            this.dogQueue = dogQueue;
            this.seq = seq;
        }
    
        public void add(Pet pet) {
            if (pet.getType().equals("cat")) {
                catQueue.add(new PetEntity(pet, this.seq++));
            } else if (pet.getType().equals("dog")) {
                dogQueue.add(new PetEntity(pet, this.seq++));
            } else {
                throw new RuntimeException("Unknown pet type");
            }
        }
    
        public Pet pollAll() {
            if (!dogQueue.isEmpty() && !catQueue.isEmpty()) {
                if (dogQueue.peek().getSeq() < catQueue.peek().getSeq()) {
                    return dogQueue.peek().getPet();
                } else {
                    return catQueue.peek().getPet();
                }
            } else if (!dogQueue.isEmpty()) {
                return dogQueue.peek().getPet();
            } else if (!catQueue.isEmpty()) {
                return catQueue.peek().getPet();
            } else {
                throw new RuntimeException("CatDogQueue is empty");
            }
        }
    
        public Cat pollCat() {
            if (!catQueue.isEmpty()) {
                return (Cat) catQueue.peek().getPet();
            } else {
                throw new RuntimeException("catQueue is empty");
            }
        }
    
        public Dog pollDog() {
            if (!dogQueue.isEmpty()) {
                return (Dog) dogQueue.peek().getPet();
            } else {
                throw new RuntimeException("dogQueue is empty");
            }
        }
    
        public boolean isEmpety() {
            return catQueue.isEmpty() && dogQueue.isEmpty();
        }
    
        public boolean isCatQueueEmpty() {
            return catQueue.isEmpty();
        }
    
        public boolean isDogQueueEmpty() {
            return dogQueue.isEmpty();
        }
        
        public static class PetEntity {
            private Pet pet;
            private long seq;
    
            public PetEntity(Pet pet, long seq) {
                this.pet = pet;
                this.seq = seq;
            }
    
            public Pet getPet() {
                return pet;
            }
    
            public long getSeq() {
                return seq;
            }
    
            public String getType() {
                return getPet().getType();
            }
        }
    
        public static class Pet {
            private String type;
    
            public Pet(String type) {
                this.type = type;
            }
    
            public String getType() {
                return type;
            }
        }
    
        public static class Dog extends Pet {
            public Dog(String type) {
                super("dog");
            }
        }
    
        public static class Cat extends Pet {
            public Cat(String type) {
                super("cat");
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:【算法题】猫狗队列

        本文链接:https://www.haomeiwen.com/subject/tdxecqtx.html