【数据结构】设计循环队列

🌈欢迎来到数据结构专栏~~栈和队列oj题

---

• (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort🎓
• 🌍博客主页：张小姐的猫~江湖背景🌍
• 快上车🚘，握好方向盘跟我有一起打天下嘞！
• 送给自己的一句鸡汤🤔：
• 🔥在路上就好，无问东西🔥
• 🙏作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
• 🎉🎉欢迎持续关注！🎉🎉
  

🌍 设计循环队列 【难度：中等】

🏷️力扣地址：🌈622. 设计循环队列

🌍题目描述：

💥特别注意：

• 无论是数组实现还是链表实现，都要多开一个空间，否则无法区分判空判满。即要存k个数据的循环队列，要开(k+1)个空间。
• 用数组实现，要注意当到了尾节点，如何将指针重置的问题

考虑到，用指针实现，不仅仅要找尾，还要找尾的上一个，都挺麻烦的，所以接下来我要用数组实现一下

🌠动图解析：👇🏻

🎄 入对列

💫关键思路：

• 【极端思维】如果队列已经满了，还要继续插入吗？ ❌应该直接返回false
• 入队列，tail++，然后插入数据
• 【极端思维】当tail去到k+1 的时候，tail就要回到k==0的位置

🌠动图解析：👇🏻

代码实现💡：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
   
    if(myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->tail] = value;
    obj->tail++;

    if(obj->tail == k+1)
       obj->tail =0;
    //取模法 ~ 画图理解
    //obj->tail = (k+1);
    return true;
}

🎄判断队列是否满

💫关键思路：

• 定义一个next作为tail的下一个节点

• 【极端思维】当next去到k+1 的时候，next就要回到k==0的位置

🌠动图解析：👇🏻

代码实现💡：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
   
    int next = obj->tail + 1;
    if(next == k+1)
       next = 0;

    return next == obj->head;
}

🎄判断队列是否为空

💫关键思路：

• 出队列一个，head++，直到head == tail的时候，队列为空

这里比较简单直接上代码
代码实现💡：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
   
    return obj->head == obj->tail;
}

🎄出队列

💫关键思路：

• 【极端思维】：还是和上面的一样：当head走到k+1的时候，要重置一下head，回到k=0

代码实现💡：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
   
    if(myCircularQueueIsEmpty(obj))
      return false;
     
    ++obj->head;
    if(obj->head == k+1)
       obj->head =0;
    
    return true;
}

🎄取出队尾数据

💫关键思路：

• 【极端思维】：当tail在k=0的时候，队尾的数据应该在tail=k的位置，也就是下图中的5的位置
• 取模法：每次++，下一次都可能越界，就%= k+1处理一下

🌠画图解析：👇🏻

代码实现💡：

int myCircularQueueRear(MyCircularQueue* obj) {
   
    if(myCircularQueueIsEmpty(obj))
      return -1;

    int prev = obj->tail-1;
    if(obj->tail ==0)
      prev =obj->k;
    //取模法
    //int prev = obj -> tail-1 + k + 1;
    // prev %= (k+1);

    return true;
}

🎄销毁队列

💫特殊注意：

我们可以直接把obj给free掉吗？ ❌
结构如下

• 如果我先把obj给释放掉，那么开创的数组空间就是内存泄漏了
• 所以应该先释放数组空间，再释放结构体空间

代码实现💡：

void myCircularQueueFree(MyCircularQueue* obj) {
   
     free(obj->a);
     free(obj);
}

意外发生：

遇到这样的报错，其实是因为前面的函数调用了后面的函数接口，那在前面声明一下就好了，也可以把顺序换一下就行

完整代码如下：

typedef struct {
   
    int *a;
    int k;
    int tail;
    int head;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
   
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = malloc(sizeof(int)*(k+1));//因为要多开一个空间去判断 空or满
    obj->head = obj->tail =0;
    obj->k = k;

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
   
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
   
    int next = obj->tail + 1;
    if(next == obj->k+1)
       next = 0;

    return next == obj->head;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
   
    if(myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->tail] = value;
    obj->tail++;

    if(obj->tail == obj->k+1)
       obj->tail =0;
    
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
   
    if(myCircularQueueIsEmpty(obj))
      return false;
     
    ++obj->head;
    if(obj->head == obj->k+1)
       obj->head =0;
    
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
   
    if(myCircularQueueIsEmpty(obj))
      return -1;

    return obj->a[obj->head]; 
}

int myCircularQueueRear(MyCircularQueue* obj) {
   
    if(myCircularQueueIsEmpty(obj))
      return -1;

    int prev = obj->tail-1;
    if(obj->tail ==0)
      prev =obj->k;

    return obj->a[prev];
}

void myCircularQueueFree(MyCircularQueue* obj) {
   
     free(obj->a);
     free(obj);
}

可能我们还是对取模法有点不清晰，接下来看这道题目

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)
解析如图：

答案：B

总结：

• 取模的时候，要注意有需要的时候可以加上队列的长度，然后再模

📢写在最后

• 能看到这里的都是棒棒哒🙌！
• 想必栈和队列也算是数据结构中比较难🔥的部分了，如果认真看完以上部分，肯定有所收获。
• 接下来我还会继续写关于📚《排序》等…
• 💯如有错误可以尽管指出💯
• 🥇想学吗？我教你啊🥇
• 🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉
  

转载：https://blog.csdn.net/qq_42996461/article/details/125674149