一、概念
普通队列若采用数组实现，随着出队入队操作的进行，队头队尾指针的移动，队头指针走到数组0号位置之后，因为队列只能在队尾插入，那么队头前面的空间就无法再次使用，导致假溢出问题。因此提出了循环队列，其思想是队头或队尾指针到达空间最后一个位置后，下一步移动又会重新返回到初始位置，图示如下：
循环队列为空：队头队尾指针都在初始位置。
满循环队列：为了能使用Q.rear=Q.front来区别是队空还是队满，我们常常认为上图情况时为队满，此时rear+1=front。
注：图示只是为了便于对循环队列的理解，真实的队列还是依靠数组或者链表实现的，内存不会发生弯曲形成头尾相连的情况，而是对指针的操作，实现超过最大位置时就自动返回到初始位置形成循环。
实现方法：每次对队头队尾指针进行改变时，都要对最大容量size进行%取余。若有减法操作，还需先加上最大容量size再对size进行取余，防止数组越界。
二、结构体定义
//循环队列 typedef int QDataType; typedef struct { QDataType* array; int front;//队头 int rear;//队尾 int size;//容量 } MyCircularQueue;
三、接口实现
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判空,空返回true，非空返回false bool myCircularQueueIsFull(MyCircularQueue* obj);//判满,满返回true，非满返回false MyCircularQueue* myCircularQueueCreate(int k);//初始化队列 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);//入队 bool myCircularQueueDeQueue(MyCircularQueue* obj);//出队 int myCircularQueueFront(MyCircularQueue* obj);//获取队头元素 int myCircularQueueRear(MyCircularQueue* obj);//获取队尾元素 void myCircularQueueFree(MyCircularQueue* obj);//销毁
1.循环队列初始化
MyCircularQueue* myCircularQueueCreate(int k) {//初始化队列 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { return NULL; } obj->array = (QDataType*)malloc(sizeof(QDataType) * (k + 1));//申请k+1一个空间 obj->front = 0; obj->rear = 0; obj->size = k + 1; return obj; }
2.循环队列入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//入队 if (myCircularQueueIsFull(obj)) { return false; } obj->array[obj->rear] = value; obj->rear = (obj->rear + 1) % obj->size; return true; }
3.循环队列出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//出队 if (myCircularQueueIsEmpty(obj)) { return false; } obj->front = (obj->front + 1) % obj->size; return true; }
4.获取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {//获取队头元素 if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->array[obj->front]; }
5.获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//获取队尾元素 if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->array[(obj->rear - 1+obj->size) % obj->size]; }
6.循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判空 if (obj->front == obj->rear) { return true; } return false; }
7.循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {//判满 if ((obj->rear + 1) % obj->size == obj->front) { return true; } return false; }
8.循环队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {//销毁 free(obj->array); free(obj); }
四、接口测试
1.测试函数
void Test_Queue() { MyCircularQueue* obj = myCircularQueueCreate(3); myCircularQueueEnQueue(obj, 1); myCircularQueueEnQueue(obj, 2); myCircularQueueEnQueue(obj, 3); myCircularQueueEnQueue(obj, 4);//队满 printf("front=%d\n", myCircularQueueFront(obj));//获取队头1 printf("rear=%d\n", myCircularQueueRear(obj));//获取队尾3 myCircularQueueDeQueue(obj);//出队1 printf("front=%d\n", myCircularQueueFront(obj));//获取队头2 myCircularQueueFree(obj);//销毁 }
2.测试结果
五、完整代码
#include<stdio.h> #include<malloc.h> #include<stdbool.h> //循环队列 typedef int QDataType; typedef struct { QDataType* array; int front;//队头 int rear;//队尾 int size;//容量 } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判空,空返回true，非空返回false bool myCircularQueueIsFull(MyCircularQueue* obj);//判满,满返回true，非满返回false MyCircularQueue* myCircularQueueCreate(int k) {//初始化队列 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if (obj == NULL) { return NULL; } obj->array = (QDataType*)malloc(sizeof(QDataType) * (k + 1));//申请k+1一个空间 obj->front = 0; obj->rear = 0; obj->size = k + 1; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//入队 if (myCircularQueueIsFull(obj)) { return false; } obj->array[obj->rear] = value; obj->rear = (obj->rear + 1) % obj->size; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) {//出队 if (myCircularQueueIsEmpty(obj)) { return false; } obj->front = (obj->front + 1) % obj->size; return true; } int myCircularQueueFront(MyCircularQueue* obj) {//获取队头元素 if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->array[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) {//获取队尾元素 if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->array[(obj->rear - 1+obj->size) % obj->size]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判空 if (obj->front == obj->rear) { return true; } return false; } bool myCircularQueueIsFull(MyCircularQueue* obj) {//判满 if ((obj->rear + 1) % obj->size == obj->front) { return true; } return false; } void myCircularQueueFree(MyCircularQueue* obj) {//销毁 free(obj->array); free(obj); } void Test_Queue() { MyCircularQueue* obj = myCircularQueueCreate(3); myCircularQueueEnQueue(obj, 1); myCircularQueueEnQueue(obj, 2); myCircularQueueEnQueue(obj, 3); myCircularQueueEnQueue(obj, 4);//队满 printf("front=%d\n", myCircularQueueFront(obj));//获取队头1 printf("rear=%d\n", myCircularQueueRear(obj));//获取队尾3 myCircularQueueDeQueue(obj);//出队1 printf("front=%d\n", myCircularQueueFront(obj));//获取队头2 myCircularQueueFree(obj);//销毁 } int main() { Test_Queue(); return 0; }
