1. Toy模板网首页
  2. > Toy博客

数据结构:循环队列的实现(leetcode622.设计循环队列)

10月前 作者：摆烂小青菜 分类：Toy博客 阅读(44) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构:循环队列的实现(leetcode622.设计循环队列)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

 文章来源地址https://www.toymoban.com/news/detail-780220.html

目录

一.循环队列简单介绍

二.用静态数组实现循环队列

1.数组循环队列结构设计

2.数组循环队列的堆区内存申请接口 

3.数据出队和入队的接口实现

4.其他操作接口

5.数组循环队列的实现代码总览 

三.静态单向循环链表实现循环队列 

1.链表循环队列的结构设计

2.创建静态单向循环链表的接口

3.数据的出队和入队接口

4.其他队列操作接口

5.静态链表循环队列总体代码

问题来源:622. 设计循环队列 - 力扣（Leetcode）

一.循环队列简单介绍

  • 循环队列一般是一种静态的线性数据结构,其中的数据符合先进先出的原则.
  • 循环队列的容器首地址和容器尾地址通过特定操作(比如指针链接,数组下标取余等方式)相连通,从而实现了容器空间的重复利用(在一个非循环静态队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间)

设计循环队列存储结构,初阶数据结构,数据结构,散列表

设计循环队列存储结构,初阶数据结构,数据结构,散列表 

二.用静态数组实现循环队列

维护队列的结构体:

typedef struct 
{
    int * arry;  //指向堆区数组的指针
    int head;    //队头指针
    int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)
    int capacity;//静态队列的容量
} MyCircularQueue;

1.数组循环队列结构设计

我们假定静态数组的容量为k(可存储k个数据)：

  • 根据队列的基本数据结构:有两个指针用于维护数组中的有效数据空间,分别为head指针和tail指针,head指针用于指向队头数据,tail用于指向队尾数据的下一个位置(即tail指针不指向有效数据)设计循环队列存储结构,初阶数据结构,数据结构,散列表
  •  如图所示,head指针和tail指针之间就是有效数据的内存空间
  • 通过head指针和tail指针的关系来实现队列的判满(判断队列空间是否已被占满)与判空(判断队列是否为空队列)；为了达到这个目的,我们需要将静态数组的容量大小设置为k+1(即多设置一个元素空间) 
  1. 队列的判空条件: tail == head;设计循环队列存储结构,初阶数据结构,数据结构,散列表
  2. 队列的判满条件: (tail+1)%(k+1) == head;设计循环队列存储结构,初阶数据结构,数据结构,散列表 另外一种情形:设计循环队列存储结构,初阶数据结构,数据结构,散列表
  • 由此我们可以先设计出队列的判满和判空接口： 
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空
{
    assert(obj);
    return (obj->tail == obj->head);
}

bool myCircularQueueIsFull(MyCircularQueue* obj)  //判断队列是否为满
{
    assert(obj);
    return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}

2.数组循环队列的堆区内存申请接口 

  • 在堆区上创建MyCircularQueue结构体,同时为队列申请一个空间大小为(k+1)*sizeof(DataType)字节的数组： 
    MyCircularQueue* myCircularQueueCreate(int k)  //k个容量大小的循环队列的初始化接口
{
    MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    //开辟维护循环队列的结构体
    if(NULL == tem)
    {
        perror("malloc failed");
        exit(-1);
    }
    tem->arry = NULL;
    tem->capacity = k;   
    //队列的数据容量为k
    tem->arry = (int*)malloc((k+1)*sizeof(int));
    //开辟堆区数组
    if(NULL == tem->arry)
    {
        perror("malloc failed");
        exit(-1);
    }
    //将head,tail下标初始化为0
    tem->head = 0; 
    tem->tail = 0;
    return tem;
}

3.数据出队和入队的接口实现

数据出队和入队的图解:

设计循环队列存储结构,初阶数据结构,数据结构,散列表

设计循环队列存储结构,初阶数据结构,数据结构,散列表设计循环队列存储结构,初阶数据结构,数据结构,散列表

