【数据结构】第3章栈和队列循环队列

矫情吗；* 2022-11-28 00:49 214阅读 0赞

【循环队列的初始化、判空、判满、长度、取队头元素、入队、出队、遍历】

--------------------

> 为解决“假溢出” 问题，将顺序队列变为一个环状的空间，变成循环队列；循环队列少一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满

`Q.front`：int型队头指针，初始等于0，队非空时指向队头元素  
`Q.rear`：int型队尾指针，初始等于0，队非空时指向队尾元素的下一个位置  
队满： `(Q.rear+ 1) % MAXQSIZE == Q.front` 尾指针在循环意义上加1后等于头指针，则认为队满  
队空： `Q.front == Q.rear`  
入队：`Q.rear = (Q.rear + 1) % MAXQSIZE` 尾指针在循环意义上加1  
出队：`Q.front = (Q.front + 1) % MAXQSIZE` 头指针在循环意义上加1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic 1]

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int QElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----队列的顺序存储结构-----
    #define MAXQSIZE 100
    typedef struct 
    {
        
        QElemType *base;    //储存空间的基地址
        int front;          //头指针
        int rear;           //尾指针
    }SqQueue;
    
    SqQueue Q;
    
    //1、循环队列初始化
    Status InitQueue(SqQueue &Q)
    {
        
        Q.base = new QElemType[MAXQSIZE];   //为队列分配一个最大容扯为MAXSIZE的数组空间
        if(!Q.base)
            exit(OVERFLOW);                 //存储分配失败
        Q.front = Q.rear = 0;               //头指针和尾指针为0，队列为空
        return OK;
    }
    
    //4、循环队列判空
    Status QueueEmpty(SqQueue Q)
    {
        
        if(Q.front == Q.rear)
            return OK;
        else
            return ERROR;
    }
    
    //5、循环队列长度
    int QueueLength(SqQueue Q)
    {
        //返回Q的元素个数，即队列的长度
        return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    //非循环队列Q.rear - Q.front，循环队列可能为负，故先加再模
    }
    
    //6、循环队列取队头元素
    QElemType GetHead(SqQueue Q)
    {
        //返回Q队头元素，不修改队头指针
        if(Q.front != Q.rear)            //队列非空
            return Q.base[Q.front];      //返回队头元素的值，队头指针不变
    }
    
    //7、循环队列入队
    Status EnQueue(SqQueue &Q, QElemType e)
    {
        //插入元素e为Q 的新队尾元素
        if((Q.rear + 1) % MAXQSIZE == Q.front)  //尾指针在循环意义上加1后等于头指针，表明队满
            return ERROR;
        Q.base[Q.rear] = e;                     //新元素插入队尾
        Q.rear = (Q.rear + 1) % MAXQSIZE;       //队尾指针加1
        return OK;
    }
    
    //8、循环队列出队
    Status DeQueue(SqQueue &Q, QElemType &e)
    {
        //删除Q的队头元素，用e返回其值
        if(Q.front == Q.rear)
            return ERROR;                   //队空
        e = Q.base[Q.front];                //保存队头元素
        Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
        return OK;
    }
    
    //9、循环链表遍历
    Status QueueTraverse(SqQueue Q)
    {
        
        if(Q.front == Q.rear)
            return ERROR;  
        for(int i = Q.front; i < Q.rear; i++)
            cout<<Q.base[i]<<' ';
        cout<<'\n';
        return ERROR;
    }
    
    //10、循环队列判满
    Status QueueFull(SqQueue Q)
    {
        
        if((Q.rear + 1) % MAXQSIZE == Q.front)
            return OK;
        else
            return ERROR;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic]: https://img-blog.csdnimg.cn/20200815130748219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky,size_16,color_FFFFFF,t_70#pic
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic 1]: /images/20221124/a79beb919d4b4299a494278a29fedfd8.png