题目
动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1:
输入： ["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"] [[], [[0, 0]], [[1, 0]], [], [], []] 输出： [null,null,null,[0,0],[-1,-1],[1,0]]
示例2:
输入： ["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"] [[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []] 输出： [null,null,null,null,[2,1],[0,0],[1,0]]
解题
方法一：双队列
由于先进先出的原则，要取狗，就狗队列pop，要取猫，就猫队列pop
当取任意动物时
- 没有猫，就取狗
- 没有狗，就取猫
- 都有时，取先进收容所的
注意，都没有的情况，已经包含在情况1里了，因为取狗前会判断，有没有狗
那么对于情况3，可以添加一个进入收容所的次序(cnt)，来判断，每添加一个动物cnt++
队列中，存放(cnt,动物编号)，这样子，就可以对情况3，使用判断cnt大小，来判断哪个动物先进的收容所。
(cnt越小，说明进的越早，应该最先出收容所)
class AnimalShelf { private: queue<vector<int>> queueCat;//(cnt,动物编号) queue<vector<int>> queueDog; int cnt=0; public: AnimalShelf() { } void enqueue(vector<int> animal) { if(animal[1]==0) queueCat.push({cnt,animal[0]});//(cnt,编号) else queueDog.push({cnt,animal[0]}); cnt++; } vector<int> dequeueAny() { if(queueCat.empty()) return dequeueDog();//如果没有猫，就取狗 if(queueDog.empty()) return dequeueCat();//如果没有狗，就取猫 if(queueCat.front()[0]<queueDog.front()[0]) return dequeueCat();//猫狗都有，就取最老的(编号最小) else return dequeueDog(); } vector<int> dequeueDog() { if(queueDog.empty()) return {-1,-1};//如果没有狗 else{ int id=queueDog.front()[1];//编号 queueDog.pop(); return {id,1};//返回 编号,狗 } } vector<int> dequeueCat() { if(queueCat.empty()) return {-1,-1}; else{ int id=queueCat.front()[1]; queueCat.pop(); return {id,0};//返回 编号,猫 } } };
