数据结构—循环队列

  • 循环队列
  • 设计循环队列
    • 结构体的创建
    • 循环队列的初始化
    • 判空
    • 判满
    • 插入（尾插）
    • 出队列（头删）
    • 取队头元素
    • 取队尾元素
    • 空间的销毁

循环队列

一般在操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

为了能使下标Qrear = Qfront来区别队空还是队满，我们常常认为以下左图为队空，右图为队满的情况。a1到a7为7个有效数据，有效数据k个；左图初始空队列状态，我们认为Qrear=Qfront=0，右图此时满队列的状态，Qrear=7，Qfront=0

设计循环队列

结构体的创建

typedef struct {int*a;//用动态数组实现int front;//头的下标int rear;//尾的下标//所以front和rear的取值都是0~kint k;//队列长度，有效数据长度为k} MyCircularQueue;

循环队列的初始化

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(NULL == obj)//动态开辟结构体指针（销毁空间时也需free）{perror("malloc obj faile\n");return NULL;}obj->front = obj ->rear = 0;//初始队列元素为空，头尾在一起下标都为0obj->a = (int*)malloc(sizeof(int)*(k+1));//动态数组开辟k+1个空间，因为实际队列长度要比有效数据长度多一个空间if(obj->a == NULL){perror("malloc obj->a faile");return NULL;}obj->k= k;//队列有效数据长度return obj;}

判空

因为这是循环队列，在经过不断的插入删除的过程中，rear和front会不断地变换位置，所以判空条件就是判断他俩是否相等而不是他俩是否都为0

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;//若rear和front相等即为空}

判满

判满条件只需要看(rear+1)%(k+1)==front就好了

//判满bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1) % (obj->k+1) == obj->front;}

插入（尾插）

boolmyCircularQueueEnQueue(MyCircularQueue* obj, int value) {//有插入就要判断空间问题，判断队列是否满了if(myCircularQueueIsFull(obj)){return false;//插入失败返回false}obj->a[obj->rear++] = value;obj->rear %= obj->k+1;//rear为下标取值范围为0~k,所以这里限制以下rear的取值范围return true;}

出队列（头删）

删除要判断是否为空队列，空队列不可以删除；头删原理就是，自增front，同样在进行头删的时候，因为front的自增，在动态数组a[k]到a[0]之间的过渡也需要对front取值范围的限制。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除就要判空if(myCircularQueueIsEmpty(obj)){return false;}++obj->front;obj->front %= obj->k+1;return true;}

取队头元素

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;//队列为空返回-1}return obj->a[obj->front];}

取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;//队列为空返回-1}return obj->a[(obj->rear-1+obj->k+1) % (obj->k+1)];}

空间的销毁

//空间的销毁void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a = NULL;//防止野指针形成free(obj);obj = NULL;}