目录

设计循环队列

🙂【1】数组循环队列

思路分析

❓1

❓2

❓3

易错总结

创建MyCircularQueue

初始化myCircularQueueCreate

为空否myCircularQueueIsEmpty

为满否myCircularQueueIsFull

插入元素myCircularQueueEnQueue

删除元素myCircularQueueDeQueue

获取首元素myCircularQueueFront

获取尾元素myCircularQueueRear

释放空间myCircularQueueFree

🆗【1】总代码

🙂【2】链表循环队列 

思路分析

❓

易错总结 

创建MyCircularQueue

初始化myCircularQueueCreate

为空否myCircularQueueIsEmpty

为满否myCircularQueueIsFull

插入元素myCircularQueueEnQueue

删除元素myCircularQueueDeQueue

获取首元素myCircularQueueFront

获取尾元素myCircularQueueRear

释放空间myCircularQueueFree

🆗【2】总代码

---

另外扩展了解一下，实际中我们有时还会使用一种队列叫【循环队列】。如操作系统讲解【生产者消费者模型】时可以就会使用循环队列。环形队列可以使用【数组】实现，也可以使用循环【链表】实现。我们今天来实现一下。

设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

 

🙂【1】数组循环队列

 

这个【数组循环队列】在逻辑上是如上图所示，但是在物理上，不是循环的。所以特别注意：关于数组循环的这个点，我们必须手动控制。 

思路分析

❓1

空和放一个元素怎么区分？

• 方法1：back初始化为0，指向队尾元素的下一个位置。
• 方法2：back初始化为-1，指向队尾元素。 
• 特别提醒！：用方法1比较好控制

 

❓2

空和满怎样去区分（用方法1区分空和一个元素）？

• 方法1：设置size。
• 方法2：malloc多一个空间，不放置元素。（k+1)
• 以上两者方法都可以。

❓3

怎么处理数组物理上不循环（改成逻辑上循环）？

• (back+1)%(k+1) = fron
• obj->back %= obj->k+1
• return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)]

这里是以判空和满的来讲解，其他的插入和取尾元素是同理的！！ 

易错总结

• 临时变量出了函数就销毁了，必须malloc
• A%B（A>B对A来说是没有任何影响，A<=B对A来说模去多余的B）---用来处理数组回绕地方
• 操作符优先级 所以最好都加上括号
• 处理的表达式的左边不能为计算式（❌obj->front+1%=obj->k+1;）
• 判空和满直接下标运算即可，不用用数组（为什么不能用数组❓）
• 释放空间先释放数组空间，在释放myCircularQueue

创建MyCircularQueue

//用数组实现+多开辟一个空间不放元素
typedef struct {int*a;int front;int back;//数组下标int k;//循环队列的最多放置数据
} MyCircularQueue;

初始化myCircularQueueCreate

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int*tmp=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间obj->a=tmp;obj->front=0;obj->back=0;//指向最后一个元素的下一个obj->k=k;return obj;
}

为空否myCircularQueueIsEmpty

//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->back;//==0 
}

为满否myCircularQueueIsFull

//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front//操作符优先级问题
}

插入元素myCircularQueueEnQueue

 考虑下这个特殊情况！

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}obj->a[obj->back] = value;obj->back++;obj->back %= obj->k+1;//处理//obj->front+1%=obj->k+1;//处理左边不能为计算表达式return true;
}

删除元素myCircularQueueDeQueue

  考虑下这个特殊情况！

//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}else{obj->front++;obj->front%=obj->k+1;//处理return true;}
}

获取首元素myCircularQueueFront

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

获取尾元素myCircularQueueRear

  考虑下这个特殊情况！

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

释放空间myCircularQueueFree

//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);obj=NULL;
}

🆗【1】总代码

//用数组实现+多开辟一个空间不放元素
typedef struct {int*a;int front;int back;//数组下标int k;//循环队列的最多放置数据
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int*tmp=(int*)malloc(sizeof(int)*(k+1));//多开辟一个空间obj->a=tmp;obj->front=0;obj->back=0;//指向最后一个元素的下一个obj->k=k;return obj;
}
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->back;//==0 
}//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front//操作符优先级问题
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}obj->a[obj->back] = value;obj->back++;obj->back %= obj->k+1;//处理//obj->front+1%=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;}else//return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];return obj->a[(obj->back+obj->k)%(obj->k+1)];
}//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);obj=NULL;
}

