用链表实现循环队列

举报
芒果_Mango 发表于 2022/03/28 10:41:43 2022/03/28
【摘要】 大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助!如果有错误请大佬们指正!共同学习交流作者简介:CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog掘金LV3用户 https://juejin.cn/u...

大家好,我是芒果,一名非科班的在校大学生。对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


题目

622. 设计循环队列 - 力扣(LeetCode) (leetcode-cn.com)

image-20220209215847477

循环队列

  • 1.符合先进先出
  • 2.空间大小是固定的,一开始就要开辟好空间,空间重复利用
    • 若用链表实现,出数据不用释放空间

为了方便插入和删除:

定义两个变量:记为front和tail

入数据:tail往后走

出数据:front往后走

当tail/front走到最后一个位置还要往后走:回到第一个位置(循环)


分析:

存k个数据,只开辟k个空间的话

  • 数组实现

image-20220209215856686

判空和判满产生歧义!

  • 链表实现

image-20220209215908484

判空和判满产生歧义!


==解决办法:要存放k个数据,就开辟k+1个空间,否则无法实现判空和判满==

  • 数组

image-20220209215920323

判空 :front == tail
判满: (tail + 1)%( k + 1) == front

  • 链表

image-20220209215930473

判空: 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标志的是队尾结点的下一个结点==

image-20220209215945373

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往后走
  • 删除数据,并不释放空间,空间重复利用

image-20220209215956585

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);
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。