数据结构之——OJ题环形队列实现详解
目录
数组版队列图:
针对方法2:
方法1.为数组预留一块空闲的空间
方法2.使用size统计队列存入的个数
之前我发了一篇关于队列的数据结构实现博客,有兴趣的伙伴们可以去看看:
数据结构之——队列详解 ( 1 )_
队列的原则是先进先出,后进后出,所以队列有两个指针:队头(head)和队尾( tail )指针,head 用于指向队列的头部位置并且插入元素,tail用于指向队列的尾部位置并删除元素,而接下来讲的循环队列也是要遵循以上规则。
队列是一条直线,循环队列就像一个圆一样,头尾相接:
队列既可以用数组实现,也可以用链表实现,循环队列也是如此,而且循环队列的长度是固定的,那么它只支持一次性 的堆区空间开辟!大多数情况是使用数组实现,那么下面我来展示一下数组版的队列图解:
数组版队列图:
通过图解发现,每次添加数据后,tail就会指向队尾位置的下一个位置。
当队列为空和队列为满时,head和tail指针都指向同一个位置。
在图3中 head和tail指针又指向了同一个位置,此时数组为满,所以产生一个问题:当队列为空或者为满时,无法区分,头尾指针都指向同一块空间!那么该如何区分呢?
其实有两种方法进行区分:
方法1.为队列创建一个size,用于统计队列存入数据的个数,这样当size==0时,那么即使head和tail指向同一块空间,也为空;size==数组总长度时,head和tail指向同一块空间表示队列数据已满。
方法2:在开辟数组的过程中,多预留一块空间,这块空间不需要存储数据,当尾指针tail指向的位置的下一个位置如果是队头指针head指向的位置,表明队列已满;若tail指向的位置的下一个位置不为head,则表明队列为空。
针对方法2:
例下图:当队列中存入了7个数据后,tail指向数据7的下一块空间,而方法2针对队列为空或满的方式为:tail位置的下一个位置为head指向的位置,表明已满,所以图1的队列(数组是满的)
而图2的队列经过删除数据1,2,3,且又添加数据9,10后,tail的位置的下一个位置并不是head指向的位置,所以该队列不满(数组允许存储的个数为7个,而只存储了6个)
注:数组中始终有一块空间不允许存储值。
基于此,这两种方法均可以很好的用来分辨队列空或者满的情况。
而今天要实现的是力扣的OJ题:设计循环队列。通过上述的讲解,我们可以轻松的实现该题
方法1.为数组预留一块空闲的空间
循环队列实现代码:
//方法3.多预留一个空间时的取余方法
//环形队列————长度是固定的,所以删除数据时不可以free掉那块空间
typedef struct {
int* arr;
int head;
int tail;
int N; //N表示要为数组原有长度多预留一个空间
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) { //K就是原有的长度
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr = (int*)malloc(sizeof(int) * (k + 1));
obj->head = obj->tail = 0;
obj->N = k + 1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判断队列是否为空
//if (obj->head == obj->tail)//若头指针与尾指针指向的位置相同
//(之前初始化的时候让头尾指针都指向数组首元素),说明为空
return true;
else //若两指针位置各不相同,说明队列不为空
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) { //判断队列是否满了
//若尾指针+1取余数组现有长度后仍指向队头指针,说明是满的
//尾指针指向的位置的下一个位置如果等于头指针指向的位置,表明队列满了!!!
if ((obj->tail + 1) % obj->N == obj->head) {
return true;
}
//否则不满
else
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//判断若队列若不满(不满包括队列为空和数据个数不超过数组长度k,
//才可以插入元素value——队列只能尾插
if (myCircularQueueIsFull(obj))
return false; //队列满了则不允许再添加数据
else {
obj->arr[obj->tail] = value;
obj->tail++;
//若尾指针++到超过数组长度N时,需要尾指针回到数组开头往后加————
//因为是环形队列
obj->tail = obj->tail % (obj->N); //让尾指针回到开头的方法.取余
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//判断若队列不为空(不空包括满和数据个数大于0)则可以删除元素——队列只能头删
if (myCircularQueueIsEmpty(obj))
return false;
else {
//头删后,头指针需要指向下一个数据,所以head++,只要跳过就行,
//不用删除数据,因为新添加的数据会覆盖掉原有数据
obj->head++;
//若头指针++到超过数组长度N时,需要头指针回到数组开头往后加,因为是环形队列
obj->head = obj->head % (obj->N);
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
return obj->arr[obj->head];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return -1;
}
else {
//情况1:尾指针不处在边界位置时,非特殊情况,back-1
//因为尾插后back所处位置有了新数据,back要指向下一个位置等待新数据的到来
if (obj->tail != 0) {
return obj->arr[obj->tail - 1];
}
else {
//情况2:尾指针处在特殊情况时,即尾指针指向开头,
//那要返回数组的最后一个元素,因为数
//组的最后一个元素被添加后,back才来到了数组开头
//所以应该返回数组的最后一个元素
return obj->arr[obj->N - 1];//
}
}
}
//释放堆区空间
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}
方法2.使用size统计队列存入的个数
//方法2.使用size统计
typedef struct {
//第一种实现:
int* data;
//第一个元素的位置: 队头位置
int front;
//最后一个元素的下一个位置
int rear;
//数组长度
int k;
//数组当前存储的个数
int size;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
//多开一个元素的空间
MyCircularQueue* mq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//以下为结构体成员的初始化
//为结构体指针中的成员变量开辟的空间
mq->data = (int*)malloc(sizeof(int) * k);
mq->front = mq->rear = 0;
mq->k = k;
mq->size = 0;
return mq;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if (obj->size == 0)
return true;
else
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (obj->size == obj->k)
return true;
else
return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//判断队列是否已满
if (myCircularQueueIsFull(obj))
return false;
obj->data[obj->rear++] = value;
//判断队尾是否越界
if (obj->rear >= obj->k)
obj->rear = 0;
++obj->size;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//判断队列是否为空
if (myCircularQueueIsEmpty(obj))
return false;
//出队
obj->front++;
//判断队头是否越界
if (obj->front >= obj->k)
obj->front = 0;
--obj->size;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return -1;
else
return obj->data[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return -1;
//返回队尾rear的前一个位置的元素
//判断rear是否为0;
if (obj->rear != 0)
return obj->data[obj->rear - 1];
else
return obj->data[obj->k - 1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->data);
free(obj);
}