设计循环队列（详解）

呀哈喽，我是结衣
今天给大家带来的内容如标题所述，我们来设计环形队列，虽然队列没有讲，但是我就是想讲啊。那么环形队列现在开始。

队列的属性

在设计环形队列前，我们先要了解队列的特点（先进先出），就想现实中我们排队一样，先到的人先得。所以现实中银行的取票机是可以用队列实现的。

循环队列

本次讲解是基于leetcode的以题来讲解的，贴张图给大家介绍吧：

看完题目不知道大家有没有思路呢？没有的话就听我详细的解释吧。

顺序表or链表

看完题目你最先想到的实现方法是顺序表还是链表呢？倒不是说这两种方法只能选择一个，而是实现难易程度问题，你觉得用顺序表难还是用链表难呢？这里我选择用顺序表来讲解，我觉得顺序表简单一些呢。

顺序表实现循环队列

在实现之前我们来看看题目要我们实现的功能吧：

typedef struct {
    
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    
}

int myCircularQueueFront(MyCircularQueue* obj) {
    
}

int myCircularQueueRear(MyCircularQueue* obj) {
    
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    
}

void myCircularQueueFree(MyCircularQueue* obj) {
    
}

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

了解完要求下面我们就要分析了。

怎样实现循环

首先我们要定义一个头和尾。（front和back）他们就是下标哈。
有了头和尾。我们要把他们的初始值给多少呢，都给‘0’还是给‘-1’呢，这里我的做法是把头和尾都给‘0’，你可能会说那如果插入了一个数，back怎么办。哼哼，我们把back++，我们让back指向的最后一个数的下一个，而非最后一个数，那么新的问题又来了，当出现这种情况怎么办。

back不就出去了吗，是的，我们要解决这个问题就要多定义一个空间，题目让我们定义k个空间，我们就要定义k+1个空间。但是有一个空间是不存储数据的。

在k+1个空间中始终有一个空间是不存储数据的只有这样才能满足题目要求的k个空间。

这就是循环的示意图，当前面有空间，又要插入数据时，在back的位置上插入数据后再将back = 0。

结构体的创建

typedef struct {
    int* data;
    int front;
    int back;
    int k;
} MyCircularQueue;
1
2
3
4
5
6

相信看完上面的简介这个结构体的创建是没有问题的吧。

函数的实现

这里的函数的实现并不是按照题目顺序来进行的。因为这里的函数也可以相互的调用为后续节省时间。

初始化

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->data = (int*)malloc(sizeof(int) * (k + 1));
    tmp->front = 0;
    tmp->back = 0;
    tmp->k = k;
    return tmp;
}
1
2
3
4
5
6
7
8

我们先要malloc一个结构体的空间，然后再malloc tmp->data这个数组的大小，因为我们有一个空位置所以就开了k+1个的空间。还有头和尾的赋值尾‘0’，在上面的实现循环里有讲解。

队列判空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if (obj->back == obj->front)
    {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7

这个代码就很直观了，back == front就直接判空了。因为我们这里的back是不会有数据的，出现这种情况这样最初的时候在那种情况就是队列为空的情况。

队列判满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if ((obj->back + 1) % (obj->k + 1) == obj->front)
    {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7

我们都知道当back的下一个为front的时候就是满的时候，所以写成back+1 == front是不是就可以了呢？不是不行，多加个判断就可以了，但是为我们要介绍的方法取余的方法，在这种循环中就特别的好用，利用的就是当被除数比除数小的时候余数为被除数。

数据插入

写完判空判满的函数，我们下面就会轻松一些
要插入数据我们首先就是要判断队列有没有满，如果满了就不能插入，并且返回false

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->data[obj->back] = value;
    if (obj->back == obj->k)
        obj->back = 0;
    else
        obj->back++;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

除了判满，我们还要小心当back在最后的情况下，在最后的话如果我们还是back++的话，back就出界了，后果可是很严重的，后面返回为数据的时候就可能会访问野指针。导致程序崩溃。所以我们就要加判断呢。

数据删除

删除数据的时候我们要知道队列不能为空，为空就不能删除，返回false。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    if (obj->front == obj->k)
        obj->front = 0;
    else
        obj->front++;

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

当然后面判断和前面插入的时候相似，front在最后的时候就不能++了，要让他等于0。

返回头

不能为空

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->data[obj->front];
}
1
2
3
4
5
6
7

返回尾

不能为空的同时还要注意，back为0的时候，如果你还 减减 不久变成负数了吗，这样肯定是不行的，所以我们要再加一个判断咯。

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    if (obj->back == 0)
        return obj->data[obj->k];
    else
        return obj->data[obj->back - 1];
}

1
2
3
4
5
6
7
8
9
10
11

销毁

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj);
    obj = NULL;
}
1
2
3
4

销毁就是十分的简单

循环队列代码

typedef struct {
    int* data;
    int front;
    int back;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->data = (int*)malloc(sizeof(int) * (k + 1));
    tmp->front = 0;
    tmp->back = 0;
    tmp->k = k;
    return tmp;
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if ((obj->back + 1) % (obj->k + 1) == obj->front)
    {
        return true;
    }
    return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->data[obj->back] = value;
    if (obj->back == obj->k)
        obj->back = 0;
    else
        obj->back++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    if (obj->front == obj->k)
        obj->front = 0;
    else
        obj->front++;

    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    if (obj->back == 0)
        return obj->data[obj->k];
    else
        return obj->data[obj->back - 1];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj);
    obj = 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

完