题目描述

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如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]]
  说明:

收纳所的最大容量为20000

解题思路与代码

三队列法（我第一次写的错误版本）

首先我想说明的是，这道题其实不算什么难题，但是我的代码还是出现了错误，先给出我的原代码。
我的这个代码的逻辑就是，如果需要添加元素，就先去往any队列里放元素，然后根据动物种类，往cat或者dog队列里放元素。
如果是从any中取元素出来，那就先取走any队头的，然后根据队头与cat还是dog的对头相等，相应的取走cat或dog的队头。

如果是取cat或者dog，就先让cat，或dog出一个元素，然后拿着这个元素去和any队列一一比较，如果不相等，就先存入help队列中，否则就删除any的队头。然后再将help存入any。

这是我第一个版本的逻辑。感觉有很多地方很多余，但不得不说，我这个逻辑是绝对正确的。

class AnimalShelf {
public:queue any;queue dog;queue cat;AnimalShelf() {}void enqueue(vector animal) {any.push(animal[0]);if(animal[1] == 0)cat.push(animal[0]);else dog.push(animal[0]);}vector dequeueAny() { vector temp;if(any.empty()) {return {-1,-1};}int cur = any.front();temp.push_back(cur);any.pop();if(!cat.empty() && cat.front() == cur){cat.pop();temp.push_back(0);}else if(!dog.empty() && dog.front() == cur){dog.pop();temp.push_back(1);} return temp;}vector dequeueDog() {vector temp;if(dog.empty()) {return {-1,-1};}int cur = dog.front();temp.push_back(dog.front());temp.push_back(1);dog.pop();queue help;while(!any.empty() && cur != any.front()){help.push(any.front());any.pop();}any.pop();while(!help.empty()){any.push(help.front());help.pop();}return temp;}vector dequeueCat() {vector temp;if(cat.empty()) {return {-1,-1};}int cur = cat.front();temp.push_back(cat.front());temp.push_back(0);cat.pop();queue help;while(!any.empty() && cur != any.front()){help.push(any.front());any.pop();}any.pop();while(!help.empty()){any.push(help.front());help.pop();}return temp;}
}; 

照理说，我的这个代码应该是对的，但是有一个测试用例我一直通过不了，这是原因：

Line 175: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebebebe for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebebebe: note: pointer points here

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_deque.h:180:16

我去问了chatGPT，它给我的答复是：

• 这个错误通常发生在对齐问题上。 可能是因为您的系统架构不支持8字节对齐，而代码中使用了64位队列。如果您将其修改为32位队列，则可能解决此问题。

那我现在确定的我的代码逻辑没问题，就是系统不支持而已。但是有一点必须得说，我这个逻辑虽然是对的，但是又丑又长，中间很多地方其实是多余的。现在我重新修改了一下我的三队列法

再次尝试写三队列法

这一次我同样用的是三队列法，但是其中的逻辑大大的不一样了。首先，我的是三个队列里存储的都是一个vector，vector中都是两个元素，分别就是动物编号和动物种类。这样方便添加或删除。

添加逻辑不变，就是说，只要来了动物，先往any里填，按照动物种类，是cat放cat队列中，否则是dog。

删除逻辑：

• 对于dequeueDog这个方法来说，就直接先判断dog队列是否为空，若为空，则返回{-1,-1} 否则，先记录一下dog的队首元素，删除队首元素，返回记录元素。dequeueCat这个方法的删除逻辑也是一样的
• 对于dequeueAny这个方法来说，先判断cat，dog队列是否都为空，若都为空，则返回{-1,-1} 。否则，先设置标志为flag = true，返回变量temp。然后while循环判断any队列是否为空，并且标志位是否为true。
  在循环内若，cat队列不为空，且cat队首与any队首相等，则temp = any的这个队首，同时标志位为false，cat弹出元素。同理dog的判断与cat的判断条件一致。一轮循环快要结束时，any弹出队首元素。

