LeetCode 622. 设计循环队列

一、题目描述
二、解题
- 1、方案1——数组实现，预留一个空判满
- - 1.1、成环思路
  - 1.2、初始化接口
  - 1.3、入队接口
  - 1.4、出队接口
  - 1.5、取队头接口
  - 1.6、取队尾接口
  - 1.7、判空接口
  - 1.8、判满接口
  - 1.9、释放接口
- 2、方案2——单向循环链表实现，计数器判满
- - 2.2、初始化接口
  - 2.3、入队接口
  - 2.4、出队接口
  - 2.5、取队头接口
  - 2.6、取队尾接口
  - 2.7、判空接口
  - 2.8、判满接口
  - 2.9、释放接口

一、题目描述

原题连接： 622. 设计循环队列
题目描述：
设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

提示：

所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

二、解题

1、方案1——数组实现，预留一个空判满

1.1、成环思路

我们知道，数组是一块连续的空间：
在这里插入图片描述
当然首位不相连，那么我们怎样才能让它成环呢？
其实我们可以灵活地运用对下标取模的方法来实现下标循环，因为如果下标超出了当前的最大下标，那么取模时候下标就会回归到前面的下标了。
例如，这里如果下标增长到了6：
在这里插入图片描述
那么取模数组的长度6之后，就变成了0，也就轮回了：

所以这就是我们要将数组设计成环的思路，其实就是通过下标的轮回实现循环访问。

所以我们的实现思路也基本出来了，我们使用两个指针：队头指针front和队尾指针rear来标识队头和队尾，起初我们让们都指向下标为0处：
在这里插入图片描述
然后后面如果我们要执行入队操作的话，先将数据放入rear指向的空间，再让rear向后走一步：

所以rear其实指向的是队尾元素的下一个元素。
而出队操作就很简单了，直接让front完后走一步就行了，比如我们现在要将第一个元素出队：
在这里插入图片描述
我们并不需要将原来的元素删除，因为这样设计的空间是复用的，后面在入队的元素，会将原来的元素给覆盖掉。

而且最后一定要记得在front和rear完后走后在对他们进行取余数组的长度，因为要成环嘛。

但是这里要事先说明一下，如果我们想要实现长度为k的环形链表，实际上我们是需要开辟k + 1个数组空间的，因为如果不多预留一个空间的话，判满就会变得很麻烦：
在这里插入图片描述
如图，因为我们设计的rear指向的队尾元素的下一个元素，所以如果我们之开辟k个空间的话，那么当队列为满的时候就是front和rear同时指向一个元素。
而我们知道当队列为空的时候，也是fornt和rear同时指向一个元素，这就矛盾了。
所以我们要在k空间的基础之上再开辟一个空间：
在这里插入图片描述
这样当rear指向的是front的前一个元素时候，队列就为满了。
而因为我们这里的坐标已经设计成循环的了，所以是的判断公式应该是：

(rear + 1) % (k + 1) == front % (k + 1)

好啦，这就是数组环形队列实现的主要思路了，接下来就可以来实现了。

1.2、初始化接口

我们先将初始化工作完成：

typedef struct {
    int *data;
    int front;
    int rear;
    int count; // 队列的实际元素个数
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (NULL == queue) {
        perror("malloc fail!\n");
        exit(-1);
    }
    queue->data = (int*)malloc((k + 1) * sizeof(int));
    queue->front = 0;
    queue->rear = 0;
    queue->count = k;
    return queue;
}

1.3、入队接口

在入队之前，我们先要判断队列是否已满，如果已满就直接返回false，如果没满，就执行上面说到过的思路，最后返回true。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->data[obj->rear] = value;
    obj->rear++;
    obj->rear %= obj->count + 1;
    return true;
}

1.4、出队接口

出队也是一样，如果队列为空就直接返回false，否则同样执行上面所提到的思路。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
    obj->front++;
    obj->front %= obj->count + 1;
    return true;
}

1.5、取队头接口

这个其实也没什么好说的，为空就返回-1，不为空就直接返回front所指向的元素。

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    return obj->data[obj->front];
}

1.6、取队尾接口

而取队尾这个接口就不同了，因为我们设计的rear是指向队尾元素的下一个元素，所以我么其实要返回的是rear的前一个位置的元素。
一般情况下，我们直接返回rear - 1处的元素即可：
在这里插入图片描述
但是还有一个特殊情况就是当rear为0的时候：

