[刷题]队列

1.设计循环队列（LeetCode: https://leetcode.cn/problems/design-circular-queue）

题目要求：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

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

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

思路1：
（1）MyCircularQueue(k): 可以创建一个长度为k+1的链表，链表末尾指向表头形成闭环。设置一个头指针、尾指针分别指向循环链表表头、表尾节点。
（2）Front: 返回头指针指向的元素数值。
（3）Rear: 返回尾指针指向的元素数值。
（4）enQueue(value): 插入元素通过尾插的方式实现，从链表末尾插入元素。
（5）deQueue(): 删除元素通过头删方式实现，从删除表头元素。
（6）isEmpty(): 当头尾节点指向同一个节点时，循环队列为空。
（7）isFull():当尾指针指向的节点的下一个节点为头指针指向的节点时，循环队列已满。（多创建一个节点就是为了避免在循环队列满时，尾指针会和头指针指向同一个节点。区分循环队列的空和满）

参考简图：
思路2：
（1）MyCircularQueue(k): 可以创建一个长度为k+1的数组，设置头变量和尾变量分别为元素在数组中的开始下标和结束下标（开始下标是循环队列的第一个元素的下标，结束下标为循环队列的最后一个元素下标+1）。
（2）Front: 返回数组的下标为头变量的数值。
（3）Rear: 返回数组的下标为尾变量的数值。
（4）enQueue(value): 插入元素从数组尾变量下标开始。
（5）deQueue(): 删除元素通过将头变量加1
（6）isEmpty(): 当头尾变量数值相同时，循环队列为空。
（7）isFull():当尾变量加1等于头变量时，循环队列已满。

参考简图：
思路1只做框架说明（无代码），思路2的实现细节通过代码注释解说：

//思路2
typedef int Queue;

//声明一个结构体存储循环队列数组、头变量、尾变量、循环队列长度
typedef struct {
    Queue* a;//循环数组
    int front;//头变量
    int back;//尾变量
    int k;//循环队列长度
} MyCircularQueue;//结构体类型为MyCircularQueue
bool myCircularQueueIsFull(MyCircularQueue* obj);//函数声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//函数声明

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建循环队列结构体
    q->a = (Queue*)malloc(sizeof(Queue)*(k+1));//创建循环队列数组，长度为k+1
    q->front = 0;//循环队列数组头变量置为0，意味着从0下标开始
    q->back = 0;//循环队列数组尾变量置为0，意味着从0下标开始
    q->k = k;//循环队列长度为k
    return q;//返回创建指向循环队列结构体的指针
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//当循环队列满时
    {
        return false;//不能插入元素，返回失败
    }
    obj->back %= (obj->k + 1);
    //尾变量在最后一个元素的后一个空间中，当元素存到数组末尾，尾变量会越出数组下标范围。
    //需要将其挪到循环队列数组的开头，实现循环。
    //通过对尾变量余上循环队列数组长度（k+1），实现尾变量到数组开头（从0开始）
    obj->a[obj->back] = value;//将元素放入循环队列数组下标为尾变量的空间中
    obj->back++;//尾变量向后挪一位
    return true;//插入成功
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//当循环队列数组为空时
    {
        return false;//无法删除元素，返回失败
    }
    obj->front = (obj->front + 1) % (obj->k + 1);
    //将头变量加1，循环队列数组开始位置向后移一位，实现循环队列元素删除的效果
    //由于数组长度有限，当头变量超出数组下标范围时，需要将其挪到数组开头，实现闭环。
    //通过对头变量余上循环队列数组长度（k+1），实现头变量到数组开头
    return true;//删除成功
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))//当循环队列数组为空
    {
        return -1;//没有队首元素可以返回，题目要求返回-1
    }
    return obj->a[obj->front];//返回数组下标为头变量的元素，就是队首元素
}

int myCircularQueueRear(MyCircularQueue* obj) {
    while(myCircularQueueIsEmpty(obj))//当循环队列数组为空
    {
        return -1;//没有队尾元素可以返回，题目要求返回-1
    }
    int back = (obj->back + obj->k) % (obj->k + 1);
	//尾变量减1才能得到队尾元素，当尾变量为0时，减1会超出数组下标范围
	//所以需要加上数组长度再取余
    return obj->a[back];//返回数组下标为尾变量减1的元素，就是队尾元素
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return (obj->front == obj->back);//头变量和尾变量相等，为空，返回真。否则返回假。
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->front == (obj->back + 1) % (obj->k + 1));
    //尾变量减1和头变量相等时，为满，返回真。否则返回假。
    //由于尾变量可能为0，减1无法找到队尾元素。需要加上数组长度再取余
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);//先释放循环队列数组的空间
    obj->a = NULL;//将指向循环队列数组的指针置为NULL
    free(obj);//释放循环队列结构体的空间
    obj = NULL;//将指向循环队列结构体的指针置为NULL
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84