DS线性表之循环队列的讲解和实现(7)

---

前言

  力扣No.622设计循环队列
  本篇就以这题为基开始讲起

---

一、循环队列的概念

  循环队列是一种用数组实现的队列数据结构，与普通队列不同的是，循环队列允许队列的头尾相接，实现循环利用数组空间。它解决了普通队列在出队操作频繁时需要大量元素迁移的效率问题。

  循环队列通常通过两个指针来实现：一个指向队列的头部（front），一个指向队列的尾部（rear）。当队列满时，rear 指针可以绕回到数组的起始位置，实现循环存储；当队列为空时，front 和 rear 指针指向同一个位置

循环队列该怎样设计已经由上图给出，但我等下还是想讲解下为什么这么做

二、该怎么设计循环队列？

使用单链表？

确实，通过我们前面的学习，我相信大家跟我一样看到循环首先想到的是单链表加个头尾相连，中间放k个节点，这时候，我思考一个问题如下：

要不要加头节点？

事实上没必要，我们是一开始就打算开好所有k个节点，加个头节点还挺麻烦，在这里意义不大，且考虑以后入出队列还要特殊处理，所以我们放弃

rear指向哪里？

具体来说，rear应该指向哪里，是尾部，还是尾部的下一位(同栈的top栈顶指针一样)？，我们一个个来具体分析：
一、选择指向尾部的下一位，那么这时候你想想假溢出问题（判空和判满重叠），一开始没放数据，和放满都是front == rear，这很难办

二、那我们考虑加个size变量，当front == rear的时候，如果size等于0就判空，等于k就判满？其实这样也行，但是有个问题，这个时候取尾就很麻烦，因为我们rear指向的是尾部的下一位，可单链表如果要回退一个就很痛苦，加个双向链表又搞复杂了，于是我们就不考虑了

三、假如我们让rear指向尾部，可一开始rear要放哪里，肯定不是放在第一个节点上，这样就又成了尾部的下一位了，那我们将其置空，可这样当数据0个和1个的时候就又要特殊区分处理了，能行，但是很麻烦

使用数组，但怎么成环？

如果使用链表，一开始的创建也比较麻烦，综合考虑下我们使用数组，且多开一个节点，用来区分判空和判满这两种不同的情况

可数组怎么成环？答案是取模，这很精妙，因为我们两个指针其实是下标，为了达到到了空位置，相当于是到了头位置这个目的，我们如果左边小于右边，没有改变。如果左边大于左边，就会删除右边的倍数

三、循环队列的实现

理论存在，实践开始！

循环队列的结构体

typedef struct 
{
    int* a;
    int front; // 头
    int rear;  // 尾的下一位
    int k;     // 有效数字
} MyCircularQueue;

构建器(设置队列长度为 k)

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;
}

// rear + 1 == front，但是rear + 1可能会越界，所以我们要取模
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

获取队头和队尾

这里要注意一下，获取队头队尾的时候，要注意判空一下

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

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

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

    return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->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;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj)){
        return false;
    }

    obj->front++;
    obj->front %= obj->k + 1;

    return true;
}

销毁

很自然地先销毁循环队列的数组，再销毁循环队列的指针，最后置空，避免成为野指针

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

    obj = NULL;
}

四、代码汇总

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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;
}

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

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

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

    return obj->a[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}

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

    obj = NULL;
}

int main()
{
    MyCircularQueue* cq = myCircularQueueCreate(4); // 最多存放四个有效数据

    int i = 0;
    // 存进去 1 2 3 4，但是只是打印队头1
    while (myCircularQueueEnQueue(cq, ++i)) {
        int front = myCircularQueueFront(cq);
        printf("%d ", front);
    }
    putchar('\n');

    i = 0;
    // 出去 1 2 3 4，打印尾部 4 4 4，最后一次为空，打印-1
    while (myCircularQueueDeQueue(cq)) {
        int back = myCircularQueueRear(cq);
        printf("%d ", back);
    }
    putchar('\n');

    myCircularQueueFree(cq);

    return 0;
}

---

总结

  感觉如何~，是不是对取模感到很惊奇，计算机的世界就是这样，有很多我们想不到的巧妙设计等着我们去学习乃至发现，一起加油！

原文地址：https://blog.csdn.net/2301_80392199/article/details/142993303

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！