【数据结构算法经典题目刨析（c语言）】使用数组实现循环队列（图文详解）
💓 博客主页：C-SDN花园GGbond
⏩ 文章专栏：数据结构经典题目刨析(c语言)
目录
一.题目描述
二.解题思路
1.循环队列的结构定义
2.队列初始化
3.判空
4.判满
5.入队列
6.出队列
7.取队首元素
8.取队尾元素
三.完整代码实现
Circular_Queue.h
Circular_Queue.c
一.题目描述
二.解题思路
1.循环队列的结构定义
包含
- 指向数组的指针，这是循环队列的底层结构
- 指向队首和队尾的整型变量front和rear
- 循环队列的空间大小k
typedef int CQueueDataType;
typedef struct MyCircularQueue//循环队列结构定义
{
CQueueDataType* a;
int front;
int rear;
int k;
} MyCircularQueue;2.队列初始化
动态开辟一块循环队列结构体大小的空间
为数组指针的指向地址分配一块动态申请的内存，大小为k+1个空间，但实际使用k个（不申请k个是为了区别队列空和队列满，保留一个空间）
front和rear初始为0（要注意rear初始为0，意味着指向的是队尾的下一个元素）
k初始化为输入的值
最后返回该队列的地址
MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化
{
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
tmp->a = (CQueueDataType*)malloc(sizeof(CQueueDataType) * (k + 1));
tmp->front = tmp->rear = 0;
tmp->k = k;
return tmp;
}3.判空
- 对形参接收的地址判空
- 然后返回front==rear的结果
bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判空
{
assert(obj);
return obj->front == obj->rear;
}4.判满
- 对形参接收的地址判空
- 队列满的条件理应是rear+1==front，但考虑到队列是一个"环形"的，要考虑值的溢出，所以改为（rear + 1 )% （k +1)==front
bool myCircularQueueIsFull(MyCircularQueue* obj) //判满
{
assert(obj);
return (obj->rear + 1) % (obj->k + 1)==(obj->front);
}5.入队列
- 首先对形参接收的地址判空
- 然后判断队列是否满
- 如果有空间可用的话，在rear指向的位置插入数据
- 调整rear的位置，向后移动注意考虑循环的问题（rear+1）%（k+1），先对rear+1再对数组长度取模
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队列
{
assert(obj);
if (myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear] = value;
obj->rear = (obj->rear + 1) % (obj->k + 1);
return true;
}6.出队列
- 首先对形参接收的地址判空
- 然后判断队列是否为空
- 如果有数据可出的话，直接调整front的位置即可（不过应当考虑循环值溢出的问题）（front+1)%（k+1）
- 先对front+1再对数组长度取模
bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队列
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return false;
obj->front = (obj->front + 1) % (obj->k + 1);
return true;
}7.取队首元素
- 首先对形参接收的地址判空
- 然后判断队列是否为空（空队列无数据可取）
- 然后返回front位置的元素即可
int myCircularQueueFront(MyCircularQueue* obj) //取队首元素
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}8.取队尾元素
- 首先对形参接收的地址判空
- 然后判断队列是否为空（空队列无数据可取）
- 队尾元素是rear位置的前一个元素，考虑到直接-1可能会出错，正确的位置应该是（rear - 1 + k + 1) % (k + 1)，也可以简化成（rear +k ) % (k + 1)
- 返回该位置数据即可
int myCircularQueueRear(MyCircularQueue* obj) //取队尾元素
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}三.完整代码实现
Circular_Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int CQueueDataType;
typedef struct MyCircularQueue//循环队列结构定义
{
CQueueDataType* a;
int front;
int rear;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k); //循环队列初始化
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);//入队列
bool myCircularQueueDeQueue(MyCircularQueue* obj);//出队列
int myCircularQueueFront(MyCircularQueue* obj);//取队首元素
int myCircularQueueRear(MyCircularQueue* obj); //取队尾元素
bool myCircularQueueIsEmpty(MyCircularQueue* obj); //判空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判满
void myCircularQueueFree(MyCircularQueue* obj); //循环队列销毁Circular_Queue.c
#include"Circular_Queue.h"
MyCircularQueue* myCircularQueueCreate(int k) //循环队列初始化
{
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
tmp->a = (CQueueDataType*)malloc(sizeof(CQueueDataType) * (k + 1));
tmp->front = tmp->rear = 0;
tmp->k = k;
return tmp;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //入队列
{
assert(obj);
if (myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear] = value;
obj->rear = (obj->rear + 1) % (obj->k + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) //出队列
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return false;
obj->front = (obj->front + 1) % (obj->k + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) //取队首元素
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) //取队尾元素
{
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判空
{
assert(obj);
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) //判满
{
assert(obj);
return (obj->rear + 1) % (obj->k + 1)==(obj->front);
}
void myCircularQueueFree(MyCircularQueue* obj) //循环队列销毁
{
free(obj->a);
obj->front = obj->rear = 0;
obj->k = 0;
free(obj);
obj = NULL;
}