【数据结构】如何设计循环队列？图文解析（LeetCode）_网站优化分享

您的位置：上海毫米网络优化公司 > 网站优化分享 >

做题思路

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

假设队列长度 k = 4

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

为什么？

举个栗子：

只开辟 k 个空间

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

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

如果插入一个数据呢？

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

理想的判断空条件：
- 队头 == 队尾，队列为空
- 队头 != 队尾，队列非空
  目前看来似乎可以正常判断队列是否为空
  
  那如果队列满了呢？
  
  如上图所示，队列满了
  
  rear 又回到了 front 的位置
  
  现在怎么判断满呢？
  
  rear == front 吗？
  
  似乎和前面判断空冲突了
  
  想判断必须要特殊处理：比如加一个变量 size 来记录队列中元素的个数
  
  这种方法虽然可以，但是会让代码显得很臃肿，于是我选择了另一种方法：
  
  多开一个空间
  
  如果多开了一个空间（开辟 k+1 个空间）：
  - 这里多开的空间是不存放数据的
  - 这块空间存在的意义就是为了方便区分空和满
  下面我将演示一下如何判断：
  
  判断空：
  - 队头 == 队尾，队列为空
  - 队头 != 队尾，队列非空
    判断满：
    - 队尾的下一个 == 队头，队列已满
    - 队尾的下一个 != 队头，队列未满
      如下图：
      
      那么好，这里简单介绍了一下我的实现思路：
      - 使用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有可能会越界
        
        如上图：rear+1 = 5，越界了
        
        怎么办呢？可以采用取余数（%）的方法，即：（rear+1）%（k+1），让 rear+1 变回 0，达到循环的效果。
        
        情况1：队尾+1越界了
        
        (rear + 1) % (k + 1) = 0
        
        front = 0
        
        (rear + 1) % (k + 1) = front，说明循环队列已满。
        
        情况2：队尾+1没越界
        
        (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. 队尾插入数据
        
        这里需要一些操作，还是越界的问题，插入数据后队尾可能会越界，如下图：
        
        在 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. 队头删除数据
        
        删除数据后，队头也可能会有越界的情况，如下图：
        
        删除 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)
        
        如上图：这种情况下强行获取 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); }
        
        本文完
        
        网络广告人社区自己搞个app要多少钱网络营销软件武汉网页设计招聘天津建站公司模板公司网站建设费计入科目