Leetcode刷题之设计循环队列（C语言版）_环形队列 leetcode

622、设计循环队列

一、题目描述

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

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

二、题目示例

三、题目解析

首先本题我们可以采用两种方法解决，分别是数组和链表。在此，我采用数组的方法为大家解决本道题。大家觉得，上图的环形队列，最多可以存放几个数据呢？我想答案应该是7个or8个。我们从下图不难发现判断循环队列是否为空，我们就可以看front和rear是否相等。

但是当我们存放8个数据的时候，结果表示如下图所示：

此时的front和rear也相等，所以无法判断此时的循环队列是为满还是为空的状态。当然我们也可以定义一个size来记录此时的循环队列所存放的数据个数。但是我认为我们可以设定存放7个数据时，循环队列已达到为满的状态。结果如下：

此时我们可以用rear+1=front来判断循环队列是否达到存满的状态。接下来我们便正式开始本题目的讲解：

Ⅰ、typedef struct

首先在匿名结构体中需要定义4个成员变量，分别是front,rear,*a和k。

typedef struct 
{
    int front;//前面的
    int rear;//后面的
    int k;//存放数据的个数
    int *a;//数组
} MyCircularQueue;

1
2
3
4
5
6
7
8

Ⅱ、MyCircularQueue* myCircularQueueCreate(int k)

这个接口主要是对于刚才的结构体进行初始化，首先利用malloc函数对obj开辟一定的空间。对obj开辟好空间之后，我们就可以对obj中的对象进行一定的初始化。这里需要注意的是我们为数组a开辟的空间是K+1个，因为我们需要利用rear+1=front来判断循环队列是否达到存满的状态。初始化的代码如下：

MyCircularQueue* myCircularQueueCreate(int k) //初始化及开辟空间
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a= (int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;   
}
1
2
3
4
5
6
7
8

Ⅲ、bool myCircularQueueIsEmpty(MyCircularQueue* obj)

该接口的目的是判断循环队列是否处于空的状态，前文提到我们可以利用front是否等于rear来判断循环队列是否为空。代码如下：

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

1
2
3
4
5

Ⅳ、bool myCircularQueueIsFull(MyCircularQueue* obj)

前文提到我们可以用rear+1是否等于front来判断循环队列是否处于满的状态。但是这种方法也有一种弊端，那就是：
当rear+1等于6时，会产生数组越界问题，所以我们可以采用取余的方法来避免这一问题，(rear+1)%(k+1)==front来判断数组是否存储数据已满。

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear+1)%(obj->k+1)==obj->front;
}
1
2
3
4

Ⅴ、bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)

向循环队列插入一个元素。如果成功插入则返回真。，这个接口首先要想到的是如果队列已经满了，则不能继续插入，所以先判断是否已满，如果满了就返回false。
接下来便是插入元素，这里需要注意的是我们需要依旧采用取余数的方法让队列循环起来，即：rear = rear % (k + 1)。

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

Ⅵ、bool myCircularQueueDeQueue(MyCircularQueue* obj)

从循环队列中删除一个元素。如果成功删除则返回真。这个接口首先要想到的是如果队列为空了，则不能继续删除，所以先判断是否为空，如果为空就返回false。接下来就是删除操作，删除操作很简单，就是让==front++==即可，但是需要注意的是应当取余数避免越界：front = front % (k + 1)。

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
}
1
2
3
4
5
6
7
8
9
10

Ⅶ、int myCircularQueueFront(MyCircularQueue* obj)

从队首获取元素。如果队列为空，返回 -1 。这个接口比较简单容易实现

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

Ⅷ、int myCircularQueueRear(MyCircularQueue* obj)

获取队尾元素。如果队列为空，返回 -1 。这里需要注意的是，当处在下图所示的情况时，如果强行获取rear的前一个位置可能会产生数组越界问题。所以我们需要采用取余数的方式来解决：rear+k%=(k+1)

int myCircularQueueRear(MyCircularQueue* obj)
{
     if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }    
    return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
1
2
3
4
5
6
7
8

Ⅸ、void myCircularQueueFree(MyCircularQueue* obj)

free需要注意的是首先要释放数组申请的内存空间，其次才是obj申请的内存空间。

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}
1
2
3
4

四、完整代码：

typedef struct 
{
    int front;
    int rear;
    int k;//存放数据的个数
    int *a;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) //初始化及开辟空间
{
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a= (int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;   
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
 {
    return obj->front==obj->rear;
    
}

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

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

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

int myCircularQueueRear(MyCircularQueue* obj)
{
     if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }    
    return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(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
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
85
86
87
88
89
90
91
92