数据结构之队（循环队列）的基本操作和实现_循环队列的基本操作实现

引言：这篇文章的末尾有完整的实现代码，前面还是先进行分步实现，即我们探讨一下为什么要这样做，以及我们应该怎么样一步一步的实现循环队列。

目录

一、队列的概念

二、队的基本操作

三、对于队的操作，了解若干个规则

四、对队列的基本操作进行实现

（1）、队的初始化

（2）、判断队是否为空

（3）、求队列的长度

（4）、入队操作

（5）、出队操作

（6）、求队首元素

（7）、主函数

（8）、运行结果

 （9）、完整代码

总结

---

一、队列的概念

       我们可以把队列理解为食堂的排队买饭，我们只能在队尾进行排队（入队操作），然后队头的同学买完饭走了（出队操作）。所以对于队的理解就很清楚了，队就是一个只允许在队头进行出队操作，在队尾进行入队操作。即队是一个先进先出的表。（FIFO）

二、队的基本操作

（1）、队的初始化

（2）、判断队是否为空

（3）、求队列的长度

（4）、入队操作

（5）、出队操作

（6）、求队首元素

三、对于队的操作，了解若干个规则

（1）、我们首先用front和rear来标记当前队列的队首的前一个位置和队尾元素。

（2）、判断对空，那就是front和rear都标记为同一个位置。

（3）、理解这段话：那我们如何判断队满，假如说我们让这个队列一直进行入队操作，那么我们是否可以说当rear标记的位置为Maxsize-1（因为数组下标是从0开始的，Maxsize-1代表最后一个位置）时，队列就满了呢？当然不可以这样，因为我们的队首可以进行出队操作，当一直出队直到标记位为rear的标记位时，这时队列并不是队满的状态，刚好是队空。所以我们要想一个办法改变这种情况。由此引出来循环队列，我们可以把这个队设置成循环队列，这样的话就可以一直转圈的入队和出队。那我们如何判断队满呢？式子（（rear+1）%Maxsize==front），若成立则说明队满。我们可以分析一下为什么这样因为front是标记队首元素的前一个，rear是指向队尾元素，（rear+1）%Masize的意思是防止rear指向最后一个位置（Maxsize-1），当它再加1的时候，就是Maxsize了，已经超过了数组的最大下标，而如果我们再对Maxsize取余的话呢，当rear+1变为Maxsize之后再对Maxsize取余就变为了0，又回到了队列的首位置，所以我们这样做是有必要的。（rear+1）%Maxsize==front避免了rear会超出对大范围，当rear的下一个为front的时候，队就满了，因为我们是空出来了一个位置将front指向它，即front指向队首元素的前一个位置，这个位置并不存放东西。（rear+1）%Maxsize或者是（front+1）%Maxsize他们%Maxsize这个操作都是为了将当rear或者是front+1之后指向Maisize这个位置时，把它转换为0。

四、对队列的基本操作进行实现

首先声明一个队列结构体

#include <stdio.h>
#include <stdlib.h>
#define Maxsize 5
//顺序队列的实现
//重新定义数据类型,typedef在这里的意思就是重新定义它后面的东西的别名
typedef int ElemType;//这句话的意思就是定义int的别名为ElemType来代替int
//声明一个结构体
typedef struct Queue
{
    ElemType data[Maxsize];//队列能存多少元素
    int front,rear;        //front指向队列的前一个元素，rear指向队列的最后一个元素，即队尾
}SqQueue;                  //重新定义结构体的名字为SqQueue

（1）、队的初始化

//先进行初始化操作
void Init(SqQueue *s)
{
    s->front=s->rear=0;   //将队首和队尾标记队列相同的位置
}

（2）、判断队是否为空

//判断队列是否为空
int Empty(SqQueue s)
{
    if(s.front==s.rear) //因为我们在初始化的时候将它们两个相等了，所以判空直接判断
        return 1;       //为空返回真
    else
        return 0;       //不为空返回假，程序中除了0全为真
}

（3）、求队列的长度

