您现在的位置是：首页 >技术杂谈 >什么?要求设计一个循环队列?网站首页技术杂谈

什么?要求设计一个循环队列?

初阶牛 2024-07-20 06:01:03
简介什么?要求设计一个循环队列?

在这里插入图片描述

?个人主页:? :✨✨✨初阶牛✨✨✨
?推荐专栏:
???C语言初阶
???C语言进阶

?个人信条: ?知行合一
?本篇简介:>:讲解用c语言实现数据结构的循环队列.

目录

一、题目介绍:

先声明一下:
题目来源：力扣（LeetCode）

题目名称:设计循环队列:题目链接
难度: 中等

介绍:
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

需要实现的接口介绍:

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

测试接口示例:

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

二、接口函数的分析:

2.1 循环队列的结构

typedef int Queuedate;
typedef struct {
    Queuedate* date;
    int front;//队首下标
    int rear;//队尾
    int k;//队列的长度(固定的)
} MyCircularQueue;

刚开始设计循环队列时:
在这里插入图片描述
为了显示循环的模样,更加形象的图:
在这里插入图片描述

此时遇到了一个难题:

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

为了解决队列判满与判空冲突问题,这里选择设计2:以多开一个空间为代价.

那有没有办法不开空间也能解决这个问题呢?

另外方案:
增加一个size指针,用于记录循环队列元素的实际元素个数.

满队列: size=k
空队列: size为0的时候是空队列

2.2 初始化"循环队列"(myCircularQueueCreate)

步骤:

  1. 为使得myCircularQueueCreate函数生命周期结束后,obj(循环队列)不被销毁,所以需要动态申请(malloc)空间.
  2. 为obj(循环队列)的date 指针申请k(容量)个单位的空间.
  3. 将front (队首下标)和rear(待插入位置下标)设置初始状态为0.
  4. 将参数k的值,存入obj(循环队列)保存,作为循环队列的最大容量.
  5. 返回obj(循环队列).

代码:

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));;
    obj->date = (Queuedate*)malloc(sizeof(Queuedate) * (k + 1));
    if (obj->date == NULL)//如果开辟空间失败
    {
        perror("obj malloc error");
    }
    //初始化时,队首和队尾都暂时赋值为0下标
    obj->front = obj->rear = 0;
	//记录k的值,k表示循环队列的容量.
    obj->k = k;
    return obj;
}

2.3 入队(myCircularQueueEnQueue)

返回值说明:

true表示入队成功.
false表示入队失败.

步骤:

1.进行入队操作前,需要考虑队满情况(队满直接返回false即入队失败).
2.在rear下标位置插入新元素value.
3. 由于这里是循环队列,所以相比于普通的队列,这里需要一个rear自增时需要使其能够循环回0下标处.(重点)

在这里插入图片描述

此时rear=4,如果我们进行 %周期 操作
(rear++) % (k + 1)
= 5 % 5
=0
这样,rear就可以重新从0开始循环了.

代码实现:

bool bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->date[obj->rear] = value;
    //队尾++,注意考虑回0情况.
    obj->rear = (obj->rear + 1) % (obj->k + 1);
    return true;
}

2.4 出队(myCircularQueueDeQueue)

步骤解析:

  1. 出队列之前要考虑队列是否为空,队列为空返回false.
  2. front(队首下标)向后移动一位.

由于是循环队列,front也要考虑特殊情况,也需要能够回0(%周期)操作.
在这里插入图片描述

2.5 取队首、队尾元素

队首元素很简单获取,返回obj->date[obj->front]即可.
需要注意的是:如果循环队列为空,这里规定队首返回值-1;(题干有要求).

队尾元素获取稍微复杂一些,因为存在特殊情况,如下图:
在这里插入图片描述
此时可以直接返回obj->date[rear-1] 吗?
那岂不是date[-1]了,所以我们需要对rear进行处理.
rear - 1 + k + 1加上一套周期,那么:

0 - 1 + 5 % 5 = 4
似乎是满足要求的.

可是,不要高兴的太早了,我们为了解决这一特殊情况进行了==+周期==,那普通情况呢?
在这里插入图片描述
rear - 1 + k + 1加上一套周期还对吗?

2 - 1 + 5 = 6.

所以我们还需要进行==%周期==操作.
即完整的:obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//规定,如果队列为空,则队首是-1;
    {
        return -1;
    }
    return obj->date[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//规定,如果队列为空,则队首是-1;
    {
        return -1;
    }
    return obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}

代码实现:

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

2.6 循环队列的判空、判满:

在设计循环队列的时候就考虑过这个问题,所以相信大家解决这两个接口还是很简单的吧!

判空:
front(队首)和rear (待插入)指向相等时,为空.

判满:

front(队首)和rear (待插入)的下一个相等时为满.(注意%周期哦).

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if ((obj->rear + 1) % (obj->k + 1) == obj->front)
    {
        return true;
    }
    else
    {
        return false;
    }
}

循环队列的销毁:

只需要将之前在堆区申请的两次空间释放即可.

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

在这里插入图片描述

三、总代码:

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

typedef int Queuedate;
typedef struct {
    Queuedate* date;
    int front;//队首下标
    int rear;//待插入位置的下标
    int k;//队列的长度(固定的)
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));;
    obj->date = (Queuedate*)malloc(sizeof(Queuedate) * (k + 1));
    if (obj->date == NULL)
    {
        perror("obj malloc error");
    }
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->date[obj->rear] = value;
    //队尾++
    obj->rear = (obj->rear + 1) % (obj->k + 1);
    return true;
}

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

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//如果队列为空,则队首是-1;
    {
        return -1;
    }
    return obj->date[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))//如果队列为空,则队首是-1;
    {
        return -1;
    }
    return obj->date[(obj->rear - 1 + obj->k + 1) % (obj->k + 1)];
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if ((obj->rear + 1) % (obj->k + 1) == obj->front)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->date);
    free(obj);
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