因为rear - 1 = -1，所以我们此时并不能直接用rear- 1来访问数组。
那要怎么办呢？
其实很简单，我们可以使用(rear - 1) + (k + 1)对k + 1取余，正常情况下rear - 1 > 0的时候，加上一个k + 1在对k + 1进行取余其实对结果没什么影响，而当rear - 1= -1时候，加法也就变成了减法，所以就变成了k对k + 1取余，其结果是k，正好是最后一个下标。

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    int RearIndex = (obj->count + obj->rear) % (obj->count + 1);
    return obj->data[RearIndex];
}

1.7、判空接口

对于这个接口，我们直接返回rear和fornt是否相等的结果即可：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

1.8、判满接口

这个接口的思路其实上面就已经讲过：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->count + 1) == (obj->front % (obj->count + 1));
}

1.9、释放接口

因为数组也是动态开辟出来的，所以再释放队列之前要先将数组给释放了。

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->data);
    obj->front = 0;
    obj->rear = 0;
    obj->count = 0;
    free(obj);
}

2、方案2——单向循环链表实现，计数器判满

可能大家在看到“环形队列”这几个字的时候都会想到要用环形链表来实现。因为环形链表本来就已经成环了，而且数组一样老是需要对下标进行取模，判满也比较简单：
在这里插入图片描述

我尝试过之后，确实觉得是比用数组实现的逻辑要简单一点。
而在这个方案中我们就换一种方法来判满，在队列中设计一个计数器变量size，然后每次入队或出队时相应的让size自增1或自减1即可，当size为0时候说明队列为空，当size等于k的时候就说明队列已满。
这样就不需要在预留一个节点了。

2.2、初始化接口

我们首先要把初始化工作做完，使用链表实现比起数组来比较复杂的就是在初始化时候要将节点开辟出来，并连接成环，这个操作其实比数组的直接开辟要复杂一点儿：

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (NULL == queue) {
        perror("malloc fail!\n");
        exit(-1);
    }
    ListNode *head = NULL; // 保存第一个节点
    ListNode *tail = NULL; // 保存最后一个节点
    int i = 0;
    for (i = 0; i < k; i++) {
        ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        if (NULL == node) {
            perror("malloc fail!\n");
            exit(-1);
        }
        if (0 == i) {
            head = node;
            tail = node;
            queue->front = head;
            queue->rear = head;
        } else {
            tail->next = node; // tail连接上后面的节点
            tail = tail->next; // tail完后走
        }
    }
    // 连接成环
    tail->next = head;
    queue->size = 0;
    queue->count = k;
    return queue;
}

2.3、入队接口

入队的话，我们这里还是选择让队尾指针rear指向队尾的下一个节点，所以我们这里要向将当前rear指向的节点赋上新的值，然后再让rear往后走一步。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->rear->val = value;
    obj->rear = obj->rear->next;
    obj->size++;
    return true;
}

2.4、出队接口

因为我们是通过给节点的数据域赋上新值，来表示加入新数据的，所以我们这里也并不需要将原来的节点删除，直接让front指针往后走一步即可：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
    obj->front = obj->front->next;
    obj->size--;
    return true;
}

2.5、取队头接口

这个接口其实也没什么好说的，如果队列为空就直接返回-1，不为空就直接返回队头节点的值。

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    return obj->front->val;
}

2.6、取队尾接口

因为我们设计的rear指向的是队尾节点的下一个节点，所以我们其实要返回的是rear的前一个节点。但又因为单链表的局限性，我们不能直接找到rear的前驱。所以我们这个接口其实有两种方案，一种是可以再队列中在增加一个成员rearPre，来记录rear的前一个节点；另一种是在这个接口内直接重头遍历找到rear的前一个。
因为我觉得再定义一个rearPre没有什么必要，因为只有在取队尾的接口中用到，定义了好型显得有点儿多余，所以我这里选择的是第二种方案——直接遍历，这其实就和单链表的遍历一样了：

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    ListNode *cur = obj->front;
    while (cur->next != obj->rear) {
        cur = cur->next;
    }
    return cur->val;
}

2.7、判空接口

我们直接返回size是否等于0的判断结果即可：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size == 0;
}

2.8、判满接口

直接返回size是否等于k的结果即可：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size == obj->count;
}

2.9、释放接口

因为单链表的节点也是动态开辟出来的，所以我们在释放队列之前要先将这些节点也释放了：

void myCircularQueueFree(MyCircularQueue* obj) {
    ListNode *cur = obj->front->next;
    obj->front->next = NULL;
    while (cur) {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(obj);
}