数据结构预算法学习笔记（9):图解数据结构与算法-栈和队列（五）&（六）：猫狗队列问题

立即学习:https://edu.csdn.net/course/play/29510/422746?utm_source=blogtoedu

栈和队列（五）&（六）：猫狗队列

 

猫狗队列问题

题目：运用队列的功能，在指定用户的类的基础上，实现以下各种功能

要求：

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

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

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

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

5用户可以调用IsSEmpy方法, 检查队列中是否还有dog或cat的实例:

6.用户可以调用isDogEmpty方法,检查队列中是否有dog类的实例:

7.用户可以调用IsCaEmpty方法。检查队列中是否有cart类的实例。

 

 

猫狗队列问题常见的设计错误

错误1: cat队列只放cat实例,dog队列只放dog实例,再用一个总队列放所有的实例。

错误原因:cat、dog以及总队列的更新问题。虽然pollAll可以满足，pollCat的时候，Cat队列可以全部弹出，但是Pet队列如何同步，pollDog也是同样的问题。

错误2: 用哈希表, key表示一个cat实例或dog实例, value表示这个实例进队列的次序。

错误原因: 不能支持—个实例多次进队列的功能需求,因为哈希表的key只能对应一个value值

错误3: 将用户原有的cat或dog类改写,加一个计数项来表示某一个实例进队列的时间。

错误原因: 不能擅自改变用户的类结构。

 

【方法思路】

新定义一个类，将原有的用户的类作为成员变量之一，再添加一个count作为时间戳进行排序，根据时间戳来poll

每次比较count, 哪边小弹出哪边

【代码】

Pet类

public class Pet { private String type; public Pet(String type) { this.type = type; } public Pet() { super(); } public String getType() { return type; } }

Cat类

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

Dog类

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

新定义的PetEnterQueue类，Pet作为属性，并设置时间戳属性

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 long getCount() { return count; } public String getPetEnterQueue(){ return this.getPetEnterQueue(); } }

CatDogQueue

import sun.rmi.runtime.NewThreadAction; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; /** * 代码只是为了实现我们的想法 * 不是学习算法和数据结构中最重要的东西 * * */ public class CatDogQueue { private Queue<PetEnterQueue> dogQ; private Queue<PetEnterQueue> catQ; private long count; public CatDogQueue() { this.dogQ = new LinkedList<PetEnterQueue>(); this.catQ = new LinkedList<PetEnterQueue>(); this.count = 0; } public void add(Pet pet) { if (pet.getType().equals("dog")) { this.dogQ.add(new PetEnterQueue(pet, this.count++)); } else if (pet.getType().equals("cat")) { this.catQ.add(new PetEnterQueue(pet, this.count++)); } else { throw new RuntimeException("err, not dog or cat"); } } public Pet pollAll() { if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) { if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) { return this.dogQ.poll().getPet(); } else { return this.catQ.poll().getPet(); } } else if (!this.dogQ.isEmpty()) { return this.dogQ.poll().getPet(); } else if (!this.catQ.isEmpty()) { return this.catQ.poll().getPet(); } else { throw new RuntimeException("err, queue is empty!"); } } public Pet pollDog() { if (!this.isDogQueueEmpty()) { return this.dogQ.poll().getPet(); } else { throw new RuntimeException("Dog queue is empty ! "); } } public Pet pollCat() { if (!this.isCatQueueEmpty()) { return this.catQ.poll().getPet(); } else { throw new RuntimeException("Cat queue is empty!"); } } public boolean isEmpty() { return this.dogQ.isEmpty() && this.catQ.isEmpty(); } public boolean isDogQueueEmpty() { return this.dogQ.isEmpty(); } public boolean isCatQueueEmpty() { return this.catQ.isEmpty(); } public static void main(String[] args) { CatDogQueue catDogQueue = new CatDogQueue(); System.out.println(catDogQueue.count); catDogQueue.add(new Pet("cat")); catDogQueue.add(new Pet("cat")); catDogQueue.add(new Pet("cat")); catDogQueue.add(new Pet("dog")); catDogQueue.add(new Pet("cat")); catDogQueue.add(new Pet("dog")); catDogQueue.add(new Pet("cat")); catDogQueue.add(new Pet("dog")); catDogQueue.add(new Pet("dog")); System.out.println(catDogQueue.count); System.err.println(catDogQueue.catQ.size()); for (int i = 0; i< catDogQueue.catQ.size() - 1 ; i++){ System.out.println(catDogQueue.pollDog().getType()); } for (int i = 0; i< catDogQueue.count ; i++){ System.out.println(catDogQueue.pollAll().getType()); } } }