【数据结构】如何设计循环队列？图文解析（LeetCode）

03-08 9195阅读 0评论

【数据结构】如何设计循环队列？图文解析（LeetCode） 第1张

LeetCode链接：622. 设计循环队列 - 力扣（LeetCode）

目录

做题思路

只开辟 k 个空间

多开一个空间

代码实现

1. 循环队列的结构

2. 开辟空间

3. 判断空

4. 判断满

5. 队尾插入数据

6. 队头删除数据

7. 获取队头元素

8. 获取队尾元素

9. 销毁队列

全部代码

做题思路

  • 设计循环队列，使用数组或链表都可以，各有优劣
  • 本文使用数组实现
  • 本文使用C语言实现

    假设队列长度 k = 4

    多开一块空间（开辟 k+1 块空间）可以方便区分空和满

    为什么？

    举个栗子：

    只开辟 k 个空间

    如果只开辟 k 个空间（假设 k = 4）：

    • front（队头）
    • rear（队尾）
    • front 和 rear 初始都为 0

      【数据结构】如何设计循环队列？图文解析（LeetCode） 第2张

      如果插入一个数据呢？

      front 不变，rear 向后移动，如下图：

      【数据结构】如何设计循环队列？图文解析（LeetCode） 第3张

      理想的判断空条件：

      • 队头 == 队尾，队列为空
      • 队头 != 队尾，队列非空

        目前看来似乎可以正常判断队列是否为空

        那如果队列满了呢？

        【数据结构】如何设计循环队列？图文解析（LeetCode） 第4张

        如上图所示，队列满了

        rear 又回到了 front 的位置

        现在怎么判断满呢？

        rear == front 吗？

        似乎和前面判断空冲突了

        想判断必须要特殊处理：比如加一个变量 size 来记录队列中元素的个数

        这种方法虽然可以，但是会让代码显得很臃肿，于是我选择了另一种方法：

        多开一个空间

        如果多开了一个空间（开辟 k+1 个空间）：

        【数据结构】如何设计循环队列？图文解析（LeetCode） 第5张

        • 这里多开的空间是不存放数据的
        • 这块空间存在的意义就是为了方便区分空和满

          下面我将演示一下如何判断：

          判断空：

          • 队头 == 队尾，队列为空
          • 队头 != 队尾，队列非空

            判断满：

            • 队尾的下一个 == 队头，队列已满
            • 队尾的下一个 != 队头，队列未满

              如下图：

              【数据结构】如何设计循环队列？图文解析（LeetCode） 第6张

              那么好，这里简单介绍了一下我的实现思路：

              • 使用C语言实现
              • 使用数组实现
              • 数组多开一块空间

                接下来就是详细的实现方法

                代码实现

                本题要求：

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

                  1. 循环队列的结构

                  //循环队列的结构
