设计循环队列

设计循环队列

下面是队列提供的接口函数

typedef struct {int* a;int k;int front;int rear;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(Queue==NULL){perror("malloc fail");return NULL;}Queue->a = malloc(sizeof(int)*(k+1));Queue->k=k;Queue->front = Queue->rear=0;return Queue;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj->front++;obj->front%=(obj->k+1);}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}

一、循环队列的构建

这里我们用数组构建循环队列，因为如果用链表的话需要前后衔接，用双向循环列表，比较麻烦，用数组的话不需要衔接，因为数组是连续的。
然后就是用循环队列里面需要设置front和rear两个整数来判断这个循环队列是否为空或者是否满了
这里的rear必须是指向尾元素的下一个位置

因为这样容易判断队列是否为空，如果不指向下一个元素那么有一个元素的情况下rear和front的值相同，没有元素的情况下rear与front的值还是相同。

typedef struct {int* a;int k;int front;int rear;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(Queue==NULL){perror("malloc fail");return NULL;}Queue->a = malloc(sizeof(int)*(k+1));Queue->k=k;Queue->front = Queue->rear=0;return Queue;
}

二、判断是否为空

1.没有元素的情况下

2.有元素的情况下

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}

三、判断队列是否满了

1.第一种情况

rear+1 = front

2.第二种情况

这里的rear需要除以一个周期，因为我们开辟了k+1个空间，所以这里的rear对应的值为k，所以需要+1除以一个周期k+1才能回到最开始的位置
即：(rear+1)%(k+1)==front

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

四、队列插入

需要判断这个队列是否满了
然后还有个细节的地方，如下图

此时的rear需要回到第一个位置，不然后面继续插入数据，数组出现越界访问

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);}return true;
}

五、队列的删除

基本上与上面的原理差不多

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj->front++;obj->front%=(obj->k+1);}return true;
}

六、队列取头尾

取头很简单，重要的是取尾
取尾我们知道rear-1就是尾，但是我们忽略了一种特殊情况

这种情况下rear-1为负数，所以我们需要回正，再者考虑其他正常情况，我们需要加上队列的一个周期k+1然后%（k+1）

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}