力扣面试题 23 - 动物收容所

题目：

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

说明:

1. 收纳所的最大容量为20000

思路：

1. 使用一个双端链表的结构来表示动物队列。队列包含两种类型的动物：猫和狗。每个动物节点包含其编号和种类信息。
2. 收养动物但不指定猫还是狗时，如何判断谁更“老”呢？可以通过比较序号的方式判断。

具体函数设计：

1. 数据结构设计

• 使用了一个双端链表的结构来表示动物队列。队列包含两种类型的动物：猫和狗。每个动物节点包含其编号和种类信息。
• 使用 *head 和 *tail 分别表示队列的头部和尾部指针，便于在队列两端进行操作。
• 需要分别处理猫、狗和任意动物的入队和出队操作。

2. animalShelfCreate 创建队列

• 初始化一个空的 AnimalShelf 结构体，其中 head 和 tail 都初始化为 NULL，表示队列为空。

3. animalShelfEnqueue 入队操作

• 根据传入的动物数据（编号和种类），创建一个新的动物节点。
• 如果队列为空（即 *tail == NULL），将新的动物节点作为队列的第一个元素，*head 和 *tail 都指向该节点。
• 如果队列不为空，则根据动物种类（猫或狗）将新节点添加到对应的队列末尾，更新 *tail。

4. animalShelfDequeueAny 任意出队操作

• 判断队列是否为空。如果队列为空，直接返回 NULL。
• 如果队列非空，返回头部节点（第一个入队的动物）。更新 *head，让它指向下一个动物节点。如果更新后队列为空，还需要将 *tail 置为 NULL。

5. animalShelfDequeueDog 狗出队操作

• 判断队列是否为空。如果为空，返回 NULL。
• 否则，从队列中寻找最早进入队列的狗并将其出队。更新头部指针 *head，并且如果队列为空，还需要将 *tail 置为 NULL。

6. animalShelfDequeueCat 猫出队操作

• 判断队列是否为空。如果为空，返回 NULL。
• 否则，从队列中寻找最早进入队列的猫并将其出队。更新头部指针 *head，并且如果队列为空，还需要将 *tail 置为 NULL。

7. animalShelfFree 释放队列

• 释放队列中所有节点的内存。

C代码如下：

// 定义 Animal 结构体
typedef struct Animal {
    int id;
    int type; // 0 表示猫，1 表示狗
    struct Animal* next;
} Animal;

// 定义 AnimalShelf 结构体
typedef struct {
    Animal* dogHead;
    Animal* catHead;
    Animal* dogTail;
    Animal* catTail;
} AnimalShelf;

// 创建 AnimalShelf
AnimalShelf* animalShelfCreate() {
    AnimalShelf* shelf = (AnimalShelf*)malloc(sizeof(AnimalShelf));
    shelf->dogHead = NULL;
    shelf->catHead = NULL;
    shelf->dogTail = NULL;
    shelf->catTail = NULL;
    return shelf;
}

// 辅助函数：将动物加入队列
void enqueueAnimal(Animal** head, Animal** tail, int id, int type) {
    Animal* newAnimal = (Animal*)malloc(sizeof(Animal));
    newAnimal->id = id;
    newAnimal->type = type;
    newAnimal->next = NULL;
    if (*tail) {
        (*tail)->next = newAnimal;
    } else {
        *head = newAnimal;
    }
    *tail = newAnimal;
}

// 辅助函数：从队列中移除动物
Animal* dequeueAnimal(Animal** head, Animal** tail) {
    if (!*head) return NULL;
    Animal* animal = *head;
    *head = (*head)->next;
    if (!*head) {
        *tail = NULL;
    }
    return animal;
}

int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize);

int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize);

// 加入动物
void animalShelfEnqueue(AnimalShelf* obj, int* animal, int animalSize) {
    if (animal[1] == 0) {
        enqueueAnimal(&obj->catHead, &obj->catTail, animal[0], animal[1]);
    } else if (animal[1] == 1) {
        enqueueAnimal(&obj->dogHead, &obj->dogTail, animal[0], animal[1]);
    }
}

// 收养任意动物
int* animalShelfDequeueAny(AnimalShelf* obj, int* retSize) {
    *retSize = 2;
    if (!obj->dogHead && !obj->catHead) {
        int* result = (int*)malloc(2 * sizeof(int));
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    if (!obj->dogHead) return animalShelfDequeueCat(obj, retSize);
    if (!obj->catHead) return animalShelfDequeueDog(obj, retSize);

    if (obj->dogHead->id < obj->catHead->id) {
        return animalShelfDequeueDog(obj, retSize);
    } else {
        return animalShelfDequeueCat(obj, retSize);
    }
}

// 收养狗
int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize) {
    *retSize = 2;
    Animal* dog = dequeueAnimal(&obj->dogHead, &obj->dogTail);
    if (!dog) {
        int* result = (int*)malloc(2 * sizeof(int));
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = dog->id;
    result[1] = dog->type;
    free(dog);
    return result;
}

// 收养猫
int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize) {
    *retSize = 2;
    Animal* cat = dequeueAnimal(&obj->catHead, &obj->catTail);
    if (!cat) {
        int* result = (int*)malloc(2 * sizeof(int));
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = cat->id;
    result[1] = cat->type;
    free(cat);
    return result;
}

// 释放 AnimalShelf
void animalShelfFree(AnimalShelf* obj) {
    Animal* temp;
    while (obj->dogHead) {
        temp = obj->dogHead;
        obj->dogHead = obj->dogHead->next;
        free(temp);
    }
    while (obj->catHead) {
        temp = obj->catHead;
        obj->catHead = obj->catHead->next;
        free(temp);
    }
    free(obj);
}