求队列的长度，我们首先判断队列是否为空，如果不为空，判断rear是否大于front，若rear大于front直接相减即可，若rear小于front，相减之后为负数，再加上一个Maxsize即可，如果相减之后为正数，那么我们可以加上一个Maxsize再取余Maxsize即可，这样的话，不管rear是否发育front，我们都可以用(s.rear-s.front+Maxsize)%Maxsize来表示

//求队列的长度
int Length(SqQueue s)
{
    //先判断队列是否为空
    if(Empty(s))     //意思是如果队列为空则返回1，那么if括号里面的意思是不等于0的话执行里面的东西
    {
        return 0;
    }
    return (s.rear-s.front+Maxsize)%Maxsize;
}

（4）、入队操作

//入队操作
void Add(SqQueue *s,ElemType x)//将x入队
{
    //首先判断队列是否已满
    if(s->front==(s->rear+1)%Maxsize) //队列中留出一个空位置让front指向它，那么当rear+1等于front的话我们就说队满了
    {
        printf("当前队列已满，不能将值为：%d的元素入队\n\n",x);
        return;
    }
    else
    {
        s->data[(s->rear+1)%Maxsize]=x;//在rear的下一个位置存入元素x
        s->rear=(s->rear+1)%Maxsize;   //把rear的位置往后移一位
    }
}

（5）、出队操作

//出队操作
void Dele(SqQueue *s,ElemType *e)     //用e来保存出队的元素
{
    if(Empty(*s))
    {
        printf("当前队列为空，操作失败\n\n");
        return;
    }
    else
    {
        *e=s->data[(s->front+1)%Maxsize];//用e来保存出队的这个元素
        s->front=(s->front+1)%Maxsize;   //出队之后front往后移动一位
    }
}

（6）、求队首元素

//读取队首元素
ElemType Get(SqQueue s)
{
     if(Empty(s))     //意思是如果队列为空则返回1，那么if括号里面的意思是不等于0的话执行里面的东西
    {
        printf("队首元素不存在，队列为空\n\n");
        return 0;
    }
    return s.data[(s.front+1)%Maxsize];//返回队首元素，这样做的目的是防止front当前的位置在Maxsize这个位置
}

（7）、主函数

int main()
{
    SqQueue s;//定义一个队，名称s；这里也可以定义一个队指针，用这个指针来代替这个表s，修改一下函数中的参数就行。只是实现方式不同，结果相同
    //进行初始化
    Init(&s);
    ElemType e=0;
    int x;
    printf("先将队列初始化之后的头标记为：%d 尾标记为：%d\n\n",s.front,s.rear);
    printf("队列的大小为：%d\n\n",Maxsize);
    //来五次入队操作
    Add(&s,8);
    Add(&s,5);
    Add(&s,4);
    Add(&s,0);
    Add(&s,7);
    //看一下当前队的长度
    x=Length(s);
    if(x)
    {
        printf("操作完成之后，当前队列的长度为：%d\n\n",Length(s));
    }
    //读取队首元素
    x=Get(s);
    if(x)                          //如果x不为0,执行里面的东西
    {
        printf("当前队列中的队首元素为：%d\n\n",x);
    }
    //出队操作
    Dele(&s,&e);
    Dele(&s,&e);
    Dele(&s,&e);
   //读取队首元素
    x=Get(s);
    if(!(x==0&&e==0))          //如果x和e不为0,执行里面的东西
    {
        printf("出队操作之后，刚刚出队的元素为：%d,当前队首元素为：%d\n\n",e,x);
    }
    return 0;
}

（8）、运行结果

 （9）、完整代码