🙂【2】链表循环队列 

链表很简单对于处理循环的问题，只要实现单项循环链表即可。这里的难点就是：（1）创建单项循环链表。（2）找到back的前一个元素

思路分析

关于判【空/一个元素】& 判【空/满】都是和上面数组是一样的。这里不过多阐述。

❓

怎么去找到back的前一个元素？

其实这个问题在我们前面博文实现链表也详细讲解，相信大家可以轻松掌握！！

        Node*prev=obj->front;while(prev->next != obj->back){prev=prev->next;}

易错总结 

• 初始化一定要把back置回开头
• 找back前一个元素：要么用三个指针，要么遍历一遍链表。
• 释放空间不能遍历去释放，会造成野指针。
• 释放空间先把循环链表改变成单向链表，才能循环遍历释放。 

创建MyCircularQueue

typedef struct Node
{int val;struct Node*next;
}Node;//节点typedef struct {Node*front;Node*back;    int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列

初始化myCircularQueueCreate

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->front=NULL;obj->back=NULL;while(k--){Node*newnode=(Node*)malloc(sizeof(Node));if(obj->front == NULL){obj->front=obj->back=newnode;obj->front->val=0;}else{obj->back->next=newnode;obj->back=newnode;obj->back->val=0;}}//循环obj->back->next=obj->front;//backobj->back=obj->front;//obj->size=0;return obj;
}

为空否myCircularQueueIsEmpty

//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->size == 0 && obj->front == obj->back)return true;elsereturn false;
}

为满否myCircularQueueIsFull

//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj->size != 0 && obj->front == obj->back)return true;elsereturn false;
}

插入元素myCircularQueueEnQueue

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}else{obj->back->val=value;obj->back=obj->back->next;obj->size++;return true;}
}

删除元素myCircularQueueDeQueue

//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}else{obj->front=obj->front->next;//❌易错obj->size--;return true;}
}

获取首元素myCircularQueueFront

//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->front->val;
}

获取尾元素myCircularQueueRear

//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}//❌易错else{Node*prev=obj->front;while(prev->next != obj->back){prev=prev->next;}return prev->val;}
}

释放空间myCircularQueueFree

//释放空间
//❌易错
void myCircularQueueFree(MyCircularQueue* obj) {Node*prev=obj->front;while(prev->next != obj->front){prev=prev->next;}//prev是最后一个prev->next=NULL;//while(obj->front->next != NULL){Node*tmp=obj->front;obj->front=obj->front->next;free(tmp);tmp=NULL;}free(obj->front);obj->front=NULL;free(obj);obj=NULL;
}

🆗【2】总代码

typedef struct Node
{int val;struct Node*next;
}Node;//节点typedef struct {Node*front;Node*back;    int size;//计算放入队列的元素个数
} MyCircularQueue;//循环队列MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->front=NULL;obj->back=NULL;while(k--){Node*newnode=(Node*)malloc(sizeof(Node));if(obj->front == NULL){obj->front=obj->back=newnode;obj->front->val=0;}else{obj->back->next=newnode;obj->back=newnode;obj->back->val=0;}}//循环obj->back->next=obj->front;//backobj->back=obj->front;//obj->size=0;return obj;
}//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->size == 0 && obj->front == obj->back)return true;elsereturn false;
}//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj->size != 0 && obj->front == obj->back)return true;elsereturn false;
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//true 满了{return false;}else{obj->back->val=value;obj->back=obj->back->next;obj->size++;return true;}
}//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj)){return false;}else{obj->front=obj->front->next;obj->size--;return true;}
}//获取首元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->front->val;
}//获取尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}else{Node*prev=obj->front;while(prev->next != obj->back){prev=prev->next;}return prev->val;}
}//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {Node*prev=obj->front;while(prev->next != obj->front){prev=prev->next;}//prev是最后一个prev->next=NULL;//while(obj->front->next != NULL){Node*tmp=obj->front;obj->front=obj->front->next;free(tmp);tmp=NULL;}free(obj->front);obj->front=NULL;free(obj);obj=NULL;
}

 还有数据结构的【栈】和操作系统的【栈】是不一样的。数据结构的【栈】是一种线性表。操作系统的【栈】是内存的区域，会发生栈溢出和内存泄露的问题（递归程序/返回条件有问题），但是数据结构【栈】不会。

✔✔✔✔✔最后，感谢大家的阅读，若有错误和不足，欢迎指正！