typedef struct
{
    int* a;     //一个数组
    int front;  //存放队头的下标
    int rear;   //存放队尾的下标
    int k;      //队列长度
} MyCircularQueue;

                  2. 开辟空间

                  //开辟空间并初始化
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个方便区分空和满
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

                  3. 判断空

                  前面说过了，队头等于队尾时，队列为空

                  //检测循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->rear;
}

                  4. 判断满

                  注意这里有一些坑点

                  前面说过：队尾+1等于队头时，队列为满

                  但是我用的是数组，不是链表，队尾+1有可能会越界

                  【数据结构】如何设计循环队列？图文解析（LeetCode） 第7张

                  如上图：rear+1 = 5，越界了

                  怎么办呢？可以采用取余数（%）的方法，即：（rear+1）%（k+1），让 rear+1 变回 0，达到循环的效果。

                  情况1：队尾+1越界了

                  【数据结构】如何设计循环队列？图文解析（LeetCode） 第8张

                  (rear + 1) % (k + 1) = 0

                  front = 0

                  (rear + 1) % (k + 1) = front，说明循环队列已满。

                  情况2：队尾+1没越界

                  【数据结构】如何设计循环队列？图文解析（LeetCode） 第9张

                  (rear + 1) % (k + 1) = 4

                  front = 0

                  (rear + 1) % (k + 1) != front，说明循环队列未满。

                  //检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

                  5. 队尾插入数据

                  这里需要一些操作，还是越界的问题，插入数据后队尾可能会越界，如下图：

                  【数据结构】如何设计循环队列？图文解析（LeetCode） 第10张

                  在 rear 处插入数据后，rear 需要向后移动，导致越界

                  1）判断队列是否已满，满了是不能插入的，直接返回 false

                  2）在队尾插入数据

                  3）队尾++，可能会越界

                  4）依旧采用取余数的方法让队列循环起来，即：rear = rear % (k + 1)

                  //向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k + 1);
    return true;
}

                  6. 队头删除数据

                  删除数据后，队头也可能会有越界的情况，如下图：

                  【数据结构】如何设计循环队列？图文解析（LeetCode） 第11张

                  删除 front 处的数据后，front 需要向后移动，导致越界

                  1）判断队列是否为空，空队列是不能删数据的，直接返回 false

                  2）删除数据很简单，直接让队头++即可

                  3）取余数避免越界：front = front % (k + 1)

                  //从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= (obj->k + 1);
    return true;
}

                  7. 获取队头元素

                  情况1：队列为空

                  根据题意，返回 -1

                  情况2：队列不为空

                  直接返回数组中下标为 front 的元素即可

                  //从队首获取元素。如果队列为空，返回-1
int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

                  8. 获取队尾元素

                  情况1：队列为空

                  根据题意，返回 -1

                  情况2：队列不为空

                  • 需要返回数组中下标 rear 的前一个元素（rear-1）
                  • 此操作可能会导致越界
                  • 用取余数的方式避免越界：(rear + k) % (k + 1)

                    【数据结构】如何设计循环队列？图文解析（LeetCode） 第12张

                    如上图：这种情况下强行获取 rear 的前一个元素会导致越界

                    //获取队尾元素。如果队列为空，返回-1
int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}

                    9. 销毁队列

                    销毁所有动态开辟的空间

                    //销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

                    全部代码

                    //循环队列的结构
typedef struct
{
    int* a;     //一个数组
    int front;  //存放队头的下标
    int rear;   //存放队尾的下标
    int k;      //队列长度
} MyCircularQueue;
//开辟空间并初始化
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个方便区分空和满
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}
//检测循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->rear;
}
//检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
//向循环队列插入一个元素。如果成功插入则返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear] = value;
    obj->rear++;
    obj->rear %= (obj->k + 1);
    return true;
}
//从循环队列中删除一个元素。如果成功删除则返回真
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front %= (obj->k + 1);
    return true;
}
//从队首获取元素。如果队列为空，返回-1
int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}
//获取队尾元素。如果队列为空，返回-1
int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}
//销毁循环队列
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);
    free(obj);
}

                    本文完


相关阅读：

1、Axios使用

2、【NodeMcu-ESP8266】引脚使用参考指南——推荐收藏

3、【JavaEE多线程】Java 文件操作

4、【数据结构】图论（图的储存方式，图的遍历算法DFS和BFS、图的遍历算法的应用、图的连通性问题）

5、使用FastDDS编译IDL文件

免责声明
1、本网站属于个人的非赢利性网站，转载的文章遵循原作者的版权声明。
2、本网站转载文章仅为传播更多信息之目的，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所
提供信息的准确性及可靠性，但不保证信息的正确性和完整性，且不对因信息的不正确或遗漏导致的任何
损失或损害承担责任。
3、任何透过本网站网页而链接及得到的资讯、产品及服务，本网站概不负责，亦不负任何法律责任。
4、本网站所刊发、转载的文章，其版权均归原作者所有，如其他媒体、网站或个人从本网下载使用，请在
转载有关文章时务必尊重该文章的著作权，保留本网注明的“稿件来源”，并白负版权等法律责任。

手机扫描二维码访问

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

发表评论

快捷回复： 表情：
评论列表 （暂无评论，9195人围观）

还没有评论，来说两句吧...

目录[+]