网站有必要备案吗,简约创意logo设计免费生成,昆明平台网站开发,湖州网站seo一、题目 设计你的循环队列实现。 循环队列是一种线性数据结构#xff0c;其操作表现基于 FIFO#xff08;先进先出#xff09;原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普…一、题目 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 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 的范围内请不要使用内置的队列库。
二、解题思路
2.1 数组实现 我们可以通过数组来模拟循环队列利用数组的索引构建一个虚拟的环形结构。在循环队列中设置两个指针队尾 rear 和队首 front队列的大小是固定的。结构如下图所示 在循环队列中当队列为空时front 和 rear 相等即 front rear而当队列的所有空间都被占满时同样会出现 front rear 的情况。为了区分这两种状态我们规定队列的数组容量为 capacity但循环队列最多只能存储 capacity - 1 个元素。当队列中只剩下一个空闲的存储单元时就认为队列已满。因此队列判空的条件是 front rear而判满的条件是 front (rear 1) % capacity。 对于一个固定大小的数组只要知道队尾 rear 和队首 front就可以计算出队列的当前长度 (rear - front capacity) mod capacity
循环队列的主要属性如下 **elements**一个固定大小的数组用于存储循环队列的元素。 **capacity**循环队列的容量即队列中最多可以容纳的元素数量。 **front**队首元素在数组中的索引。 **rear**队尾元素的下一个位置的索引。
循环队列的接口方法如下 **MyCircularQueue(int k)**初始化队列数组的空间大小为 k 1并将 front 和 rear 初始化为 0。 **enQueue(int value)**在队列的尾部插入一个元素并将 rear 更新为 (rear 1) % capacity。 **deQueue()**从队首取出一个元素并将 front 更新为 (front 1) % capacity。 **Front()**返回队首的元素需要先检测队列是否为空。 **Rear()**返回队尾的元素需要先检测队列是否为空。 **isEmpty()**检测队列是否为空只需判断 rear 是否等于 front。 **isFull()**检测队列是否已满只需判断 front 是否等于 (rear 1) % capacity。 通过这种方式循环队列能够高效地利用数组空间同时避免普通队列在空间利用上的不足。 #include iostream
#include vector
using namespace std;class MyCircularQueue {
private:int front; // 队首指针int rear; // 队尾指针int capacity; // 队列容量vectorint elements; // 用于存储队列元素的数组public:// 构造函数初始化队列MyCircularQueue(int k) {this-capacity k 1; // 容量为 k 1多分配一个空间用于区分空和满状态this-elements vectorint(capacity); // 初始化数组rear front 0; // 初始化队首和队尾指针}// 向循环队列插入一个元素bool enQueue(int value) {if (isFull()) {return false; // 队列已满插入失败}elements[rear] value; // 将元素插入队尾rear (rear 1) % capacity; // 更新队尾指针循环return true;}// 从循环队列中删除一个元素bool deQueue() {if (isEmpty()) {return false; // 队列为空删除失败}front (front 1) % capacity; // 更新队首指针循环return true;}// 获取队首元素int Front() {if (isEmpty()) {return -1; // 队列为空返回 -1}return elements[front]; // 返回队首元素}// 获取队尾元素int Rear() {if (isEmpty()) {return -1; // 队列为空返回 -1}return elements[(rear - 1 capacity) % capacity]; // 返回队尾元素处理循环情况}// 检查队列是否为空bool isEmpty() {return rear front; // 队首和队尾指针相等时队列为空}// 检查队列是否已满bool isFull() {return ((rear 1) % capacity) front; // 队尾的下一个位置是队首时队列已满}
};int main() {// 创建循环队列容量为 3MyCircularQueue circularQueue(3);// 测试 enQueue 操作cout enQueue(1): circularQueue.enQueue(1) endl; // 输出: 1 (true)cout enQueue(2): circularQueue.enQueue(2) endl; // 输出: 1 (true)cout enQueue(3): circularQueue.enQueue(3) endl; // 输出: 1 (true)cout enQueue(4): circularQueue.enQueue(4) endl; // 输出: 0 (false队列已满)// 测试 Rear 操作cout Rear(): circularQueue.Rear() endl; // 输出: 3// 测试 isFull 操作cout isFull(): circularQueue.isFull() endl; // 输出: 1 (true)// 测试 deQueue 操作cout deQueue(): circularQueue.deQueue() endl; // 输出: 1 (true)// 测试 enQueue 操作cout enQueue(4): circularQueue.enQueue(4) endl; // 输出: 1 (true)// 测试 Rear 操作cout Rear(): circularQueue.Rear() endl; // 输出: 4// 测试 Front 操作cout Front(): circularQueue.Front() endl; // 输出: 2// 测试 isEmpty 操作cout isEmpty(): circularQueue.isEmpty() endl; // 输出: 0 (false)return 0;
}
复杂度分析 时间复杂度初始化和每项操作的时间复杂度均为 O(1)。 空间复杂度O(k)其中 k 为给定的队列元素数目。 2.2 链表实现 我们也可以使用链表来实现队列。与数组相比链表实现队列更加灵活因为链表可以在 O(1)时间复杂度内完成元素的插入和删除操作。具体来说入队操作是将新元素插入到链表的尾部而出队操作则是返回链表的头节点并将头节点指向下一个节点。
循环队列的属性如下 head链表的头节点表示队列的头部。 tail链表的尾节点表示队列的尾部。 capacity队列的容量即队列可以存储的最大元素数量。 size队列当前存储的元素数量。 通过链表实现循环队列可以避免数组实现中需要处理索引循环的问题同时也能高效地完成队列的基本操作。
#include iostream
using namespace std;// 链表节点定义
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};class MyCircularQueue {
private:ListNode *head; // 队首指针指向链表的头节点ListNode *tail; // 队尾指针指向链表的尾节点int capacity; // 队列的容量int size; // 队列当前的大小public:// 构造函数初始化队列MyCircularQueue(int k) {this-capacity k; // 设置队列容量this-size 0; // 初始化队列大小为 0this-head nullptr; // 初始化队首指针为空this-tail nullptr; // 初始化队尾指针为空}// 向队列尾部插入一个元素bool enQueue(int value) {if (isFull()) {return false; // 队列已满插入失败}ListNode *node new ListNode(value); // 创建新节点if (!head) {head tail node; // 如果队列为空新节点既是队首也是队尾} else {tail-next node; // 将新节点链接到队尾tail node; // 更新队尾指针}size; // 队列大小加 1return true;}// 从队列头部删除一个元素bool deQueue() {if (isEmpty()) {return false; // 队列为空删除失败}ListNode *node head; // 保存队首节点head head-next; // 更新队首指针size--; // 队列大小减 1delete node; // 释放队首节点的内存if (isEmpty()) {tail nullptr; // 如果队列为空更新队尾指针为空}return true;}// 获取队首元素int Front() {if (isEmpty()) {return -1; // 队列为空返回 -1}return head-val; // 返回队首节点的值}// 获取队尾元素int Rear() {if (isEmpty()) {return -1; // 队列为空返回 -1}return tail-val; // 返回队尾节点的值}// 检查队列是否为空bool isEmpty() {return size 0; // 队列大小为 0 时为空}// 检查队列是否已满bool isFull() {return size capacity; // 队列大小等于容量时为满}
};int main() {// 创建循环队列容量为 3MyCircularQueue circularQueue(3);// 测试 enQueue 操作cout enQueue(1): circularQueue.enQueue(1) endl; // 输出: 1 (true)cout enQueue(2): circularQueue.enQueue(2) endl; // 输出: 1 (true)cout enQueue(3): circularQueue.enQueue(3) endl; // 输出: 1 (true)cout enQueue(4): circularQueue.enQueue(4) endl; // 输出: 0 (false队列已满)// 测试 Rear 操作cout Rear(): circularQueue.Rear() endl; // 输出: 3// 测试 isFull 操作cout isFull(): circularQueue.isFull() endl; // 输出: 1 (true)// 测试 deQueue 操作cout deQueue(): circularQueue.deQueue() endl; // 输出: 1 (true)// 测试 enQueue 操作cout enQueue(4): circularQueue.enQueue(4) endl; // 输出: 1 (true)// 测试 Rear 操作cout Rear(): circularQueue.Rear() endl; // 输出: 4// 测试 Front 操作cout Front(): circularQueue.Front() endl; // 输出: 2// 测试 isEmpty 操作cout isEmpty(): circularQueue.isEmpty() endl; // 输出: 0 (false)return 0;
}
复杂度分析 时间复杂度初始化和每项操作的时间复杂度均为 O(1)。 空间复杂度O(k)其中 k 为给定的队列元素数目。
