循环队列详解

1. 循环队列

1.1 概念及结构

循环队列是一种特殊类型的队列数据结构，也被称为”唤醒缓冲器“。它在数组的基础上实现了循环利用空间的功能。在循环队列中，队尾和队头之间形成了一个循环，当队尾指针“追上”队头指针时，队列不再继续增长，而是继续利用之前出队的空间。

循环队列通常由两个指针来辅助构建：

1. 队尾指针(rear)：指向队尾元素的下一个位置，也就是即将插入新元素的位置。
2. 队头指针(front)：指向队头元素的位置。

入队和出队：

• 入队操作会将元素插入到队尾指针所指向的位置，并将队尾指针后移。当队列满时，入队操作会失败。

• 出队操作会**删除队头元素，并将队头指针后移。**当队列为空时，出队操作会失败。

队空和队满的条件：

• 当队列为空时，front指针和rear指针同时指向下标为0的位置，因此循环队列为空的条件为front == rear
• 需要清楚，由于循环队列需要预留一个空间来区分队列为空和队列满的状态，队列满的条件为rear + 1 == head

为什么需要预留一个空间？

假设我们不预留空间，要对下面的队列插入元素‘7’

那么插入后，front（head）和rear（tail）两个指针的关系就变成了这样：

可以看到，front和rear又相等了，这不就和队列为空的条件混到一起了吗。所以说要多预留一个空间用来判断队列满的情况：

1.2 结构的定义

这里我们用数组来模拟实现循环队列

typedef struct {
    int *data;	//动态数组
    int front;	//队头指针
    int rear;	//队尾指针
    int capacity;	//最大容量
} MyCircularQueue
1
2
3
4
5
6

1.3 基本功能实现

1.3.1 初始化(返回一个循环队列指针)

MyCircularQueue* myCircularQueueCreate(int k);
1

• k为循环队列的最大容量
• 该函数用来返回一个已经初始化好的循环队列指针

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* CQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
    CQueue->data = (int*)malloc(sizeof(int) * (k + 1));	//申请k+1个空间
    CQueue->front = 0;
    CQueue->rear = 0;
    CQueue->capacity = k;

    return CQueue;
}
1
2
3
4
5
6
7
8
9
10

1.3.2 判空

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

1.3.3 判满

可不要简单的以为循环队列满的条件就是rear + 1 == front，我们要考虑下面两种情况（假设最大容量为4）：

情况一：

情况二：

上面两种情况队列都是满的，显然我们不能简单的用front == rear + 1来判断队列是否已满。

直接下结论：我们可以用表达式(rear + 1) % (capacity + 1) == front来判断队列是否已满

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

1.3.4 入队

入队移动的是队尾指着，同样也要考虑两种情况：

情况一：

情况二：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))	//如果已满，插入失败
        return false;

    //如果队尾指针在队列尾部，那么插入过后，队尾指针移到最前面
    if (obj->rear == obj->capacity)
    {
        obj->data[obj->rear] = value;
        obj->rear = 0;
    }
    //否则队尾指针加以即可
    else
    {
        obj->data[obj->rear] = value;
        obj->rear++;
    }

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3.5 出队

出队移动的是队头指针，考虑两种情况：

情况一：

情况二：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))	//如果队列为空，则出队失败
        return false;

    //如果队头指针位于队列最后一个位置，那么删除后就要回到最前面
    if (obj->front == obj->capacity)
        obj->front = 0;
    //否则队头指针往后移即可
    else    
        obj->front++;

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3.5 返回队头元素

由于队头指针指向的就是队头元素，因此直接返回下标位置的元素即可

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))	//队列为空，返回-1
        return -1;

    return obj->data[obj->front];
}
1
2
3
4
5
6

1.3.6 返回队尾元素

由于队尾指针指向的是队尾元素的下一个位置，因此要考虑两种情况：

情况一：

情况二：

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))	//队列为空，返回-1
        return -1;

    //如果队尾指针在下标为0的位置，就说明队尾元素位于数组最后的位置
    if (obj->rear == 0)
        return obj->data[obj->capacity];
    //否则，队尾元素就是队尾指针下标-1的位置
    else
        return obj->data[obj->rear - 1];
}
1
2
3
4
5
6
7
8
9
10
11

1.3.7 销毁队列

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->data);	//销毁数组
    free(obj);	//销毁队列
}
1
2
3
4

1.4 练习

学习完循环队列的相关知识，可以做这一题来加深印象