数据结构 循环队列

无论是普通队列还是循环队列，我们要遵循的标准，或者是规则，就是FIFO，先进先出。

在此基础之上，我们来创造一个循环队列。
首先我们自然要struct一个结构体，也就是我们的队列

typedef struct {
    int *a;
    int k;
    int head;
    int tail;
} MyCircularQueue;
1
2
3
4
5
6

在这个结构体中，指针a指向未来我们所要开辟的数组空间，也就是我们的循环队列。

k则是循环队列的内容大小，简单来说，就是数组的长度。

head和tail就是我们未来开辟数组所构成的循环队列的头下标和尾下标。

理解循环队列，主要是在理解其头尾下标的配合，通过其配合，我们可以控制进出队列。

我们可以看到，在初始化阶段，head和tail都是0，或者说，头尾下标处于同一位置，此时，队列为控，可以入队列。

可是，此时此刻，有一个问题，队列满了如何判断呢？
按照这个逻辑，队列满的时候，head和tail也处于同一位置，那么无法区分开队列是控还是满。

此时，我们引入一个概念，就是在malloc数组的时候，把大小设置为(k+1)，用多余出的一个空间来判断是否队列满了。

如图所示，当K=6时，我们开辟7个空间，当存满六个数据时，此时队列已经满了，但是tail和head并没有重合，head是在tail的下一个位置，我们可以通过这样来，判断循环队列的空或者是满！

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->k=k;
    obj->head=obj->tail=0;
    obj->a=(int*)malloc(sizeof(int)*(k+1));

    return obj;
}
1
2
3
4
5
6
7
8

我们在这里开辟（K+1）个空间用来处理空满问题。

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->head > obj->tail&&obj->tail+1==obj->head)
    return true;
    if(obj->head<obj->tail&&obj->tail-obj->head==obj->k)
    return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

显而易见，通过判断tail和head是否相等来判断队列是否为空，easy；
但是，在判断队列是否为满时，我们要注意，head和tail的位置大小是不确定的，所以我们要分别来判断。

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

这里是入队列代码，我们首先要判满，如果满了就返回假。
队列未满，就开始入队列，直接把tail下标所在的位置赋值为value即可，
然后让tail++。
最后，问题来了，tail++以后，是有可能越界的，虽然我们设计的是一个循环队列，但其本质
还是依赖于数组，在tail越界以后，将其赋值为0，这个逻辑就通顺了。

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

这里是出队列，同理，判断队列是否为空。
队列非空，就可以进行出队列操作。
我们出队列操作实际上，也只是简单的把队列的头往后移一位而已，直接head++即可，
同样的，我们也要注意越界问题，越界后赋值为0即可。

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    if(obj->tail==0)
    return obj->a[obj->k];
    else
    return obj->a[obj->tail-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在这里，front是返回队首元素，rear是返回队尾元素，同样的，我们首先要判空，
front很简单，我们只需要简单返回head下标所处的元素即可，
而rear我们则需要注意一下，tail在每次入队列后要++，那么，我们要返回tail下标之前的一个元素，
tail-1即可，当tail为0的时候，返回数组末端下标元素即可。

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->k=obj->head=obj->tail=0;
    free(obj);
}

1
2
3
4
5
6

最后，简单的free即可。

全部源码如下：

typedef struct {
    int *a;
    int k;
    int head;
    int tail;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);//声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//声明


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->k=k;
    obj->head=obj->tail=0;
    obj->a=(int*)malloc(sizeof(int)*(k+1));

    return obj;
}

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

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

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

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

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->head > obj->tail&&obj->tail+1==obj->head)
    return true;
    if(obj->head<obj->tail&&obj->tail-obj->head==obj->k)
    return true;
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->k=obj->head=obj->tail=0;
    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