用链表实现循环队列
大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助!如果有错误请大佬们指正!共同学习交流
作者简介:
CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
掘金LV3用户 https://juejin.cn/user/1381426159953960
阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage
题目
循环队列
- 1.符合先进先出
- 2.空间大小是固定的,一开始就要开辟好空间,空间重复利用
- 若用链表实现,出数据不用释放空间
为了方便插入和删除:
定义两个变量:记为front和tail
入数据:tail往后走
出数据:front往后走
当tail/front走到最后一个位置还要往后走:回到第一个位置(循环)
分析:
存k个数据,只开辟k个空间的话
- 数组实现
判空和判满产生歧义!
- 链表实现
判空和判满产生歧义!
==解决办法:要存放k个数据,就开辟k+1个空间,否则无法实现判空和判满==
- 数组
判空 :front == tail
判满: (tail + 1)%( k + 1) == front
- 链表
判空: front == tail
判满: tail->next == front
队列结构
MyCircularQueue(k)
: 构造器,设置队列长度为 k 。
//链表的结点类型
typedef struct Node
{
struct Node* next;//指向下一个结点
int data;//存放数据
}ListNode;
typedef struct
{
ListNode* front;//标志链表的头
ListNode* tail;//标志链表的尾
int k; //存放多少个数据
} MyCircularQueue
创建队列
MyCircularQueue(k)
: 构造器,设置队列长度为 k
构建循环链表 ,存k个数,开辟k+1个空间
-
先开辟一个结点,然后用循环创建k个空间,尾插链接
-
while(k--)//执行k次 while(--k);//执行k-1次
-
注意:创建好之后,并不是循环链表!还要把尾和头链接起来
-
让队列结构体的tail和front指针指向链表的头结点(存放数据tail往后走,删除数据head往后走)
MyCircularQueue* myCircularQueueCreate(int k)
{
//动态开辟队列结构体
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//开辟k+1个空间的链表
//先开辟一个空间
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail = head;//方便链接
//开辟k个空间
while(k--)
{
//尾插
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
tail->next = newnode; //链接
tail = newnode; //新结点成为尾
}
//最后让tail和head进行链接,构成循环
tail->next = head;
//队列结构体的头指针和尾指针指向链表的头
tmp->front = head;
tmp->tail = head;//tail也是指向链表的头,后面要进数据,往后走
//把创建好的环形链表的队列返回
return tmp;
}
插入元素
enQueue(value)
: 向循环队列插入一个元素。如果成功插入则返回真。
- 插入数据,先判断队列是否为满
- 插入到尾指针指向的结点,然后尾指针向后移动
- ==tail标志的是队尾结点的下一个结点==
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
//插入:要保证队列没有满
if(myCircularQueueIsFull(obj))
{
return false;
}
//插入到tail指向的结点,然后tail往后走
obj->tail ->data = value;
obj->tail = obj->tail ->next;
//成功插入则返回真
return true;
}
删除元素
deQueue()
: 从循环队列中删除一个元素。如果成功删除则返回真。
- 删除数据,要保证队列不为空
- 删除数据:tail不动,front往后走
- 删除数据,并不释放空间,空间重复利用
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//删除数据-要保证队列不为空
if(myCircularQueueIsEmpty(obj))
{
return false;
}
//删除数据->front往后移动
obj->front = obj->front->next;
//成功删除则返回真
return true;
}
获取队尾元素
Rear
: 获取队尾元素。如果队列为空,返回 -1 。
- 获取队尾元素,要保证队列不为空
- tail指向的是队尾元素的下一个元素,要找到队尾元素,就需要遍历队列,找到tail的上一个元素
int myCircularQueueRear(MyCircularQueue* obj)
{
//取队尾数据->要保证队头不为空
if(myCircularQueueIsEmpty(obj))
{
//如果队列为空,返回 -1
return -1;
}
//由于tail标志的是队尾的后一个元素
//tail的前一个结点就是队尾结点
//遍历查找
ListNode* cur = obj->front;
while(cur->next != obj->tail)
{
cur = cur->next;
}
//跳出循环时:cur指向的就是tail的前一个结点
//返回此时的数据,就是队尾的值
return cur->data;
}
获取队头元素
Front
: 从队首获取元素。如果队列为空,返回 -1 。
-
获取队头元素,要保证队列不为空
-
如果队列不为空。front指向的就是队头结点,直接返回front指向结点的数据
int myCircularQueueFront(MyCircularQueue* obj)
{
//取队头数据->要保证队头不为空
if(myCircularQueueIsEmpty(obj))
{
//如果队列为空,返回 -1
return -1;
}
return obj->front->data;
}
判断队列是否为空
isEmpty()
: 检查循环队列是否为空
如果tail和front指向相同的结点 ->队列为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//如果tail == front就是空
return obj->tail == obj->front;
}
判读队列是否为满
isFull()
: 检查循环队列是否已满。
如果tail -> next == front 队列就满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//如果tail->next == front就是满
return obj->tail->next == obj->front;
}
释放队列
注意:每个结点都是malloc出来的,要遍历释放。从头释放到尾
,最后还要释放队列结构体
void myCircularQueueFree(MyCircularQueue* obj) {
//链表的每个结点都是malloc出来的,需要遍历释放
ListNode* cur = obj->front;
//从头obj->head一直释放到尾obj->tail
while(cur != obj->tail)
{
ListNode* next = cur->next;//保存下一个结点
free(cur);
cur = next;
}
//注意:跳出循环时候:cur指向的就是尾结点
free(cur);//释放尾结点
//释放队列结构体
free(obj);
}
注意事项:
要把判空和判满的声明先放在前面,因为我们实现的接口,判空和判满是在我们调用的前面的,如果不先声明,会报错
用链表实现的代码
//链表的结点类型
typedef struct Node
{
struct Node* next;
int data;
}ListNode;
typedef struct
{
ListNode* front;//标志链表的头
ListNode* tail;//标志链表的尾
int k; //存放多少个数据
} MyCircularQueue;
//先声明判空和判满的函数
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k)
{
//动态开辟队列结构体
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//开辟k+1个空间的链表
//先开辟一个空间
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail = head;//方便链接
//开辟k个空间
while(k--)
{
//尾插
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
tail->next = newnode; //链接
tail = newnode; //新结点成为尾
}
//最后让tail和head进行链接,构成循环
tail->next = head;
//队列结构体的头指针和尾指针指向链表的头
tmp->front = head;
tmp->tail = head;//tail也是指向链表的头,后面要进数据,往后走
//把创建好的环形链表的队列返回
return tmp;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
//插入:要保证队列没有满
if(myCircularQueueIsFull(obj))
{
return false;
}
//插入到tail指向的结点,然后tail往后走
obj->tail ->data = value;
obj->tail = obj->tail ->next;
//成功插入则返回真
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//删除数据-要保证队列不为空
if(myCircularQueueIsEmpty(obj))
{
return false;
}
//删除数据->front往后移动
obj->front = obj->front->next;
//成功删除则返回真
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
//取队头数据->要保证队头不为空
if(myCircularQueueIsEmpty(obj))
{
//如果队列为空,返回 -1
return -1;
}
return obj->front->data;
}
int myCircularQueueRear(MyCircularQueue* obj)
{
//取队尾数据->要保证队头不为空
if(myCircularQueueIsEmpty(obj))
{
//如果队列为空,返回 -1
return -1;
}
//由于tail标志的是队尾的后一个元素
//tail的前一个结点就是队尾结点
//遍历查找
ListNode* cur = obj->front;
while(cur->next != obj->tail)
{
cur = cur->next;
}
//跳出循环时:cur指向的就是tail的前一个结点
//返回此时的数据,就是队尾的值
return cur->data;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//如果tail == front就是空
return obj->tail == obj->front;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
//如果tail->next == front就是满
return obj->tail->next == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
//链表的每个结点都是malloc出来的,需要遍历释放
ListNode* cur = obj->front;
//从头obj->head一直释放到尾obj->tail
while(cur != obj->tail)
{
ListNode* next = cur->next;//保存下一个结点
free(cur);
cur = next;
}
//注意:跳出循环时候:cur指向的就是尾结点
free(cur);//释放尾结点
//释放队列结构体
free(obj);
}
- 点赞
- 收藏
- 关注作者
评论(0)