设计循环队列存储结构,初阶数据结构,数据结构,散列表 

  •  根据图解我们可以设计出数据入队和出队的接口: 
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口
{
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //确保队列没满
    obj->arry[obj->tail]=value;
    obj->tail = (obj->tail + 1)%(obj->capacity +1);
    return true;
}
    bool myCircularQueueDeQueue(MyCircularQueue* obj)    //数据出队接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //确保队列不为空
    obj->head = (obj->head +1)%(obj->capacity +1);
    return true;
}

4.其他操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)   //返回队头数据的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arry[obj->head];
}

 返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
    //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置
    return obj->arry[labelret];
}

队列的销毁接口:

void myCircularQueueFree(MyCircularQueue* obj)     //销毁队列的接口
{
    assert(obj);
    free(obj->arry);
    obj->arry = NULL;
    free(obj);
    obj = NULL;
}

5.数组循环队列的实现代码总览 

 数组循环队列总体代码:

typedef struct 
{
    int * arry;  //指向堆区数组的指针
    int head;    //队头指针
    int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)
    int capacity;//静态队列容量
} MyCircularQueue;


bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明

MyCircularQueue* myCircularQueueCreate(int k)          //循环队列初始化接口
{
    MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    //开辟维护循环队列的结构体
    if(NULL == tem)
    {
        perror("malloc failed");
        exit(-1);
    }
    tem->arry = NULL;
    tem->capacity = k;   
    //队列的数据容量为k
    tem->arry = (int*)malloc((k+1)*sizeof(int));
    //开辟堆区数组
    if(NULL == tem->arry)
    {
        perror("malloc failed");
        exit(-1);
    }
    
    tem->head = 0;
    tem->tail = 0;
    return tem;
}



bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口
{
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //确保队列没满
    obj->arry[obj->tail]=value;
    obj->tail = (obj->tail + 1)%(obj->capacity +1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)           //数据出队接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //确保队列不为空
    obj->head = (obj->head +1)%(obj->capacity +1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)               //返回队头数据的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arry[obj->head];
}

int myCircularQueueRear(MyCircularQueue* obj)                 //返回队尾数据的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
    //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置
    return obj->arry[labelret];
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj)               //判断队列是否为满
{
    assert(obj);
    return ((obj->tail+1)%(obj->capacity +1) == obj->head);
}

void myCircularQueueFree(MyCircularQueue* obj)                 //销毁队列的接口
{
    assert(obj);
    free(obj->arry);
    obj->arry = NULL;
    free(obj);
    obj = NULL;
}

力扣题解测试:

设计循环队列存储结构,初阶数据结构,数据结构,散列表

三.静态单向循环链表实现循环队列 

链表节点结构体定义:

typedef struct listnode
{
    int data;
    struct listnode * next;
}ListNode;

维护链表循环队列的结构体:

typedef struct 
{
    int capacity;     //记录队列容量大小
    ListNode * head;  //指向队头节点
    ListNode * tail;  //指向队尾节点
} MyCircularQueue;

1.链表循环队列的结构设计

静态单向循环链表的容量大小为k:

  • 与数组循环队列类似,我们同样需要开辟一个节点个数为k+1的静态循环链表
  • 链表循环队列的总体结构图示:设计循环队列存储结构,初阶数据结构,数据结构,散列表设计循环队列存储结构,初阶数据结构,数据结构,散列表另外一种队列判满的情形:设计循环队列存储结构,初阶数据结构,数据结构,散列表
  1.  链表循环队列的判满条件(判断队列空间是否被占满的关系式):tail->next == head;
  2.  链表循环队列的判空条件(判断队列是否为空队列的关系式): tail == head;

链表循环队列的判满和判空的接口:

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

bool myCircularQueueIsFull(MyCircularQueue* obj)     //判断队列是否为满
{
    assert(obj);
    return (obj->tail->next == obj->head);
}

2.创建静态单向循环链表的接口

实现一个接口,创建一个维护链表循环队列的结构体同时创建容量大小为k+1的静态单向循环链表:设计循环队列存储结构,初阶数据结构,数据结构,散列表

MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{
    int NodeNum =k+1;                          //创建k+1个链表节点
    MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    assert(object);                            //申请维护循环队列的结构体
    object->capacity = k;

    ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址
    while(NodeNum)
    {
        if(NodeNum == k+1)
        {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode = tem;
            object->tail = object->head=tem;    //让tail和head指向同一个初始节点
        }
        else
        {
            ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode->next = tem;                //链接链表节点
            preNode = tem;
        }
        NodeNum--;
    }
    preNode->next = object->head;               //将表尾与表头相接
    return object;
}

3.数据的出队和入队接口

数据出入队图解:

设计循环队列存储结构,初阶数据结构,数据结构,散列表设计循环队列存储结构,初阶数据结构,数据结构,散列表

设计循环队列存储结构,初阶数据结构,数据结构,散列表

根据图解实现数据出入队接口:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//数据入队接口(从队尾入队)
{
    assert(obj);
    if(!obj || myCircularQueueIsFull(obj))  //确定队列没满
    {
        return false;
    }           
    obj->tail->data = value;                //数据入队
    obj->tail = obj->tail->next;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)  //数据出队接口
{
    assert(obj);
    if(!obj || myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //数据出队
    obj->head = obj->head->next;
    return true;
}

4.其他队列操作接口

返回队头数据的接口:

int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->head->data; //返回队头元素
}

返回队尾数据的接口:

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    ListNode * tem = obj->head;
    while(tem->next != obj->tail)               //寻找队尾元素
    {
        tem=tem->next;
    }
    return tem->data;  //返回队尾元素
}

队列销毁接口:

队列销毁过程图解:设计循环队列存储结构,初阶数据结构,数据结构,散列表

void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{
    assert(obj);
    //利用头指针来完成链表节点的释放
    ListNode * endpoint = obj->head;           //记录一个节点释放的终点
    obj->head = obj->head->next;
    while(obj->head!=endpoint)
    {
        ListNode * tem = obj->head->next;
        free(obj->head);
        obj->head = tem;
    }
    free(endpoint);                            //释放掉终点节点
    free(obj);                                 //释放掉维护环形队列的结构体
}

5.静态链表循环队列总体代码

总体代码:

typedef struct listnode
{
    int data;
    struct listnode * next;
}ListNode;

typedef struct 
{
    int capacity;
    ListNode * head;
    ListNode * tail;
    int taildata;   //单向链表找尾复杂度为O(N),因此我们用一个变量来记录队尾数据
} MyCircularQueue;


bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//顺序编译注意:先被使用而后被定义的函数要记得进行声明



MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
{
    int NodeNum =k+1;                          //创建k+1个链表节点
    MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    assert(object);                            //申请维护循环队列的结构体
    object->capacity = k;

    ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址
    while(NodeNum)
    {
        if(NodeNum == k+1)
        {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode = tem;
            object->tail = object->head=tem;    //让tail和head指向同一个初始节点
        }
        else
        {
            ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
            assert(tem);
            preNode->next = tem;                //链接链表节点
            preNode = tem;
        }
        NodeNum--;
    }
    preNode->next = object->head;               //将表尾与表头相接
    return object;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口(从队尾入队)
{
    assert(obj);
    if(!obj || myCircularQueueIsFull(obj))  //确定队列没满
    {
        return false;
    }           
    obj->tail->data = value;                //数据入队
    obj->tail = obj->tail->next;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)               //数据出队接口
{
    assert(obj);
    if(!obj || myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->head = obj->head->next;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    ListNode * tem = obj->head;
    while(tem->next != obj->tail)               //寻找队尾元素
    {
        tem=tem->next;
    }
    return tem->data;
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj)                    //判断队列是否为满
{
    assert(obj);
    return (obj->tail->next == obj->head);
}



void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
{
    assert(obj);
    //利用头指针来完成链表节点的释放
    ListNode * endpoint = obj->head;           //记录一个节点释放的终点
    obj->head = obj->head->next;
    while(obj->head!=endpoint)
    {
        ListNode * tem = obj->head->next;
        free(obj->head);
        obj->head = tem;
    }
    free(endpoint);                            //释放掉终点节点
    free(obj);                                 //释放掉维护环形队列的结构体
}

leetcode题解测试:

设计循环队列存储结构,初阶数据结构,数据结构,散列表

设计循环队列存储结构,初阶数据结构,数据结构,散列表 

 

 

到了这里，关于数据结构:循环队列的实现(leetcode622.设计循环队列)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、

    2024年01月20日
    浏览(45)
  • Java 数据结构篇-用链表、数组实现队列（数组实现：循环队列）

    Java 数据结构篇-用链表、数组实现队列（数组实现：循环队列）

    🔥博客主页： 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 队列的说明         1.1 队列的几种常用操作         2.0 使用链表实现队列说明         2.1 链表实现队列         2.2 链表实现队列 - 入栈操作         2.3 链表实现队

    2024年02月05日
    浏览(40)
  • 【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    1.1 概念 队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾（Tail/Rear） 出队列：进行删除操作的一端称为 队头（Head/Front） 队列和栈的区别： 队列是 先进先出（队

    2024年02月03日
    浏览(44)
  • 入门数据结构，c语言实现循环队列实现（详细篇）。

    入门数据结构，c语言实现循环队列实现（详细篇）。

    目录 一、前言 二、循环队列的概念 三、实现循环队列 1、头文件与特殊函数介绍 2、循环队列的结构体 3、队列的初始化 4、判断队列是否为空 5、队列的进队操作 6、队列的出队操作 7、返回队头 8、返回队列长度 9、放回队列容量大小 10、销毁队列 四、完成队列（队列完整代

    2024年02月06日
    浏览(45)
  • 【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈

    【数据结构】队列篇| 超清晰图解和详解：循环队列模拟、用栈实现队列、用队列实现栈

    博主简介： 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页： @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子，都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路： 🍊数据结构： 使用数组为数据结构，且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(39)
  • 探索数据结构：链式队与循环队列的模拟、实现与应用

    探索数据结构：链式队与循环队列的模拟、实现与应用

    队列（queue）是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。其严格遵循 先进先出（First In First Out） 的规则，简称 FIFO 。 队头（Front） ：允许删除的一端，又称队首。 队尾（Rear） ：允许插入的一端。 队列与栈类似，实现方式有两种。一种是以 数组

    2024年04月08日
    浏览(82)
  • 【LeetCode】数据结构题解（12）[用栈实现队列]

    【LeetCode】数据结构题解（12）[用栈实现队列]

    所属专栏：玩转数据结构题型❤️ 🚀 博主首页：初阳785❤️ 🚀 代码托管：chuyang785❤️ 🚀 感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️ 🚀 博主也会更加的努力，创作出更优质的博文！！❤️ 🚀 关注我，关注我，关注我，重要的事情说三遍！！！！！

    2024年02月13日
    浏览(42)
  • 【LeetCode】数据结构题解（11）[用队列实现栈]

    【LeetCode】数据结构题解（11）[用队列实现栈]

    所属专栏：玩转数据结构题型❤️ 🚀 博主首页：初阳785❤️ 🚀 代码托管：chuyang785❤️ 🚀 感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️ 🚀 博主也会更加的努力，创作出更优质的博文！！❤️ 🚀 关注我，关注我，关注我，重要的事情说三遍！！！！！

    2024年02月13日
    浏览(39)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 ：这道题要求我们用栈模拟队列（工作上一定没人这么搞）。程序当中，push函数很好解决，直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作，而栈是先进后出。只

    2024年02月12日
    浏览(43)
  • 【数据结构】如何用队列实现栈？图文详解（LeetCode）

    【数据结构】如何用队列实现栈？图文详解（LeetCode）

    LeetCode链接：225. 用队列实现栈 - 力扣（LeetCode） 本文默认读者已经掌握栈与队列的基本知识 或者先看我的另一篇博客：【数据结构】栈与队列_字节连结的博客-CSDN博客 由于我们使用的是C语言，不能直接使用队列的操作， 所以做这道题得先把我们之前实现的队列复制过来：

    2024年02月12日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包