【数据结构】如何设计循环队列？图文解析（LeetCode）

LeetCode链接：622. 设计循环队列 - 力扣（LeetCode）

目录

做题思路

只开辟 k 个空间

多开一个空间

代码实现

1. 循环队列的结构

2. 开辟空间

3. 判断空

4. 判断满

5. 队尾插入数据

6. 队头删除数据

7. 获取队头元素

8. 获取队尾元素

9. 销毁队列

全部代码

---

做题思路

• 设计循环队列，使用数组或链表都可以，各有优劣
• 本文使用数组实现
• 本文使用C语言实现

假设队列长度 k = 4

多开一块空间（开辟 k+1 块空间）可以方便区分空和满

为什么？

举个栗子：

只开辟 k 个空间

如果只开辟 k 个空间（假设 k = 4）：

• front（队头）
• rear（队尾）
• front 和 rear 初始都为 0

如果插入一个数据呢？

front 不变，rear 向后移动，如下图：

理想的判断空条件：

• 队头 == 队尾，队列为空
• 队头 != 队尾，队列非空

目前看来似乎可以正常判断队列是否为空

那如果队列满了呢？

如上图所示，队列满了

rear 又回到了 front 的位置

现在怎么判断满呢？

rear == front 吗？

似乎和前面判断空冲突了

想判断必须要特殊处理：比如加一个变量 size 来记录队列中元素的个数

这种方法虽然可以，但是会让代码显得很臃肿，于是我选择了另一种方法：

多开一个空间

如果多开了一个空间（开辟 k+1 个空间）：

• 这里多开的空间是不存放数据的
• 这块空间存在的意义就是为了方便区分空和满

下面我将演示一下如何判断：

判断空：

• 队头 == 队尾，队列为空
• 队头 != 队尾，队列非空

判断满：

• 队尾的下一个 == 队头，队列已满
• 队尾的下一个 != 队头，队列未满

如下图：

那么好，这里简单介绍了一下我的实现思路：

• 使用C语言实现
• 使用数组实现
• 数组多开一块空间

接下来就是详细的实现方法

---

代码实现

本题要求：

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

1. 循环队列的结构

//循环队列的结构
typedef struct
{
    int* a;     //一个数组
    int front;  //存放队头的下标
    int rear;   //存放队尾的下标
    int k;      //队列长度
} MyCircularQueue;

2. 开辟空间

//开辟空间并初始化
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个方便区分空和满
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

3. 判断空

前面说过了，队头等于队尾时，队列为空

//检测循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->rear;
}

4. 判断满

注意这里有一些坑点

前面说过：队尾+1等于队头时，队列为满

但是我用的是数组，不是链表，队尾+1有可能会越界

如上图：rear+1 = 5，越界了

怎么办呢？可以采用取余数（%）的方法，即：（rear+1）%（k+1），让 rear+1 变回 0，达到循环的效果。

情况1：队尾+1越界了

(rear + 1) % (k + 1) = 0

front = 0

(rear + 1) % (k + 1) = front，说明循环队列已满。

情况2：队尾+1没越界

(rear + 1) % (k + 1) = 4

front = 0

(rear + 1) % (k + 1) != front，说明循环队列未满。

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

5. 队尾插入数据

这里需要一些操作，还是越界的问题，插入数据后队尾可能会越界，如下图：

在 rear 处插入数据后，rear 需要向后移动，导致越界

1）判断队列是否已满，满了是不能插入的，直接返回 false

2）在队尾插入数据

3）队尾++，可能会越界

4）依旧采用取余数的方法让队列循环起来，即：rear = rear % (k + 1)

//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k + 1);
    return true;
}

6. 队头删除数据

删除数据后，队头也可能会有越界的情况，如下图：

删除 front 处的数据后，front 需要向后移动，导致越界

1）判断队列是否为空，空队列是不能删数据的，直接返回 false

2）删除数据很简单，直接让队头++即可

3）取余数避免越界：front = front % (k + 1)

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

7. 获取队头元素

情况1：队列为空

根据题意，返回 -1

情况2：队列不为空

直接返回数组中下标为 front 的元素即可

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

8. 获取队尾元素

情况1：队列为空

根据题意，返回 -1

情况2：队列不为空

• 需要返回数组中下标 rear 的前一个元素（rear-1）
• 此操作可能会导致越界
• 用取余数的方式避免越界：(rear + k) % (k + 1)

如上图：这种情况下强行获取 rear 的前一个元素会导致越界

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

9. 销毁队列

销毁所有动态开辟的空间

//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

---

全部代码

//循环队列的结构
typedef struct
{
    int* a;     //一个数组
    int front;  //存放队头的下标
    int rear;   //存放队尾的下标
    int k;      //队列长度
} MyCircularQueue;
 
//开辟空间并初始化
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个方便区分空和满
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}
 
//检测循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->rear;
}
 
//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
 
//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k + 1);
    return true;
}
 
//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= (obj->k + 1);
    return true;
}
 
//从队首获取元素。如果队列为空，返回-1
int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}
 
//获取队尾元素。如果队列为空，返回-1
int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
 
//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

---

本文完