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

⭐️个人主页: 收藏加关注,永远不迷路~ ⭐️


前言

🌱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;
}

五、运行结果

❄️❄️❄️


总结

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