#include <stdio.h>
#include <stdlib.h>
#define Maxsize 5
//顺序队列的实现
//重新定义数据类型,typedef在这里的意思就是重新定义它后面的东西的别名
typedef int ElemType;//这句话的意思就是定义int的别名为ElemType来代替int
//声明一个结构体
typedef struct Queue
{
    ElemType data[Maxsize];//队列能存多少元素
    int front,rear;        //front指向队列的前一个元素，rear指向队列的最后一个元素，即队尾
}SqQueue;                  //重新定义结构体的名字为SqQueue
//先进行初始化操作
void Init(SqQueue *s)
{
    s->front=s->rear=0;   //将队首和队尾标记队列相同的位置
}
//判断队列是否为空
int Empty(SqQueue s)
{
    if(s.front==s.rear) //因为我们在初始化的时候将它们两个相等了，所以判空直接判断
        return 1;       //为空返回真
    else
        return 0;       //不为空返回假，程序中除了0全为真
}
//求队列的长度
int Length(SqQueue s)
{
    //先判断队列是否为空
    if(Empty(s))     //意思是如果队列为空则返回1，那么if括号里面的意思是不等于0的话执行里面的东西
    {
        return 0;
    }
    return (s.rear-s.front+Maxsize)%Maxsize;
}
//读取队首元素
ElemType Get(SqQueue s)
{
     if(Empty(s))     //意思是如果队列为空则返回1，那么if括号里面的意思是不等于0的话执行里面的东西
    {
        printf("队首元素不存在，队列为空\n\n");
        return 0;
    }
    return s.data[(s.front+1)%Maxsize];//返回队首元素，这样做的目的是防止front当前的位置在Maxsize这个位置
}
//入队操作
void Add(SqQueue *s,ElemType x)//将x入队
{
    //首先判断队列是否已满
    if(s->front==(s->rear+1)%Maxsize) //对列中留出一个空位置让front指向它，那么当rear+1等于front的话我们就说队满了
    {
        printf("当前队列已满，不能将值为：%d的元素入队\n\n",x);
        return;
    }
    else
    {
        s->data[(s->rear+1)%Maxsize]=x;//在rear的下一个位置存入元素x
        s->rear=(s->rear+1)%Maxsize;   //把rear的位置往后移一位
    }
}
//出队操作
void Dele(SqQueue *s,ElemType *e)     //用e来保存出队的元素
{
    if(Empty(*s))
    {
        printf("当前队列为空，操作失败\n\n");
        return;
    }
    else
    {
        *e=s->data[(s->front+1)%Maxsize];
        s->front=(s->front+1)%Maxsize;
    }
}
int main()
{
    SqQueue s;//定义一个队，名称s；这里也可以定义一个队指针，用这个指针来代替这个表s，修改一下函数中的参数就行。只是实现方式不同，结果相同
    //进行初始化
    Init(&s);
    ElemType e=0;
    int x;
    printf("先将队列初始化之后的头标记为：%d 尾标记为：%d\n\n",s.front,s.rear);
    printf("队列的大小为：%d\n\n",Maxsize);
    //来五次入队操作
    Add(&s,8);
    Add(&s,5);
    Add(&s,4);
    Add(&s,0);
    Add(&s,7);
    //看一下当前队的长度
    x=Length(s);
    if(x)
    {
        printf("操作完成之后，当前队列的长度为：%d\n\n",Length(s));
    }
    //读取队首元素
    x=Get(s);
    if(x)                          //如果x不为0,执行里面的东西
    {
        printf("当前队列中的队首元素为：%d\n\n",x);
    }
    //出队操作
    Dele(&s,&e);
    Dele(&s,&e);
    Dele(&s,&e);
    x=Get(s);
    if(!(x==0&&e==0))
    {
        printf("出队操作之后，刚刚出队的元素为：%d,当前队首元素为：%d\n\n",e,x);
    }
 
    return 0;
}

总结

       循环队列的难点就是如何判断队空和队满，以及当rear指向最后一个位置时，我们再进行入队的操作，还有当front指向最后一个位置，我们再进行出队的操作，都需要队Maxsize进行取模运算，顺序表，链表，栈，队他们的操作都很相似，大家可以对比一下，只要掌握了其中一个的操作，对于其他的操作，都可以迎刃而解，将逻辑内化于心。本人能力有限，如有表述不对的地方，欢迎批评指正。