首页 > 代码库 > 数据结构设计

数据结构设计

之前在简书上初步总结过几个有关栈和队列的数据结构设计的题目。http://www.jianshu.com/p/d43f93661631

实现猫狗队列,猫类型和狗类型都继承自Pet类型

Pet类型如下

技术分享

技术分享

技术分享

要求如下:

技术分享

思路:

如果使用一个队列来存储,那么无法区分猫和狗;如果使用两个队列,那么pollAll()中猫和狗的先后顺序无法区分;继续思考时候可以使用一个时间戳,相当于一个map,键为pet,值为其如队列的时间,但是这带来一个问题就是同一个宠物多次进队列的问题。所以,采用新建一个数据结构PetEnterQueue类型,对之前的宠物进行封装。这个类型包含Pet和count两个变量,然后猫狗队列中实际存放的是这个PetEnterQueue的实例,如队列的时候可以检测时猫还是狗然后封装进count之后进入各自的队列(猫和狗),然后pollDog pollPet的时候自个儿弹就行了,pollAll的时候先弹出两个队列头的count较小的。

 

数据结构设计