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