[数据结构与算法]循环队列的实现

目录

定义

初始化

入队

出队

获取首尾元素

判断空和满

销毁

做题链接力扣?622. 设计循环队列

队列进行尾插和头删，我们选择链表来实现他

定义

//定义
typedef struct {
	int *a;       //起始地址
	int head;     //头结点的下标
	int tail;     //尾结点的下标
	int k;        //元素个数
} MyCircularQueue;

初始化

开辟空间，由题意知空间是固定的，分析：

我们知道开始时 head与tail相等，则队列为空，但是当队列一直插入，队列插满时，tail更新到第一个，此时tail=head，但队列不为空。? ?这里就要思考怎么样来解决这个误判的问题：

我们可以扩容时多增加一个空间，判断tail的next是否为空，决定队列是否已满。

//初始化
MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->a = (int*)malloc(sizeof(int)*(k + 1));
	obj->head = obj->tail = 0;
	obj->k = k;
	return obj;
}

入队

入队时，先要判断队列是否已经满了，因为判断函数在后面实现，因此在此函数前应先声明判断函数。

因为是循环队列，没满的情况下tail不可能一直++下去，当tail=k时，head之前为空的话，tail须等于0；tail不等于k时，继续++。

bool myCircularQueueIsFull(MyCircularQueue* obj);
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->tail] = value;
	if (obj->tail == obj->k)
	{
		obj->tail = 0;
	}
	else
	{
		obj->tail++;
	}
	return true;
}

出队

先判断是否为空，判断函数在之后实现，因此要先声明。

不为空的情况下，若head=k，那么head应该更新到0的位置，否则head直接++即可，注意题目要求的返回条件。

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return false;
	if (obj->head == obj->k)
	{
		obj->head = 0;
	}
	else
	{
		obj->head++;
	}
	return true;
}

获取首尾元素

首元素就是下标head的位置，记得要先判断是否为空；尾元素稍微复杂一点，先判断，在分析：

因为我们为了避免队列满和空情况混淆，因此开了k+1个空间，当tail=0时，队列的尾元素应该在tail之前，即在k的位置上，其他情况下在tail-1的下标位置上。边界为特殊情况！

//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[obj->head];
}

//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return -1;
	if (obj->tail == 0)
	{
		return obj->a[obj->k];
	}
	else
	{
		return obj->a[obj->tail - 1];
	}
}

判断空和满

空的情况即head=tail则为空；满的情况下考虑边界情况，唐tail在k位置时，head在0位置时，队列存了k个元素，已满。其他情况下，若tail+1的位置=head的位置，即已满。

tail位置不存元素，是个多开辟的空间，尾元素位置不在tail上，在tail的前一个！！！

//判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->head == obj->tail;
}

//判断队列是否存满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	if (obj->tail == obj->k&&obj->head == 0)
	{
		return true;
	}
	else
	{
		return obj->tail + 1 == obj->head;
	}

}

销毁

销毁的话要注意两层销毁，防止出现野指针。

//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
}

?