第三章：5.栈和队列 -- 循环队列的表示及实现

前言：

　　在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个变量（虚拟指针）： front 和 rear 分别指向头和尾对应的数组下标。为了在 C 语言中描述的方便，在此：初始化建空队列时，令 front = rear=0 。当插入新元素时， “尾指针” 增1；每当删除队列头元素时， “头指针”增1 。如下图：

　　存在问题：在执行到（d）步的时候，空间已满，但是队列头部前的4 个结点空间实际上却是空的。

　　解决方案：在执行到（d）步的时候，继续往空间的起始位置插入元素（即：将顺序结构队列臆想为一个循环的结构）。那么这种结构的队列就是循环队列。

　　1、栈

　　2、栈的应用举例

　　3、栈与递归的实现

　　4、队列

　　5、离散事件模型

正文：

　　循环队列

　　　　当队列为循环队列时。

　　　　　　1.“指针” 和队列之间的关系不变。

　　　　　　2.但是无法通过 front = rear 来判断队列是否为空。详细情况可看下图 3.14

　　　　　　此时我们规定当“队列头指针” 在 “队列尾指针” 的下一位置时，队列满，不能再进行插入操作。

　　　　存储结构如下：

　　　　　　#define MAXQSIZE 5
　　　　　　//结点定义
　　　　　　typedef struct{
　　　　　　   QElemType *base;               //单链表中结点的数据域
　　　　　　   int front;                       　　//队列 “头指针”
　　　　　　    int rear;                       　　//队列 “尾指针”
　　　　　　}SqQueue;

　　　　说明：

　　　　　　当 MAXQSIZE 设为 5时，rear=4。此时插入新的元素e，发现队列未满，下标为 0 的空间元素已被删除。

　　　　　　　　1. 那么此时 base[4]=e ;

　　　　　　　　2. rear 指向下一个下标：rear = 4 +1 =5。因为5 不存在，因此正确写法为： rear = (rear +1)%MAXQSIZE。 rear= (4+1)%5=0 ；

　　　　代码实现：

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define MAXQSIZE 5
//Status是函数的类型，其值是函数结果状态码
typedef int Status;

typedef int QElemType;

//结点定义
typedef struct{
    QElemType *base;                //单链表中结点的数据域
    int front;                        //队列 “头指针”
    int rear;                        //队列 “尾指针”
}SqQueue;

//初始化队列
Status InitQueue(SqQueue &Q){
    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

//返回队列长度
int QueueLength(SqQueue &Q){
    //int len;
    //len=Q.rear-Q.front;  (Q.rear < Q.front) 否则为负数
    //len=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; 
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

//插入元素
Status EnQueue(SqQueue &Q,QElemType e){
    if(QueueLength(Q) == MAXQSIZE-1)        //队列 满
        return ERROR;

    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}

//删除元素
Status DeQueue(SqQueue &Q,QElemType &e){
    if(QueueLength(Q) == 0)                    //队列为空
        return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}

//打印所有元素
void printV(SqQueue &Q){
    if(QueueLength(Q) == 0)                    //队列为空
        printf("%s","队列为空");
    
    int q=Q.front;
    int r=Q.rear;

    printf("front：%d
",q);
    printf("rear：%d
",r);
    while(q!=r){
        printf("下标：%d",q);
        printf("值：%d
",Q.base[q]);
        q=(q+1)%MAXQSIZE;
    }
}

void main(){
    SqQueue Q;
    InitQueue(Q);

    EnQueue(Q,1);
    EnQueue(Q,2);
    EnQueue(Q,3);
    EnQueue(Q,4);
    printV(Q);    

    QElemType e;
    DeQueue(Q,e);
    printf("
删除元素：%d
",e);
    DeQueue(Q,e);
    printf("删除元素：%d

",e);
    printV(Q);

    printf("
%s

","插入元素，下标越界，从base端继续开始分配");
    EnQueue(Q,5);
    EnQueue(Q,6);
    printV(Q);
    
    printf("
length:%d
",QueueLength(Q));
}

　　　　运行结果：