68Design一样设计网站,.org做商业网站,中山精品网站建设信息,商城开发平台. 个人主页#xff1a;晓风飞 专栏#xff1a;LeetCode刷题|数据结构|Linux 路漫漫其修远兮#xff0c;吾将上下而求索 文章目录 题目要求#xff1a;应该支持如下操作#xff1a;示例#xff1a;提示#xff1a; 结构体定义队列的创建基本操作判断队列是否为空#xf…
. 个人主页晓风飞 专栏LeetCode刷题|数据结构|Linux 路漫漫其修远兮吾将上下而求索 文章目录 题目要求应该支持如下操作示例提示 结构体定义队列的创建基本操作判断队列是否为空判断队列是否已满入队操作出队操作获取队首和队尾元素内存释放 难点解释难点1难点2难点3 要做题目的点击这里–队列oj题——622.设计循环队列
题目要求 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 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 提示 所有的值都在 0 至 1000 的范围内 操作数将在 1 至 1000 的范围内 请不要使用内置的队列库。 结构体定义
首先我们定义一个名为 MyCircularQueue 的结构体来表示循环队列
typedef struct {int *a; // 队列中的元素数组int k; // 队列的最大容量int front; // 指向队列头部元素的指针int back; // 指向队列尾部的下一个位置的指针
} MyCircularQueue;
在这个结构体中a 是一个整型数组用来存储队列中的元素。k 表示队列的最大容量front 和 back 分别表示队列头部和尾部的指针。
队列的创建
队列的创建涉及到内存的分配和初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a (int *)malloc(sizeof(int)*(k1));obj-front obj-back 0;obj-k k;return obj;
}这里我们为队列结构体和队列数组分配内存。注意我们为数组分配 k1 的空间因为在循环队列中我们总是保留一个位置不使用以区分队列为空和队列为满的状态。
基本操作
判断队列是否为空
// 检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-back; // 如果 front 和 back 相等则队列为空
}当 front 和 back 相等时队列为空。
判断队列是否已满
// 检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-back 1) % (obj-k 1) obj-front; // 如果 back 的下一个位置是 front则队列已满
}如果 back 的下一个位置是 front则队列已满。
入队操作
// 向队列中添加元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满则无法添加元素return false;obj-a[obj-back] value; // 在 back 的位置插入元素obj-back (obj-back 1) % (obj-k 1); // 更新 back 的位置在入队时我们首先检查队列是否已满。如果不满将元素放在 back 指向的位置并更新 back 指针。
出队操作
// 从队列中删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空则无法删除元素return false;obj-front (obj-front 1) % (obj-k 1); // 更新 front 的位置return true;
}出队时我们检查队列是否为空。如果不为空则移动 front 指针。
获取队首和队尾元素
// 获取队列头部的元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空返回 -1return -1;return obj-a[obj-front]; // 返回队列头部的元素
}// 获取队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空返回 -1return -1;return obj-a[(obj-back - 1 obj-k 1) % (obj-k 1)]; // 返回队列尾部的元素
}这两个函数用于获取队首和队尾的元素。注意在获取队尾元素时我们使用了模运算来正确处理环形结构。
内存释放
最后当队列不再需要时我们应该释放其占用的内存
// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a); // 释放数组内存free(obj); // 释放队列结构体内存
}难点解释
难点1 这里我优化了代码没有优化前是这样的
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满则无法添加元素return false;obj-a[obj-back] value; // 在 back 的位置插入元素obj-back; // 更新 back 的位置obj-back %(obj-k1);//确保值在循环队列的有效范围内return true;
}难点2 1.循环队列的容量在这个循环队列的实现中队列的实际容量是 k 1但为了区分空队列和满队列的状态我们总是保留一个元素的空间不使用。所以队列中最多可以存储 k 个元素。 2.队列尾部指针 (obj-back)这个指针指向队列中下一个元素将要存放的位置。当一个新元素被加入队列时它被放置在 obj-back 指向的位置然后 obj-back 会向前移动一个位置。 3.队列头部指针 (obj-front)这个指针指向队列中当前的第一个元素。当一个元素被移出队列时obj-front 会向前移动一个位置。 4.判断队列是否已满 (obj-back 1) % (obj-k 1) 计算出 obj-back 向前移动一个位置后的值并使用模运算确保这个值在循环队列的有效范围内即从 0 到 k。 难点3 下面是这个表达式的详细解释 1.obj-back: 指向队列中下一个插入元素的位置。 2.obj-back - 1: 因为 obj-back 指向的是下一个空位所以队尾元素实际上是在 obj-back - 1 的位置。 3.由于队列是循环的当 obj-back 为 0 时obj-back - 1 会变成一个负数。为了正确地处理这种情况我们加上 obj-k 1这保证了我们总是在一个正数的范围内操作。 4.(obj-back - 1 obj-k 1) % (obj-k 1): 这个模运算确保了即使加上了 obj-k 1结果仍然是在队列大小的合法范围内。因此这个表达式能够正确地处理循环队列的尾部元素访问无论 obj-back 是在队列的开始位置还是任何其他位置 可以来我的github参观参观看完整代码 路径点击这里–oj622-设计循环队列
