新人小白的第一篇博客
️希望大家多多关注
以后会经常更新哒~

️个人主页： 收藏加关注，永远不迷路~ ️

---

前言

Tips：文章有点长，小主耐心一点哦~

编程实现循环队列的基本操作：建队列，取队头元素，入队，出队

---

一、循环队列是什么？

1️⃣我们先来介绍线性表： 数据结构分为线性结构和非线性结构，队列和线性表都是线性结构。线性表是由n 个数据元素组成的有限序列，该序列有惟一的“第一个”和惟一的“最后一个”数据元素；除了 “第一个”和“最后一个”之外，队列中的每个数据元素都只有一个直接前驱和一个直接后继。线性表的插入和删除操作可以在表中任意位置进行。

2️⃣再来谈谈队列：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

3️⃣队列的相关概念：队列的数据元素称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）的线性表。

4️⃣为什么要有循环队列：为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，称为循环队列。

5️⃣循环队列的相关特性：在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

---

二、定义函数

1.定义存储结构

//循环队列的存储结构
#define MAXQSIZE  100   //最大队列长度
typedef  struct
{
    QElemType *base;       //用于动态分配存储空间
    int  front;            //队头索引
    int  rear;             //队尾索引
} SqQueue;

2.初始化

//初始化
void InitQueue (SqQueue &Q)
{
    //构造一个空队列
    Q.base =new QElemType[MAXQSIZE];
    Q.front=Q.rear=0;
}

3.销毁队列

//销毁队列
void DestroyQueue(SqQueue &Q)
{
    if(Q.base)
        free(Q.base);
    Q.base = NULL;
    Q.front = Q.rear = 0;
}

4.清空队列

//清空队列
void ClearQueue(SqQueue &Q)
{
    Q.front=Q.rear=0;
}

5.求长度

//求长度
int  QueueLength (SqQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

6.判空

//判空
bool QueueEmpty (SqQueue Q)
{
    return (Q.front==Q.rear);
}

7.求队头元素

//求队头元素
Status GetHead (SqQueue Q, QElemType &e)
{
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    return OK;
}

8.循环队列入队

//循环队列入队
Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}

9.循环队列出队

//循环队列出队
Status DeQueue (SqQueue &Q,QElemType &e)
{
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1) % MAXQSIZE;
    return OK;
}

10.遍历使队列显示

//遍历使队列显示
void DisplayQueue(SqQueue Q)
{
    int i=Q.front;
    while(Q.front!=Q.rear && (i+MAXQSIZE) % MAXQSIZE != Q.rear)
    {
        cout<<Q.base[i]<<endl;
        i++;
    }
}

---

三、定义小菜单

可以采用小菜单使界面更加好看呦~

void show_help()
{
    cout<<"******* Data Structure ******"<<endl;
    cout<<"1----清空循环队列"<<endl;
    cout<<"2----判断循环队列是否为空"<<endl;
    cout<<"3----求循环队列长度"<<endl;
    cout<<"4----取队头元素"<<endl;
    cout<<"5----入队"<<endl;
    cout<<"6----出队"<<endl;
    cout<<"7----显示队列"<<endl;
    cout<<"     退出，输入0"<<endl;
}

---

四、完整代码

️️️

#include <iostream>
using namespace std;
#define ERROR -1
#define OK 1
typedef int QElemType;
typedef int Status;
//循环队列的存储结构
#define MAXQSIZE  100   //最大队列长度
typedef  struct
{
    QElemType *base;       //用于动态分配存储空间
    int  front;            //队头索引
    int  rear;             //队尾索引
} SqQueue;
//初始化
void InitQueue (SqQueue &Q)
{
    //构造一个空队列
    Q.base =new QElemType[MAXQSIZE];
    Q.front=Q.rear=0;
}
//销毁队列
void DestroyQueue(SqQueue &Q)
{
    if(Q.base)
        free(Q.base);
    Q.base = NULL;
    Q.front = Q.rear = 0;
}
//清空队列
void ClearQueue(SqQueue &Q)
{
    Q.front=Q.rear=0;
}
//求长度
int  QueueLength (SqQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
//判空
bool QueueEmpty (SqQueue Q)
{
    return (Q.front==Q.rear);
}
//求队头元素
Status GetHead (SqQueue Q, QElemType &e)
{
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    return OK;
}
//循环队列入队
Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear = (Q.rear+1) % MAXQSIZE;
    return OK;
}
//循环队列出队
Status DeQueue (SqQueue &Q,QElemType &e)
{
    if(Q.front==Q.rear) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1) % MAXQSIZE;
    return OK;
}
//遍历使队列显示
void DisplayQueue(SqQueue Q)
{
    int i=Q.front;
    while(Q.front!=Q.rear && (i+MAXQSIZE) % MAXQSIZE != Q.rear)
    {
        cout<<Q.base[i]<<endl;
        i++;
    }
}
void show_help()
{
    cout<<"******* Data Structure ******"<<endl;
    cout<<"1----清空循环队列"<<endl;
    cout<<"2----判断循环队列是否为空"<<endl;
    cout<<"3----求循环队列长度"<<endl;
    cout<<"4----取队头元素"<<endl;
    cout<<"5----入队"<<endl;
    cout<<"6----出队"<<endl;
    cout<<"7----显示队列"<<endl;
    cout<<"     退出，输入0"<<endl;
}
int main()
{
    char operate_code;
    show_help();
    SqQueue Q;
    InitQueue(Q);
    QElemType e;
    int i;
    while(1)
    {
        cout<<"请输入操作代码:";
        cin>>operate_code;
        if(operate_code=='1')
        {
            cout<<"The queue has been cleared."<<endl;
            ClearQueue(Q);
        }
        else if (operate_code=='2')
        {
            if(QueueEmpty(Q))
                cout<<"The queue is empty."<<endl;
            else
                cout<<"The queue is not empty."<<endl;
        }
        else if (operate_code=='3')
        {
            cout<<"The length of queue is:"<<QueueLength(Q)<<endl;
        }
        else if (operate_code=='4')
        {
            cout<<"队头元素为："<<endl;
            if(GetHead(Q,e) == 1) cout<<e<<endl;
            else cout <<"error"<<endl;
        }
        else if (operate_code=='5')
        {
            cout<<"请输入你想要入队的数："<<endl;
            cin>>e;
            EnQueue(Q,e);
        }
        else if (operate_code=='6')
        {
            cout<<"出队元素为："<<endl;
            if(DeQueue(Q,e)) cout<<e<<endl;
        }
        else if (operate_code=='7')
        {
            cout<<"The contents of the queue are:"<<endl;
            DisplayQueue(Q);
        }
        else if (operate_code=='0')
        {
            break;
        }
        else
        {
            cout<<"\n操作码错误！！！"<<endl;
            show_help();
        }
    }
    //调用销毁栈函数
    DestroyQueue(Q);
    return 0;
}

---

五、运行结果

️️️

---

总结

本文用来介绍数据结构中循环队列的代码实现过程及运行结果示例。采用菜单样式显示循环队列的初始化、清空、销毁、求长度，求队头元素、判空、入队，出队，以及遍历队列使其显示等操作。