知名网站开发,贵州做网站的,品牌建设对企业的作用,h5免费制作app文章目录
1.循环队列的定义
2.循环队列的判空判满
3.创建队列并初始化
4.入队和出队
5. 返回队尾队首元素
6.释放循环队列 1.循环队列的定义 定义#xff1a;存储队列元素的表从逻辑上被视为一个环。 我们此次实现的循环队列#xff0c;采用顺序表 typedef struct {int… 文章目录
1.循环队列的定义
2.循环队列的判空判满
3.创建队列并初始化
4.入队和出队
5. 返回队尾队首元素
6.释放循环队列 1.循环队列的定义 定义存储队列元素的表从逻辑上被视为一个环。 我们此次实现的循环队列采用顺序表 typedef struct {int*a;int front;int rear;int k;} MyCircularQueue; 本质上是一个出入受限的顺序表那我们是怎么实现他的环状结构的呢毕竟顺序表是一个线性的结构而不是环状的。 答 他用取模运算刚好在存储空间上变成了“环状”。 例如我们要走一个环状顺序表 如果我们将rear1front2在逻辑上我们可以正常移动但其实我们物理存储上的指针已经溢出了所以我们刚好可以取模来控制指针的移动。 如果我们尾指针前进一步就可以Q.rear1% k刚好可以到达front的位置。 2.循环队列的判空判满 如图我们可以看到此时rearfront既可以是判空的条件也可以是判满的条件那我们应该怎么区分呢有三种方法://这里的指针变量会和题目中的不太一样但是判断逻辑相同 1.牺牲一个单元来进行区分 队满Q.rear1%MaxSize Q.front 队空 Q.frontQ.rear 2.设置一个Size表示队列元素长度来判断。 队满SizeMaxSize; 队空Size0 3.设置一个 tag标记 tag0 Q.frontQ.rear,队空 tag1 Q.frontQ.rear,队满。 isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);if(obj-rearobj-front ){return true;}return false ;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);if((obj-rear1)%(obj-k1)obj-front ){return true;}return false ;
} 3.创建队列并初始化 MyCircularQueue(k): 构造器设置队列长度为 k MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建一个循环的队列结构体指针节点obj-a(int*)malloc(sizeof(int)*(k1)) ;//队列长度为k但是要多一个空间用来判断空还是满obj-frontobj-rear0;obj-kk;return obj;
}队列长度为k但是要多一个空间用来判断空还是满 所以我们用的是第一种判空判满策略牺牲一个存储空间 4.入队和出队 入队操作: obj-a[obj-rear]value; obj-rear(obj-rear1)%(obj-k1);// 先赋值再移动指针 出队操作 obj-front(obj-front1)%(obj-k1);// 直接移动指针 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if (myCircularQueueIsFull(obj)){return false;}obj-a[obj-rear]value;obj-rear(obj-rear1)%(obj-k1);return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)){return false;}obj-front(obj-front1)%(obj-k1);return true;
}5. 返回队尾队首元素 Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。 int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-front];}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)){return -1;}else{int rearobj-rear0 ? obj-k : obj-rear-1;return obj-a[rear]; }
} int rearobj-rear0 ? obj-k : obj-rear-1; 由于队尾后面还有一个用于判空判满的空间如果rear刚好指向这片空间他实际上是指向的真正的队尾下标为k如果不为0说明他指向的空间为正常的前驱结点。 6.释放循环队列 切记: 先释放结构体指针指向的创建的队列所在的空间再去释放结构体指针的空间。 void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
