设计循环队列

设计循环队列

下面是队列提供的接口函数

typedef struct {
    int* a;
    int k;
    int front;
    int rear;
} MyCircularQueue;




MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if(Queue==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    Queue->a = malloc(sizeof(int)*(k+1));
    Queue->k=k;
    Queue->front = Queue->rear=0;
    return Queue;
}

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

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

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

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    else
    {
        obj->front++;
        obj->front%=(obj->k+1);
    }
    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
    return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}


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

一、循环队列的构建

这里我们用数组构建循环队列，因为如果用链表的话需要前后衔接，用双向循环列表，比较麻烦，用数组的话不需要衔接，因为数组是连续的。
然后就是用循环队列里面需要设置front和rear两个整数来判断这个循环队列是否为空或者是否满了
这里的rear必须是指向尾元素的下一个位置

因为这样容易判断队列是否为空，如果不指向下一个元素那么有一个元素的情况下rear和front的值相同，没有元素的情况下rear与front的值还是相同。

typedef struct {
    int* a;
    int k;
    int front;
    int rear;
} MyCircularQueue;




MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if(Queue==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    Queue->a = malloc(sizeof(int)*(k+1));
    Queue->k=k;
    Queue->front = Queue->rear=0;
    return Queue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、判断是否为空

1.没有元素的情况下

2.有元素的情况下

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

三、判断队列是否满了

1.第一种情况

rear+1 = front

2.第二种情况

这里的rear需要除以一个周期，因为我们开辟了k+1个空间，所以这里的rear对应的值为k，所以需要+1除以一个周期k+1才能回到最开始的位置
即：(rear+1)%(k+1)==front

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

1
2
3
4

四、队列插入

需要判断这个队列是否满了
然后还有个细节的地方，如下图

此时的rear需要回到第一个位置，不然后面继续插入数据，数组出现越界访问

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    return false;
    else
    {
        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) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    else
    {
        obj->front++;
        obj->front%=(obj->k+1);
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10

六、队列取头尾

取头很简单，重要的是取尾
取尾我们知道rear-1就是尾，但是我们忽略了一种特殊情况

这种情况下rear-1为负数，所以我们需要回正，再者考虑其他正常情况，我们需要加上队列的一个周期k+1然后%（k+1）

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
    return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}
1
2
3
4
5
6
7
8
9
10
11
12
13