猫狗队列的再解

也是头一次在其他的这类型网站投稿,不过似乎没有markdown语法…,以下来自我的个人博客近期所写的,对猫狗
队列的解答。

猫狗队列是一个很经典的问题了吧,在书上我也翻看了很久;而网上的答案呢,也是千篇一律的,跟书的代码也是一字不差的,几乎除了照搬似乎都没什么思路可言的,甚至连书上提到注意的点都没有…

一开始我是没什么思路的,翻来覆去研究书上,发现原来挺简单;但用思路写起来还真不是一回事,挺难的。各个问题涉及到的地方很多,就是如何解决的问题很多,特别是题目的第二点要求。

以下是我研究书好一会做题的过程,也发现书上一些不太好的问题吧,比如对装载 Pet 实例的类命名为:PetEnterQueue ,真的很容易造成误解以为是个队列;而且我觉得书中所写的这类似乎有些多余了,这并不是说他的实现方式不对,这样的实现思路也的确是要这样做的;但其实只要创建一个由猫和狗组合成的共同的类就好了,实现的方法写在其中也OK,以下是我的解题过程。

题目:宠物、狗、猫类代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.pat;

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”);
}
}
}

  • 用户可以调用add() ,cat类或dog类的实例放入队列中
  • 用户可以调用pollAll(),将队列中所有实例按照队列先后顺序依次弹出
  • 用户可以调用pollDog()、pollCat(),将队列中dog类、cat类的实例按照进队列的先后顺序依次弹出
  • 用户可以调用isEmpty(),检查队列中是否还有dog、cat的实例
  • 用户可以调用isDogEmpty()、isCatEmpty(),分别检查队列中是否还有dog、cat的实例

思路:

1) 用户可以调用add() ,cat类或dog类的实例放入队列中

add() 也需要装载一个 Pet 的实例(多态),如何区分继承Pet类的 cat 和 dog 对象

1
2
3
 public Cat(){
    super("cat");
}

由于Cat 和 Dog 的构造方法有 super("xxx") 这下可以用 equals 比较字符串区分不同的 cat 和 dog 对象,然后将符合条件的对象加入进 Cat 或 Dog 的队列中。

1
2
3
4
5
//最好避免魔法值,此中仅为示例
boolean bool = pet.getPetType().equal("cat");
if(bool){
 add(pet);
}

2) 用户可以调用pollAll(),将队列中所有实例按照队列先后顺序依次弹出

按照依次按顺序弹出,根据类别的队列中的对象总数或队列的大小,来决定先那个队列使用 poll() 将所有对象出列。比如 Cat 队列的对象少于 Dog 队列,就将 Cat 队列先执行 poll() 。这里将 Cat 队列命名为 catQ,Dog 队列则为 dogQ

1
2
3
4
5
if(catQ.size() < dogQ.size()){
    this.catQ.poll();
}else{
    this.dogQ.poll();
}

当然,在此之前还需要做一个非空的判断

1
2
3
  if (this.catQ.isEmpty() && this.dogQ.isEmpty()) {
      throw new RuntimeException("empty");
}

实现:

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
package com.pet.dc.queue;

import com.pet.Pet;
import java.util.LinkedList;
import java.util.Queue;

/**
* @author lorem
*/
public class CatDogQueue {
private Queue<Pet> catQ;
private Queue<Pet> dogQ;

String cat = “cat”;
String dog = “dog”;

public CatDogQueue() {
// linkedList 本质上和queue 是一样的,先进先出
this.catQ = new LinkedList<Pet>();
this.dogQ = new LinkedList<Pet>();
}

public void add(Pet pet) {
if (pet.getPetType().equals(cat)) {
this.catQ.add(pet);
}else if(pet.getPetType().equals(dog)) {
this.dogQ.add(pet);
} else {
throw new RuntimeException(“err,not cat not dog”);
}
}

public void pollAll() {
if (this.catQ.isEmpty() && this.dogQ.isEmpty()) {
throw new RuntimeException(“empty”);
}
if (this.catQ.size() > this.dogQ.size()) {
this.dogQ.poll();
} else {
this.catQ.poll();
}
}

public void pollDog() {
if (!this.dogQ.isEmpty()) {
this.dogQ.poll();
} else {
throw new RuntimeException(“dog is empty”);
}
}

public void pollCat() {
if (!this.catQ.isEmpty()) {
this.catQ.poll();
} else {
throw new RuntimeException(“cat is empty”);
}
}

public boolean isEmpty() {
if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
return false;
}
return true;
}

public boolean isDogEmpty() {
return this.dogQ.isEmpty();
}

public boolean isCatEmpty() {
return this.catQ.isEmpty();
// if (this.catQ.isEmpty()){
// return true;
// }else{
// return false;
// }
}
}

测试:

测试的话,在 maven 模块配置好 Junit4 再到 test 测试文件夹写好测试类,即可测验了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import com.pet.Pet;
import com.pet.dc.queue.CatDogQueue;
import org.junit.Test;

public class JTest {
@Test
public void test() {
Pet cat1 = new Pet(“cat”);
Pet cat2 = new Pet(“cat”);
Pet dog1 = new Pet(“dog”);
CatDogQueue cdq = new CatDogQueue();
cdq.add(cat1);
cdq.add(cat2);
// assert cat1.getPetType().equals(“cat”);
System.out.println(cdq.isDogEmpty());

}
}

看了一个照搬书上还不错的例子,通过给定的类实现猫狗队列,他的 offer() 挺好的,如果队列已满再插入直接返回 false,不像add() 抛出异常中断执行 。异常尽早暴露原则的话,哦,那真是看情况而定了。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 猫狗队列的再解


Latest posts by lorem (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (1)
    • nockyQ
    • 2018/11/11 12:27上午

    并不能根据size判断入队列的顺序

您必须 登陆 后才能发表评论

return top