C语言 设计循环队列_力扣typedef

什么是循环队列

力扣题目要求及链接

数组实现循环链表

链表实现循环链表

什么是循环队列：

队列：是一种先进先出（first in first out,FIFO）的线性表，是一种常用的数据结构。

循环队列：就是将 队列 存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列特点：如果设计一个需要可以存储k个元素的循环队列，一般来说需要开辟k+1个空间，多出的一个空间用于辅助判断循环队列是否"满"或“空”；

循环队列优点：相对于普通队列而言，再频繁删，加入操作下可节省空间。

循环队列概念图（循环队列为空时和不为满时）：

 力扣题目要求及链接：链接

 数组实现循环队列：

 
//数组实现
typedef struct {   // 数组实现时
	int* queue;
	int front; 
	int tail;
	int size;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k);
	
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
 
bool myCircularQueueDeQueue(MyCircularQueue* obj);
 
int myCircularQueueFront(MyCircularQueue* obj);
 
int myCircularQueueRear(MyCircularQueue* obj);
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
 
bool myCircularQueueIsFull(MyCircularQueue* obj);
 
void myCircularQueueFree(MyCircularQueue* obj);
 
MyCircularQueue* myCircularQueueCreate(int k) {
 
	MyCircularQueue* cqueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	cqueue->queue = (int*)malloc(sizeof(int) * (k+1));   //因为cqueue->queue是数组名称本来就是地址，所以可以这样写
	cqueue->front = cqueue->tail = 0;    //tail是下标
	cqueue->size = k;  //代表实际可以存储的元素个数
	return cqueue;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {  //tail指向的是最后一个有效内容后的空结点，如果不存在内容，则front和tail在一个位置
	if (myCircularQueueIsFull(obj))   //判满，为满时不可添加
	{	
		return false;
	}
	obj->queue[obj->tail] = value;
	obj->tail = (obj->tail + 1) % (obj->size+1);
	return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {   //删除的基本逻辑是删除fornt当前所指向的内容后指向下一内容；
	if (myCircularQueueIsEmpty(obj)) //判空，为空不可再删除
	{
		return 0;
	}
	obj->front = (obj->front + 1) % (obj->size + 1);
	return true; 
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1; //题设队列为空时返回-1
	}
	return (obj->queue[obj->front]);
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;//题设队列为空时返回-1
	}
	/*return (obj->queue[obj->tail]);*/
	return obj->queue[(obj->tail + obj->size) % (obj->size + 1)];  //难点，主要是想不到
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return (obj->front == obj->tail) ;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {   //如何判满和空是这结构的难点之一 
	return (obj->tail + 1) % (obj->size + 1) == obj->front;    //难点，主要是想不到
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
	//从里向外释放
	free(obj->queue); //obj->queue 是数组名称也free（）释放
	obj->queue = NULL;
	obj->front = obj->size = obj->tail = 0;
	free(obj);
	/*obj = NULL;*/   
	// 注意这里面即使写上 obj = NULL 也是无效的
	//obj是一个地址（指针），free是释放了指针指向的内容，
	//传参传的obj是实参的拷贝，在函数内部改变obj不对函数外的造成影响
	//所以要想使 obj = null 有效，要使用者在外部输入 obj = null ；
}

 链表实现循环队列：

//链表实现时
typedef struct Node {
    int val;
    struct Node* next;
}Node;  
 
typedef struct {
    Node* head;
    Node* tail;
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k);
	
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value);
 
bool myCircularQueueDeQueue(MyCircularQueue* obj);
 
int myCircularQueueFront(MyCircularQueue* obj);
 
int myCircularQueueRear(MyCircularQueue* obj);
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
 
bool myCircularQueueIsFull(MyCircularQueue* obj);
 
void myCircularQueueFree(MyCircularQueue* obj);
 
 
MyCircularQueue* myCircularQueueCreate(int k) //个人认为链表实现的难点就在于创建
{
	MyCircularQueue* queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	queue->head = (Node*)malloc(sizeof(Node)); //多申请的一个结点
	Node* cur = queue->head;
	while ( k != 0)
	{
		cur->next = (Node*)malloc(sizeof(Node));   //妙啊
		cur = cur->next;   
		k = k - 1;
	}
	cur->next = queue->head;
	queue->tail = queue->head;
	return queue;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	obj->tail->val = value;
	obj->tail = obj->tail->next;
	return true; 
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return false;
	}
	obj->head = obj->head->next;
	return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	return (obj->head->val);
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	Node* cur = obj->head;
	while (cur->next != obj->tail)
	{
		cur = cur->next;
	}
	return cur->val; 
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return(obj->head == obj->tail);
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return (obj->tail->next == obj->head);
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
	while (obj->head != obj->tail)
	{
		Node* cur = obj->head;
		obj->head = obj->head->next;
		free(cur);
		cur = NULL;
	}
	free(obj->head);
	obj->head = NULL;
	free(obj);
}