网站下载系统,软件技术专升本,和平网站建设公司,企业形象设计课程目录
一、题目#xff1a;
二、思路详解#xff1a;
1.循环队列的存储定义
2.循环队列的创建
3.循环队列的判空与判断情况
(1) 循环队列的判空: (2) 循环队列的判满
4.循环队列元素的插入
5.循环队列元素的删除
6.获取队头元素
7.获取队尾元素
8.循环队列释放
三…目录
一、题目
二、思路详解
1.循环队列的存储定义
2.循环队列的创建
3.循环队列的判空与判断情况
(1) 循环队列的判空: (2) 循环队列的判满
4.循环队列元素的插入
5.循环队列元素的删除
6.获取队头元素
7.获取队尾元素
8.循环队列释放
三、完整代码展示 一、题目 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。 你的实现应该支持如下操作 MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 难度中等 题目链接622. 设计循环队列 示例
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题目解析就是根据题中给的接口进行函数的实现。要求我们实现一个循环队列。
用心阅读下方会有很大的收获。 二、思路详解
1.循环队列的存储定义
首先我们需要定义出一个循环队列的存储定义这里采用的是使用动态数组来进行模拟循环队列根据题中给出的接口返回类型我们可以知道循环队列的数据类型为int 。
其次还需定义两个记录数组的下标一个记录队列的队头另一个记录队列的队尾(也就是指向要入队的下一个元素的位置)。另外还要提供一个表示要存储数据的具体个数。
如图 代码
//采用动态数组的形式来模拟循环队列
typedef struct {int* a; //指向数组int front; //队头int tail; //队尾int k; //数据个数
} MyCircularQueue;
2.循环队列的创建
循环队列的创建先使用malloc进行创建一个 循环队列空间
接着根据给的数据个数k让指针a指向一个动态数组在分别对front,tail,k进行初始化注意tail 0表示要存放的下一个数据元素的位置对动态数组a开辟空间的时候要多开辟一个空间避免假溢出的现象。最后一定要返回之前创建的循环队列。
代码
//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {//使用动态内存函数来申请内存//这里多申请一个空间的目的是防止假溢出//使用malloc创建一个循环队列MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//为循环队列里面的指针a ,让a指向一个长度为k1的数组obj-a (int*)malloc(sizeof(int)*(k1));obj-front 0; //队头从数组的下标0开始obj-tail 0; //队尾指向下一个元素obj-k k; //队列的长度为kreturn obj;
}
物理存储情况如图 但是我们一般会到其循环的逻辑结构逻辑存储如图 3.循环队列的判空与判断情况
循环队列的插入和删除是不可避免的当这之前就需要先完成判和判满的接口。注意一定要把判空和判满的函数实现放在队列插入和删除函数实现的前面。
(1) 循环队列的判空:
根据函数的返回类型是bool空我们就返回true ,否则返回false。
isEmpty(): 检查循环队列是否为空。
因为这里采取的是通过动态数组来模拟循环队列所以队列空的条件就是当front tail 的时候此时的循环队列就是空的。
如图 代码
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//队空就是队头与队尾相同时return obj-front obj-tail;
} (2) 循环队列的判满 同样根据函数的返回类型是bool空我们就返回true ,否则返回false。
isFull(): 检查循环队列是否已满。
什么时候会满呢当(tail1)%(k1) front,就是队尾下标加1模开辟空间的个数
可能很多会对为什么要多开辟一个空间原因就在这对于队列的判满的情况
当没有创建的额外空间队列只有数据10 和 11 的情况下 像上图就是假溢出现象这个队列并没有满。
总的来说
循环队列为了区分队列的空和满需要额外增加一个空的元素来占据队列的一个位置这样队列满的状态就可以通过头尾指针相邻且不重合来判断而不会出现头尾指针重合但队列实际上并不满的情况。同时循环队列需要对头尾指针进行模运算如果没有额外的空间那么当队列最后一个元素占据了数组最后一个位置时下一个元素就会从数组的第一个位置开始这样就无法正确进行模运算而增加一个空的元素可以解决这个问题。 代码
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-tail1)%(obj-k1) obj-front;
} 4.循环队列元素的插入
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
插入前判断是否满满就返回false,接着就是数据的插入插入后对tail下标进行取模(因为是反复利用原来的空间还有就是避免溢出)插入成功就返回true。 代码
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先进行判断是否满if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj-a[obj-tail] value;obj-tail;//避免tail的下标越界obj-tail%(obj-k1);return true;
} 5.循环队列元素的删除 删除前要进行判断是否为空。队头减一进行删除删除后取模。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 代码
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素队列不能为空if(myCircularQueueIsEmpty(obj)){return false;}//出队头删obj-front;obj-front%(obj-k1);return true;
} 6.获取队头元素
获取前进行判断是否为空。
Front: 从队首获取元素。如果队列为空返回 -1 代码
//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}return obj-a[obj-front];
}
7.获取队尾元素
获取前进行判断是否为空。
Rear: 获取队尾元素。如果队列为空返回 -1 代码
//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}//注意当tail 0的情况return obj-a[(obj-tail - 1 obj-k1)%(obj-k1)];
}解释一下 上述最后一行代码
重点
首先tail是指向要存放下一个元素的位置找队尾元素时tail要进行-1。 因为数组下标最小是从0开始的当tail 0且队列不为空的情况下上方代码obj-tail-1,就会造成0-1 -1的情况。上方采用(obj-tail - 1 obj-k1)%(obj-k1)就可以完美的避免当然
其实可以写成
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;// return obj-a[(obj-tail-1 obj-k1)%(obj-k1)];if(obj-tail 0){return obj-a[obj-k];}else{return obj-a[obj-tail-1];}
}
8.循环队列释放 因为用malloc开辟的动态内存空间为了避免内存泄漏我们还要释放内存。注意释放的顺序。 代码
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
三、完整代码展示 代码 //采用动态数组的形式来模拟循环队列
typedef struct {int* a; //指向数组int front; //队头int tail; //队尾int k; //数据个数
} MyCircularQueue;//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {//使用动态内存函数来申请内存//这里多申请一个空间的目的是防止假溢出//使用malloc创建一个循环队列MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//为循环队列里面的指针a ,让a指向一个长度为k1的数组obj-a (int*)malloc(sizeof(int)*(k1));obj-front 0; //队头从数组的下标0开始obj-tail 0; //队尾指向下一个元素obj-k k; //队列的长度为kreturn obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//队空就是队头与队尾相同时return obj-front obj-tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-tail1)%(obj-k1) obj-front;
}//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//插入元素前先进行判断是否满if(myCircularQueueIsFull(obj)){return false;}//插入元素使用尾插obj-a[obj-tail] value;obj-tail;//避免tail的下标越界obj-tail%(obj-k1);return true;
}//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//删除元素队列不能为空if(myCircularQueueIsEmpty(obj)){return false;}//出队头删obj-front;obj-front%(obj-k1);return true;
}//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}return obj-a[obj-front];
}//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//队列不能为空if(myCircularQueueIsEmpty(obj)){return -1; //队空返回-1}//注意当tail 0的情况return obj-a[(obj-tail - 1 obj-k1)%(obj-k1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj myCircularQueueCreate(k);* bool param_1 myCircularQueueEnQueue(obj, value);* bool param_2 myCircularQueueDeQueue(obj);* int param_3 myCircularQueueFront(obj);* int param_4 myCircularQueueRear(obj);* bool param_5 myCircularQueueIsEmpty(obj);* bool param_6 myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/
