数据结构-顺序环形队列

本是古典何须时尚 2022-07-28 04:30 227阅读 0赞

/*
    编写一个程序，实现顺序环形队列的各种基本运算（假设栈中元素类型为char）。并完成下面功能：
    （1）初始化队列q;
    （2）判断队列q是否非空；
    （3）依次进队元素a,b,c;
    （4）出队一个元素，并输出该元素；
    （5）输出队列q的元素个数；
    （6）依次进队列元素d,e,f；
    （7）输出队列q的元素个数；
    （8）输出出队序列；
    （9）释放队列。
    */
    
    #include <iostream>
    #include <malloc.h>
    #include <cstdio>
    #include <cstring>
    #define MaxSize 10
    using namespace std;
    typedef char ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int front,rear;
    }SqQueue;               //定义顺序队类型
    
    void InitQueue(SqQueue *&q)           //初始化队列q
    {
        q=(SqQueue *)malloc(sizeof(SqQueue));
        q->front=q->rear=0;
    }
    
    bool QueueEmpty(SqQueue *q)           //判断队列q是否非空
    {
        return (q->front!=q->rear);
    }
    
    bool enQueue(SqQueue *&q,ElemType e)      //进队
    {
        if((q->rear+1)%MaxSize==q->front)    //队满上溢出
            return false;
        q->rear=(q->rear+1)%MaxSize;
        q->data[q->rear]=e;
        return true;
    }
    
    bool deQueue(SqQueue *&q,ElemType &e)   //出队，并输出
    {
        if(q->front==q->rear)          //队空下溢出
            return false;
        q->front=(q->front+1)%MaxSize;
        e=q->data[q->front];
        return true;
    }
    
    int getLength(SqQueue *q)            //输出输出队列q的元素个数
    {
        return ((q->rear-q->front+MaxSize)%MaxSize);
    }
    
    void DestoryQueue(SqQueue *&q)      //释放队列
    {
        free(q);
    }
    
    int main()
    {
        ElemType a[MaxSize],e;
        SqQueue *q;
        InitQueue(q);
        cout<<"队列q是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        cout<<"输入要进队元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            enQueue(q,a[i]);
        }
        cout<<"元素已进队"<<endl;
        cout<<"队列q是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        deQueue(q,e);
        cout<<"出队一个元素并输出："<<e<<endl;
        cout<<"队列q的元素个数："<<getLength(q)<<endl;
        cout<<"输入要进队元素:";
        gets(a);
        for(int i=0;i<strlen(a);i++)
        {
            enQueue(q,a[i]);
        }
        cout<<"元素已进队"<<endl;
        cout<<"队列q的元素个数："<<getLength(q)<<endl;
        cout<<"输出出队序列：";
        for(int i=getLength(q)-1;i>=0;i--)
        {
            deQueue(q,e);
            cout<<e<<" ";
        }
        cout<<endl;
        cout<<"队列q是否非空？";
        if(QueueEmpty(q))
            cout<<"是"<<endl;
        else
            cout<<"否"<<endl;
        DestoryQueue(q);
        cout<<"队列已释放！"<<endl;
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220727/103cca53715d49329149f443e3999583.png