【数据结构】循环队列的实现

---

---

前言

(来源）

建议基本掌握普通队列的操作及实现再看本文章

---

一、循环队列

循环队列是基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环
正常我们平时实现的普通队列，大部分是以链表的方式存储，循环队列当然也可以，
但是循环队列使用顺序表的方式较普遍。

原因是无论是链表还是顺序表实现，都要考虑它的三种状态

• 空队列
• 有元素但未满的队列
• 满队列

而这时候，顺序表的判断操作比起链表要简单，故普遍使用顺序表来实现循环队列

二、实现循环队列

1.思路分析

用两个下标来标识

1. front–>头
2. rear–>尾

初始状态的时候，front和rear都指向开始的位置，
队列满的时候在这个没有多开一个空间的队列中，满了之后也会两个下标指向同一个位置，
这时候就无法区分front==rear是空队列还是满队列

考虑到要区分这两个状态，我们可以多开一个空间，使得rear+1==front就为满队列，原来的rear==front就为空队列

循环队列的动图

注意：上面动画中的n是队列的总长度，也就是它把多开的那个一个空间也算进去了，
我下面的N表示的是循环队列的有效长度，也就是没把多开的一个空间算进去，
N+1=上面动画的n

那么循环队列的三个状态中最主要的两个已经解决了，循环队列的实现也就基本可以实现了

下面就是在代码中如何实现上面的思路

2.代码中的循环队列

---

下面代码可以直接复制到LeetCode运行–>✨题目地址

typedef struct {
    int *a;//顺序表地址
    int Front;//头下标
    int rear;
    int N;
} MyCircularQueue;

//MyCircularQueue(k): 构造器，设置队列长度为 k 。
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->Front=obj->rear=0;
    obj->N=k+1;
    return obj;
}

//isEmpty(): 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

    return obj->Front==obj->rear;
}

//isFull(): 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->Front==(obj->rear+1)%obj->N;
}

//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;

    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear%=obj->N;
    return true;
}

//deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
         return false;
    obj->Front++;
    obj->Front%=obj->N;
    return true;
}

//Front: 从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->Front];
}


//Rear: 获取队尾元素。如果队列为空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
        return -1;
        return obj->a[(obj->rear-1+obj->N)%obj->N];
}



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

---

总结

---

以上就是今天要讲的内容，本文仅仅简单介绍了循环队列的实现，而更多的操作实现细节还需要各位自行实现才能知道