经典老番:猫狗队列

发表于 分类于 阅读次数：

题目

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

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

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

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

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

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

  3. 用户可以调用isDogEmpty方法，检查队列中是否还有do的实例；

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

给定猫狗类如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static class Pet{
        private String type;

        public Pet(String type) {
            this.type = type;
        }
        public String getPetTyoe() {
            return this.type;
        }
    }

    public static class Cat extends Pet{
        public Cat() {
            super("cat");
        }
    }
    public static class Dog extends Pet {
        public Dog() {
            super("dog");
        }
    }

思路

一开始我脑子一热，想用三个队列，分别存储dog，cat和All，但想了一下在pollCat或者Dog时，All的队列并不能确定其队头是否为该项。
如图所示

这让我们意识到需要为Dog和Cat做一个标识，便于分辨其先后顺序,这样只需要两个队列就可以完成该操作。由于我们无法修改Dog和Cat这两个类，所以我们自己封装一个类

下面来看下实际代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
public static class Pet{
    private String type;

    public Pet(String type) {
        this.type = type;
    }
    public String getPetType() {
        return this.type;
    }
}

public static class Cat extends Pet{
    public Cat() {
        super("cat");
    }
}
public static class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}

//封装count和pet
public static 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 getType() {
        return this.pet.getPetType();
    }
}

public static class CatDogQueue {

    private Queue<PetEnter> catQueue;
    private Queue<PetEnter> dogQueue;
    private long count;

    public CatDogQueue() {
        this.catQueue = new LinkedList<>();
        this.dogQueue = new LinkedList<>();
        this.count = 0;
    }

    public void add(Pet pet) {
        if(pet.getPetType().equals("dog")) {
            dogQueue.add(new PetEnter(pet,this.count++));
        } else if(pet.getPetType().equals("cat")) {
            catQueue.add(new PetEnter(pet,this.count++));
        }else {
            throw new IllegalArgumentException("not dog or cat");
        }
    }

    public Pet pollAll() {
        if(!this.dogQueue.isEmpty() && !this.catQueue.isEmpty()) {
            if(this.dogQueue.peek().count < this.catQueue.peek().count) {
                return this.dogQueue.poll().getPet();
            }else {
                return this.catQueue.poll().getPet();
            }
        } else if(!this.dogQueue.isEmpty()) {
            return this.dogQueue.poll().getPet();
        } else if(!this.catQueue.isEmpty()) {
            return this.catQueue.poll().getPet();
        } else {
            throw new IllegalArgumentException("queue is empty");
        }
    }

    public Dog pollDog() {
        if(!this.isDogQueueEmpty()) {
            return (Dog) dogQueue.poll().getPet();
        } else {
            throw new IllegalArgumentException("dog queue is empty");
        }
    }

    public Cat pollCat() {
        if(!this.isCatQueueEmpty()) {
            return (Cat) catQueue.poll().getPet();
        } else {
            throw new IllegalArgumentException("cat queue is empty");
        }
    }

    public boolean isDogQueueEmpty() {
        return dogQueue.isEmpty();
    }
    public boolean isCatQueueEmpty() {
        return catQueue.isEmpty();
    }
}

代码很简单，在此就不做过多的解释了。