手把手教你实现一个循环队列（C语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了手把手教你实现一个循环队列（C语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这是一道leetcode关于队列的经典题：

622. 设计循环队列https://leetcode.cn/problems/design-circular-queue/ 手把手教你实现一个循环队列（C语言）,题目,数据结构,c语言,开发语言,leetcode,链表,数据结构

思路：

大家注意这个题目要求，这个队列是定长的，如果满了则不能再添加数据。那么我们设计一个队头front和队尾rear，每次添加数据rear向后走，这时就有一个问题，怎么区分空和满呢？当最后一个数据入队列之后，由于这是个循环队列，rear会回到front这个位置。那么比较好的一种方法就是多开一个空间，满的条件是rear+1==front。

手把手教你实现一个循环队列（C语言）,题目,数据结构,c语言,开发语言,leetcode,链表,数据结构

实现：

循环队列的定义：

typedef struct {
    int K;
    int* a;
    int front;
    int rear;
} MyCircularQueue;

循环队列的创建：

为队列和数组创建空间，需要注意的是数组a的空间是K+1个，要多开一个.

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开辟一个空间，用以区分空和满
    obj->K=k;
    obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
    obj->front=0;
    obj->rear=0;
    return obj;
}

判断队列是否为空：

如果front==rear则为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}

判断队列是否为满：

如果rear+1==front则为满，或者说(rear+1)%(k+1）==front。

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->K+1)==obj->front;
}

数据入队列：

先判断队列是否满了，满了则返回false。如果不满则在rear这个位置上添加数据，再把rear++，再将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->rear)%(obj->K+1);
    return true;
}

数据出队列：

判断一下队列是否为空，空则返回false。出队列直接将front++即可，再将front=front%（k+）。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front=(obj->front)%(obj->K+1);
    return true;
}

取队列头部数据：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

取队列尾部数据：

这里需要注意，尾部数据的位置是在rear-1这个位置，所以rear-1+k+1就是rear+k.

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

完整代码：

typedef struct {
    int K;
    int* a;
    int front;
    int rear;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开辟一个空间，用以区分空和满
    obj->K=k;
    obj->a=(int*)malloc(sizeof(int)*(obj->K+1));
    obj->front=0;
    obj->rear=0;
    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->rear)%(obj->K+1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front=(obj->front)%(obj->K+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

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

这次的分享到这里就结束了，感谢大家的阅读！文章来源地址https://www.toymoban.com/news/detail-758989.html

到了这里，关于手把手教你实现一个循环队列（C语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！