具体示例请看我的代码：

class AnimalShelf {
public:queue> any;queue> cat;queue> dog;AnimalShelf() {}void enqueue(vector animal) {any.emplace(animal);if(animal[1] == 0) cat.emplace(animal);else dog.emplace(animal);}vector dequeueAny() {if(dog.empty() && cat.empty()) return {-1,-1};bool flag = true;vector temp ;while(!any.empty() && flag){if(!cat.empty() && any.front() == cat.front()){temp = cat.front();cat.pop();flag = false;}else if(!dog.empty() && any.front() == dog.front()){temp = dog.front();dog.pop();flag = false;}any.pop();}return temp;}vector dequeueDog() {if(dog.empty()) return {-1,-1};vector temp = dog.front();dog.pop();return temp;}vector dequeueCat() {if(cat.empty()) return {-1,-1};vector temp = cat.front();cat.pop();return temp;}
};

复杂度分析：

• 时间复杂度：
  • enqueue()为O(1),因为队列要求插入和删除都要在队尾或者队头。
  • dequeueAny()为O(n),因为在最坏的情况下需要遍历三个队列，并从队列中弹出一个元素，每次都要检查是否符合要求。
  • dequeCat与dequeDog的时间复杂度都是O(1),因为队列 pop 操作和 front 操作都是 O(1) 的时间复杂度。
• 空间复杂度：
  • enqueue空间复杂度最坏情况下是O(n)，n 代表队列的长度（目前any、dog、cat 都是等长的）。
  • dequeueAny，dequeCat与dequeDog都是O(1),它们使用常量额外的存储来维护队列。

所以从代码总体来说，时间复杂度是O(n)，空间复杂度是O(n)，其中 n 代表队列中所有元素的数量。

双队列法

其实双队列法比三队列法简单好多。只需要维护两个队列。一个cat，一个dog。它们都存储的元素是vector。cat来添加cat。dog来添加dog。要cat弹出cat，要dog弹出dog，随便比一下大小就行。

具体实现看代码：

class AnimalShelf {
public:queue> cat;queue> dog;AnimalShelf() {}void enqueue(vector animal) {if(animal[1] == 0) cat.emplace(animal);else dog.emplace(animal);}vector dequeueAny() {if(dog.empty() && cat.empty()) return {-1,-1};if(!cat.empty() && dog.empty()){vector temp = cat.front();cat.pop();return temp;}else if(!dog.empty() && cat.empty()){vector temp = dog.front();dog.pop();return temp;}else{if(cat.front()[0] > dog.front()[0]){vector temp = dog.front();dog.pop();return temp;}else{vector temp = cat.front();cat.pop();return temp;}}}vector dequeueDog() {if(dog.empty()) return {-1,-1};vector temp = dog.front();dog.pop();return temp;}vector dequeueCat() {if(cat.empty()) return {-1,-1};vector temp = cat.front();cat.pop();return temp;}
};

这段代码的时间复杂度分析如下：

• enqueue函数中，由于只是将元素插入队列中，因此时间复杂度为O(1)。

• dequeueAny函数中，虽然它对cat和dog队列进行了比较，但是由于所有操作都是基于队头元素（front）执行，所以算法的运行时间主要取决于所有队列的长度和已弹出前相同类型的动物的数量。因此，在最坏的情况下，两个while循环需要处理所有动物，访问每个元素至少一次，因此时间复杂度为O(n)。

• dequeueDog和dequeueCat函数中也只是查看并删除前面的元素，因此时间复杂度为O(1)。

这所有的方法的总体的空间复杂度是O(n)，其中n是所有被加入队列中的动物数量，因为该程序使用了一个数组来存储包含每种类型动物的队列，队列的具体大小等于数组的大小。

总结

又是一道考验面向对象的程序设计题。不算难，但是你要是陷入了一个逻辑的漩涡，那也挺麻烦的。