Leetcode622.设计循环队列

本专栏内容为：leetcode刷题专栏，记录了leetcode热门题目以及重难点题目的详细记录

💓博主csdn个人主页：小小unicorn
⏩专栏分类：Leetcode
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目描述

题目来源：Leetcode622.设计循环队列

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

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

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

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

解题思路：

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
 注意：环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满。

我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：

可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：
 1.当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
 2.当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。
这样就使得该数组在逻辑上是“环形”的了。

代码解决：

typedef struct 
{
    int* a;//数组模拟环形队列
    int k;//队列可存储的有效数据总数
    int front;//队头
    int tail;//队尾的后一个位置
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列
    obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间
    //初始时，队头和队尾均为0
    obj->front = 0;
    obj->tail = 0;
    obj->k = k;//设置队列可存储的有效数据个数
    
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    int tailNext = obj->tail+1;
    if(tailNext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环
    {
        tailNext = 0;
    }
    return tailNext == obj->front;//当tail+1指向的位置与front相同时，队列满
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据
    {
        return false;
    }
    else//插入数据
    {
        obj->a[obj->tail] = value;
        obj->tail++;

        if(obj->tail == obj->k+1)//使队列循环
            obj->tail = 0;

        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据
    {
        return false;
    }
    else//删除数据
    {
        obj->front++;

        if(obj->front == obj->k+1)//使队列循环
            obj->front = 0;
        
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据可返回
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front];//返回队头指向的数据
    }
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据返回
    {
        return -1;
    }
    else//返回tail-1指向位置的数据
    {
        int tailPrev = obj->tail-1;

        if(tailPrev == -1)//使队列循环
            tailPrev = obj->k;
        
        return obj->a[tailPrev];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);//先释放动态开辟的数组
    free(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
93
94
95
96
97
98
99
100
101
102
103
104
105

结果与总结：

通过所有示例，问题得到解决。