赞
踩
目录
利用数组实现循环队列,重点要解决的问题有三个:
由于数组大小k是确定的,要实现队列循环就需要让数组下标循环,利用两个下标front、back分别指向首元素和尾元素的下一个位置。front = (front+1) % k,back = (back+1) % k,即可完成下标的循环。
初始化时,front和back都为0,此时为空。因此我们确定判空条件为 front = back时循环队列为空。
我们发现,当队列满时,由于back指向队尾元素的下一个,因此队列满时,front = back ,与队列空时相矛盾。如何解决呢?
两种解决方法:
一是:循环队列结构中新增队列大小 size ,当size=0且front = back时,队列为空;当size≠0且front = back时,队列为满。
二是:新增一个空间,不存储数据,front = (front+1) % (k+1),back = (back+1) % (k+1),当 (back+1) % (k+1) = front时,队列为满。
本文仅讲解方法二,方法一详见:数组实现循环队列(增设队列大小size)-CSDN博客
循环队列结构中包括数组、头指针、尾指针、队列容量
- //方法二
- //循环队列的结构定义
- typedef int MCQDataType;
-
- typedef struct {
- MCQDataType *a;//数组
- int front;//头指针,指向队头元素
- int back;//尾指针,指向队尾元素的下一个位置
- int k;//循环队列容量
- } MyCircularQueue;
首先动态申请一个循环队列结构体的内存空间,然后为数组动态申请k+1个内存空间,并将头指针、尾指针都初始化为0,队列容量初始化为k。
- //方法二
- //循环队列的创建及其初始化
- MyCircularQueue* myCircularQueueCreate(int k) {
- MyCircularQueue *mcq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
- mcq->a=(MCQDataType*)malloc(sizeof(MCQDataType)*(k+1));
- mcq->k=k;
- mcq->front=mcq->back=0;
- return mcq;
- }
先判断队列是否为满,不满则入队,同时尾指针要 加1模(k+1) ,back = (back+1) % (k+1)
- //方法二
- //入队
- bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
- if((obj->back+1)%(obj->k+1)==obj->front)//满队列
- {
- return false;
- }
- obj->a[obj->back]=value;
- obj->back=(obj->back+1)%(obj->k+1);
- return true;
- }
先判断队列是否为空,不空则出队,同时头指针要 加1模(k+1),front = (front+1) % (k+1)
- //方法二
- //出队
- bool myCircularQueueDeQueue(MyCircularQueue* obj) {
- if(obj->front==obj->back)//空队列
- {
- return false;
- }
- obj->front=(obj->front+1)%(obj->k+1);
- return true;
- }
先判断队列是否为空,不空则返回头指针指向的元素
- //方法二
- //取队头元素
- int myCircularQueueFront(MyCircularQueue* obj) {
- if(obj->front==obj->back)//空队列
- {
- return -1;
- }
- return obj->a[obj->front];
- }
先判断队列是否为空,不空再判断尾指针的位置:
如果尾指针指向0位置,则队尾元素在数组最后一位,即k的位置(因为总共开辟了k+1个空间);
如果尾指针不指向0位置,那么队尾元素位置是back-1。
- //方法二
- //取队尾元素
- int myCircularQueueRear(MyCircularQueue* obj) {
- if(obj->front==obj->back)//空队列
- {
- return -1;
- }
- if(obj->back==0)
- {
- return obj->a[obj->k];//重点
- }
- else
- {
- return obj->a[obj->back-1];
- }
- }
判空条件是 front = back
- //方法二
- //判空
- bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
- return obj->back==obj->front;
- }
判满条件是 (back+1)%(k+1) = front
- //方法二
- //判满
- bool myCircularQueueIsFull(MyCircularQueue* obj) {
- return (obj->back+1)%(obj->k+1)==obj->front;
- }
动态申请的内存空间都要动态销毁free
- //方法二
- //销毁循环队列
- void myCircularQueueFree(MyCircularQueue* obj) {
- free(obj->a);
- free(obj);
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。