力扣622:设计循环队列
思想:循环利用之前出队列的空间,需要考虑的是如何表示空队列和满队列,若是整个队列放慢,我们就无法分别到底是队列空还是满。如图:
建立多一个空间,如N个,那么最多存储N-1个数据,那么当front(head)指针等于rear(tial)指针时为空,rear(tail)指针的下一位是front(head)指针时候为满队列
代码实现:(数组法)
//数组
typedef struct {
int* arr; //存放数据的数组
int head;
int tail;
int k;//记录数组总长度,但是实际大小要比k大1
} MyCircularQueue;
//循环队列初始化
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* ps = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (ps == NULL)
return NULL;
ps->arr = (int*)malloc((k + 1) * sizeof(int));
ps->head = ps->tail = 0;
ps->k = k;
return ps;
}
//循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (obj->tail == obj->k)
return obj->head == 0;
else
return obj->head == obj->tail + 1;
}
//循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head == obj->tail;
}
//push元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//入队
if (myCircularQueueIsFull(obj))
return false; //队列满了就无法入队了
//没有满直接添加
obj->arr[obj->tail] = value;
if (obj->tail != obj->k)
{
obj->tail++;
}
else
{
obj->tail = 0;
}
return true;
}
//pop元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//出队列
if (myCircularQueueIsEmpty(obj))
return false;
//不是空就出数据
if (obj->head != obj->k)
{
obj->head++;
}
else
obj->head = 0;
return true;
}
//返回队列首元素
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->head];
}
//返回队列尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return -1;
if (obj->tail == 0)
{
return obj->arr[obj->k];
}
else
return obj->arr[obj->tail - 1];
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
obj == NULL;
}
数组循环队列指针一旦到了顶部就需要循环到起始0位置,这样方可达到循环的目的。