猫狗队列问题

发表于 | 更新于 | 阅读次数：

猫狗队列。

题目

宠物、狗和猫的类如下：

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

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

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

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

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

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

  1. 用户可以调用 add 方法将cat类或dog类的实例放入队列中；
  2. 用户可以调用 pollAll 方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
  3. 用户可以调用 pollDog 方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
  4. 用户可以调用 pollCat 方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
  5. 用户可以调用 isEmpty 方法，检查队列中是否还有dog或cat的实例；
  6. 用户可以调用 isDogEmpty 方法，检查队列中是否有dog类的实例；
  7. 用户可以调用 isCatEmpty 方法，检查队列中是否有cat类的实例。

核心思想

设计一个pet的包装类型，包装类型中加上 count 表示这个实例对象是第几个被添加的，这样可以在执行 pollAll() 的时候根据 count 来决定返回哪一个对象。

设计两个队列，两个队列中放的都是包装类型的对象。

push的时候把要入队列的对象先包装起来，再放入队列中。

代码

DogCatQueue 类

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
public class DogCatQueue {
    private Queue<PetBox> dogQueue;
    private Queue<PetBox> catQueue;
    private long count;

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

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

    public Pet pollAll() {
        if (!this.dogQueue.isEmpty() && !this.catQueue.isEmpty()) {
            if (this.dogQueue.peek().getCount() < this.catQueue.peek().getCount()) {
                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 RuntimeException("err, queue is empty!");
        }
    }

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

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

    public boolean isEmpty() {
        return this.dogQueue.isEmpty() && this.catQueue.isEmpty();
    }

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

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

PetBox 类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class PetBox {
    private Pet pet;
    private long count;

    public PetBox(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return this.pet;
    }

    public long getCount() {
        return this.count;
    }

    public String getEnterPetType() {
        return this.pet.getPetType();
    }
}

完整测试代码

完整代码中，为了测试方便，把上边的类都改为了静态内部类。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    public static class Pet {
        private String type;

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

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

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

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

    public static class PetBox {
        private Pet pet;
        private long count;

        public PetBox(Pet pet, long count) {
            this.pet = pet;
            this.count = count;
        }

        public Pet getPet() {
            return this.pet;
        }

        public long getCount() {
            return this.count;
        }

        public String getEnterPetType() {
            return this.pet.getPetType();
        }
    }

    public static class DogCatQueue {
        private Queue<PetBox> dogQueue;
        private Queue<PetBox> catQueue;
        private long count;

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

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

        public Pet pollAll() {
            if (!this.dogQueue.isEmpty() && !this.catQueue.isEmpty()) {
                if (this.dogQueue.peek().getCount() < this.catQueue.peek().getCount()) {
                    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 RuntimeException("err, queue is empty!");
            }
        }

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

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

        public boolean isEmpty() {
            return this.dogQueue.isEmpty() && this.catQueue.isEmpty();
        }

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

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

    public static void main(String[] args) {
        DogCatQueue dogCatQueue = new DogCatQueue();

        Pet dog1 = new Dog();
        Pet cat1 = new Cat();
        Pet dog2 = new Dog();
        Pet cat2 = new Cat();
        Pet dog3 = new Dog();
        Pet cat3 = new Cat();

        dogCatQueue.add(dog1);
        dogCatQueue.add(cat1);
        dogCatQueue.add(dog2);
        dogCatQueue.add(cat2);
        dogCatQueue.add(dog3);
        dogCatQueue.add(cat3);

        dogCatQueue.add(dog1);
        dogCatQueue.add(cat1);
        dogCatQueue.add(dog2);
        dogCatQueue.add(cat2);
        dogCatQueue.add(dog3);
        dogCatQueue.add(cat3);

        dogCatQueue.add(dog1);
        dogCatQueue.add(cat1);
        dogCatQueue.add(dog2);
        dogCatQueue.add(cat2);
        dogCatQueue.add(dog3);
        dogCatQueue.add(cat3);
        while (!dogCatQueue.isDogQueueEmpty()) {
            System.out.println(dogCatQueue.pollDog().getPetType());
        }
        while (!dogCatQueue.isEmpty()) {
            System.out.println(dogCatQueue.pollAll().getPetType());
        }
    }
}