仿威客网站android优化大师

💓 博客主页：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;
}