建立自己的网站怎么样做厦门seo专业培训学校
文章目录
- 一、循环队列的构建
- 二、判断是否为空
- 三、判断队列是否满了
- 四、队列插入
- 五、队列的删除
- 六、队列取头尾
设计循环队列

下面是队列提供的接口函数
typedef struct {int* a;int k;int front;int rear;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(Queue==NULL){perror("malloc fail");return NULL;}Queue->a = malloc(sizeof(int)*(k+1));Queue->k=k;Queue->front = Queue->rear=0;return Queue;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);}return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj->front++;obj->front%=(obj->k+1);}return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
一、循环队列的构建
这里我们用数组构建循环队列,因为如果用链表的话需要前后衔接,用双向循环列表,比较麻烦,用数组的话不需要衔接,因为数组是连续的。
然后就是用循环队列里面需要设置front和rear两个整数来判断这个循环队列是否为空或者是否满了
这里的rear必须是指向尾元素的下一个位置因为这样容易判断队列是否为空,如果不指向下一个元素那么有一个元素的情况下rear和front的值相同,没有元素的情况下rear与front的值还是相同。
typedef struct {int* a;int k;int front;int rear;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* Queue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(Queue==NULL){perror("malloc fail");return NULL;}Queue->a = malloc(sizeof(int)*(k+1));Queue->k=k;Queue->front = Queue->rear=0;return Queue;
}
二、判断是否为空
1.没有元素的情况下
2.有元素的情况下
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}
三、判断队列是否满了
1.第一种情况
rear+1 = front
2.第二种情况
这里的rear需要除以一个周期,因为我们开辟了k+1个空间,所以这里的rear对应的值为k,所以需要+1除以一个周期k+1才能回到最开始的位置
即:(rear+1)%(k+1)==front
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}
四、队列插入
需要判断这个队列是否满了
然后还有个细节的地方,如下图
此时的rear需要回到第一个位置,不然后面继续插入数据,数组出现越界访问
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj->a[obj->rear]=value;obj->rear++;obj->rear%=(obj->k+1);}return true;
}
五、队列的删除
基本上与上面的原理差不多
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj->front++;obj->front%=(obj->k+1);}return true;
}
六、队列取头尾
取头很简单,重要的是取尾
取尾我们知道rear-1就是尾,但是我们忽略了一种特殊情况
这种情况下rear-1为负数,所以我们需要回正,再者考虑其他正常情况,我们需要加上队列的一个周期k+1然后%(k+1)
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}