数据结构之——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);
}