leetcode面试题：动物收容所（考查对队列的理解和运用）

题目：

有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。

enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。

dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

示例：

输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
 输出：
[null,null,null,[0,0],[-1,-1],[1,0]] 

示例解释：

收容所可以收容动物，也可以有收养人对收容所里的动物进行收养

猫咪类型为0，狗狗类型为1

1.执行 enqueue（0，0），收容编号为0的猫咪，无返回值

2.执行 enqueue（1，0），收容编号为1的猫咪，无返回值

3.执行 dequeueCat（），现在要收养一只猫咪，只能收养最老的，所以就是编号为0的猫咪，返回值为[0,0]

4.执行 dequeueDog（），现在要收养一只小狗，但是目前收容所没有狗狗，所以返回值为[-1,-1]

5.执行dequeueAny（），随机收养，不指定猫狗，选择目前收容所中最老的动物即可，此时收容所只剩一只编号为1的猫咪，所以返回[1,0]

解题思路：

1.创建两个队列分别保存收容进来的小猫和小狗，对头永远是最先进来的，也就是最老的

2.在随机收养时，如果两种动物都有存量，要注意比较哪个动物更老

源代码如下：

class AnimalShelf {
public://创建两个队列，一个是存放猫猫的，一个是存放狗狗的queue<int> cat,dog;AnimalShelf() {}//入队操作void enqueue(vector<int> animal) {//获取动物的id和type//id表示动物编号，type表示动物类型int id=animal[0],type=animal[1];//type=0表示该动物是猫猫，就添加到猫猫队列中if(type==0) cat.push(id);//否则添加到狗狗队列中else dog.push(id);}//随机收养vector<int> dequeueAny() {//如果猫猫队列为空，那么只能收养狗狗if(cat.empty()) return dequeueDog();//反之，同理else if(dog.empty()) return dequeueCat();//如果两个都不空，就比较猫猫最老的和狗狗最老的//选择这两个中最老的进行收养if(cat.front()<dog.front()) return dequeueCat();return dequeueDog();}//收养狗狗vector<int> dequeueDog() {//若队列为空，无法收养，返回{-1，-1}if(dog.empty()) return{-1,-1};//获得对头元素的idint id=dog.front();//将其出队dog.pop();//收养最老的，也就是对头的那只猫return {id,1};}//收养猫猫vector<int> dequeueCat() {//若队列为空，无法收养，返回{-1，-1}if(cat.empty()) return{-1,-1};//获得对头元素的idint id=cat.front();//将其出队cat.pop();//收养最老的，也就是对头的那只猫return {id,0};}
};