实现一种狗猫队列的结构

【题目】宠物、狗和猫的类如下：

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

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

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

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

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

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

用户可以调用 isdogempty方法,检查队列中是否有dog类的实例；

用户可以调用 iscatempty方法,检查队列中是否有cat类的实例；

【解答】

本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。

本题为开放类型的面试题,希望读者能有自己的实现,在这里列出几种常见的设计错误:

cat队列只放cat实例,dog队列只放dog实例,再用一个总队列放所有的实例。错误原因:cat、dog以及总队列的更新问题。

用哈希表,key表示个ca实例或dog实例,vaue表示这个实例进队列的次序。错误原因:不能支持一个实例多次进队列的功能需求因为哈希表的key只能对应—个value值。

将用户原有的ca或dog类改写,加个计数项来表示某一个实

例进队列的时间。错误原因:不能擅自改变用户的类结构。

本题实现将不同的实例盖上时间戳的方法,但是又不能改变用户本身的类,所以定义一个新的类,具体实现请参看如下的petenterquueue类。

Petenterqueue类在构造时,pet是用户原有的实例,coun就是这个实例的时间戳。

我们实现的队列其实是 Petenter Queue类的实例。大体说来,首先有一个不断累加的数据项,用来表示实例进队列的时间;同时有两个队列,一个是只放dog类实例的队列dogQ,另一个是只放cat类实例的队列catQ。

在加入实例时,如果实例是dog,就盖上时间戳,生成对应的Petenterqueue类的实例,然后放入dogQ;如果实例是cat,就盖上时间戳,生成对应的 Petenterqueue类的实例,然后放入catQ。具体过程请参看如下 Dogcatqueue类的add方法。

只想弹出dog类的实例时,从dgQ里不断单出即可,具体过程请参看如下 Dog Catqueue类的 poll Dog方法。

只想弹出cat类的实例时,从catQ里不断弹出即可,具体过程请

参看如下 Dog Catqueue类的po‖Cat方法。

想按实际顺序弹出实例时,因为dgQ的队列头表示所有dog实例中最早进队列的实例,同时catQ的队列头表示所有的ca实例中最早进队列的实例。则比较这两个队列头的时间戳,谁更早,就弹出谁具体过程请参看如下 Dog Catqueue类的pollall方法。

Dog Catqueue类的整体代码如下：

欢迎一起来交流代码那点事：https://mp.csdn.net/postedit/80325970?utm_source=zwqt