数据结构第九弹---循环队列

1、循环队列的定义

顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。

2、循环队列的结构

typedef struct CircularQueue{
    int* a;//存放数据数组
    int front;//头结点
    int back;//尾结点后一个，有效数据个数
    int k;//元素个数
} CircularQueue;

3、循环队列的实现

3.1、初始化队列

开辟k+1个空间，k个存放数据，将头尾结点初始化为0，即数组的第一个位置。

代码实现

//队列初始化
CircularQueue* InitQueue(int k)
{
     CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间
     obj->a=(int*)malloc(sizeof(int)*(k+1));
     obj->front=obj->back=0;//初始队列为空，头尾指针都指向0的位置
     obj->k=k;
     return obj;
}

测试

3.2、判断是否为空

根据结构定义，头结点跟尾结点相等时则队列为空。为真则为空，为假则不为空。

代码实现

bool QueueEmpty(CircularQueue* obj) {
    return obj->front==obj->back;//头尾结点相等时则为空
}

测试

3.3、判断是否为满

根据循环队列结构的定义，尾结点后一个是头结点则队列为满。为真则为满，不为真则不满。

代码实现

bool QueueFull(CircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满
}

测试

3.4、入队

根据队列的结构定义，back为尾结点的后一个，当队列空间没有满时，插入数据时则在back位置插入。

代码实现

bool EnQueue(CircularQueue* obj, int value) {
    //满了返回false
    if(QueueFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;//插入有效数据
    obj->back++;
    obj->back%=(obj->k+1);//进入循环，不能超过最大个数
    
    return true;
}

测试

3.5、出队

根据队列的定义，只能队头出数据，在循环队列里面通过头尾结点来访问数据，将front++即可删除头结点数据。

代码实现

bool DeQueue(CircularQueue* obj) {
    //如果为空返回false
    if(QueueEmpty(obj))
    {
        return false;
    }
    obj->front++;//出队则头结点往前走
    obj->front%=(obj->k+1);
    return true;
}

测试

3.6、返回队头元素

在保证队列不是空的情况下，队头元素为front下标的元素，为空则返回-1

代码实现

int QueueFront(CircularQueue* obj) {
    //为空返回-1
    if(QueueEmpty(obj))
            return -1;
    return obj->a[obj->front];
}

测试

3.7、返回队尾元素

在保证队列不是空的情况下，队头元素为back前一个下标的元素，为空则返回-1

代码实现

int QueueRear(CircularQueue* obj) {
     //为空返回-1
    if(QueueEmpty(obj))
            return -1;

    //有一种特殊情况 不是back-1
    //1.
    //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
    return obj->a[(obj->back+obj->k)%(obj->k+1)];

    //2.
    // if(obj->back==0)
    // {
    //     return obj->a[obj->k];
    // }
    // else
    // {
    //     return obj->a[obj->back-1];
    // }
}

测试

3.8、销毁队列

数组是通过队列的指针访问，且数组和队列都是内存是连续的，可以直接释放内存，所以先释放数组，在释放队列

void QueueFree(CircularQueue* obj) {
    free(obj->a);//释放数组
    free(obj);//释放队列
}

4、代码汇总

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//结构定义
typedef struct CircularQueue{
    QDataType* a;//存放数据数组
    int front;//头结点
    int back;//尾结点后一个，有效数据个数
    int k;//元素个数
} CircularQueue;
//初始化
CircularQueue* InitQueue(int k)
{
     CircularQueue* obj=(CircularQueue*)malloc(sizeof(CircularQueue));//为队列分配空间
     obj->a=(int*)malloc(sizeof(int)*(k+1));
     obj->front=obj->back=0;//初始队列为空，头尾指针都指向0的位置
     obj->k=k;
     return obj;
}
//判断是否为空
bool QueueEmpty(CircularQueue* obj) {
    return obj->front==obj->back;//头尾结点相等时则为空
}
//判断是否为满
bool QueueFull(CircularQueue* obj) {
    return (obj->back+1)%(obj->k+1)==obj->front;//尾结点的下一个等于头结点则为满
}
//入队
bool EnQueue(CircularQueue* obj, int value) {
    //满了返回false
    if(QueueFull(obj))
    {
        return false;
    }
    obj->a[obj->back]=value;//插入有效数据
    obj->back++;
    obj->back%=(obj->k+1);//进入循环，不能超过最大个数
    
    return true;
}
//出队
bool DeQueue(CircularQueue* obj) {
    //如果为空返回false
    if(QueueEmpty(obj))
    {
        return false;
    }
    obj->front++;//出队则头结点往前走
    obj->front%=(obj->k+1);
    return true;
}
//获取队头元素
int QueueFront(CircularQueue* obj) {
    //为空返回-1
    if(QueueEmpty(obj))
            return -1;
    return obj->a[obj->front];
}
//获取队尾元素
int QueueRear(CircularQueue* obj) {
     //为空返回-1
    if(QueueEmpty(obj))
            return -1;

    //有一种特殊情况 不是back-1
    //1.
    //return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];
    return obj->a[(obj->back+obj->k)%(obj->k+1)];

    //2.
    // if(obj->back==0)
    // {
    //     return obj->a[obj->k];
    // }
    // else
    // {
    //     return obj->a[obj->back-1];
    // }
}
//销毁
void QueueFree(CircularQueue* obj) {
    free(obj->a);
    free(obj);
}

循环队列OJ链接
循环队列

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！